数据结构与算法 | 链表（Linked List）

链表（Linked List）是一种线性数据结构，它由一系列节点（Node）组成，每个节点包含两部分：数据和指向下（上）一个节点的引用（或指针）。链表中的节点按照线性顺序连接在一起（相邻节点不需要存储在连续内存位置），不像数组一样存储在连续的内存位置。链表通常由头节点（Head）来表示整个链表，而尾节点的下一个节点指向null，表示链表的结束。

链表有几种常见的类型，其中最常见的包括单链表、双链表。

代码语言：java复制

 // Java LinkedList 中Node的结构
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;

        }
}

基本概念

链表基本结构是节点，节点一般包含数据和指向节点的指针；节点只有指向下一个节点指针的叫单链表（Singly Linked List），有指向上一个节点的指针的叫双链表（Doubly Linked List）。

链表的一些关键特点：

节点（Node）：链表的基本构建块是节点，每个节点包含两(三)部分，即数据 element 和指向下一个节点的指针 next（指向上一个节点的指针 prev）。
单链表（Singly Linked List）：单链表中每个节点只有一个指针，即指向下一个节点的指针。
双链表（Doubly Linked List）：双链表中每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点，使得可以双向遍历链表。
头节点（Head）：链表的头节点是链表的第一个节点，用于标识整个链表的起始位置。
尾节点（Tail）：链表的尾节点是最后一个节点，其下一个节点引用通常指向null。

链表的性质：