数据结构之链表

一、单向链表

1.定义

        1. 链表中的每一个元素称之为结点（Node）。

        2. 物理存储单元上，非连续、非顺序的存储结构。

        3. 单向链表：每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next。链表中的某个节点为B，B的下一个节点为C 表示： B.next==C。

   JAVA代码的表示：

    private static class Node<E> {
        E item;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

2.时间复杂度分析

（1）查询操作

        1. 只有在查询头节点的时候不需要遍历链表，时间复杂度是O(1)。

        2. 查询其他结点需要遍历链表，时间复杂度是O(n)。

（2）插入、删除操作

        1. 只有在添加和删除头节点的时候不需要遍历链表，时间复杂度是O(1)。

        2. 添加或删除其他结点需要遍历链表找到对应节点后，才能完成新增或删除节点，时间复杂度是O(n)。

二、双向链表

1.定义

        双向链表，顾名思义，它支持两个方向。

        1. 每个结点不止有一个后继指针 next 指向后面的结点。

        2. 有一个前驱指针 prev 指向前面的结点。

JAVA代码的表示：

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

2.时间复杂度分析

（1）查询操作

        1. 查询头尾结点的时间复杂度是O(1)。

        2. 平均的查询时间复杂度是O(n)。

        3. 给定节点找前驱节点的时间复杂度为O(1)。

（2）插入、删除操作

        1. 头尾结点增删的时间复杂度为O(1)。

        2. 其他部分结点增删的时间复杂度是 O(n)。

        3. 给定节点增删的时间复杂度为O(1)。

三、总结

 1.单向链表和双向链表的区别是什么？

        1.1 单向链表只有一个方向，结点只有一个后继指针 next。

        1.2 双向链表它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。

2.链表操作数据的时间复杂度是多少？

原文地址：https://blog.csdn.net/weixin_53094999/article/details/136354366

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！