链表

线性表

线性表（Linear List）是数据结构中的一个概念，指的是一组具有线性关系的数据元素的集合。在线性表中，元素之间只有一对一的相互关系。

线性表主要有两种存储结构：顺序存储结构和链式存储结构。

顺序存储结构：

在顺序存储结构中，线性表的元素按顺序紧密排列，通常利用数组来实现。表中的元素在内存中占据一片连续的空间，每个元素都可以通过计算得到的偏移量迅速访问。顺序存储结构简单而高效，但在插入和删除操作时可能需要移动大量元素，从而影响效率。此外，顺序存储结构通常在创建时需预分配固定大小的空间，这可能会导致空间的浪费或无法在运行时动态扩展容量。

优点

无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素

缺点

插入和删除操作需要移动大量元素
当线性表长度变化较大时，难以确定存储空间的容量
造成存储空间的碎片

链式存储结构：

链式存储结构则是通过一系列节点组成的，每个节点包含元素本身的值及一个或多个指向其他节点的指针（链表中的“链接”）。根据指针的数量和方向的不同，链式存储结构可以分为以下几类：

单链表：每个节点包含一个数据域和一个指向下一个节点的指针。
双向链表：每个节点包含一个数据域，一个指向前一个节点的指针，和一个指向下一个节点的指针。
循环链表：类似于单链表或双向链表，但是链表的最后一个节点会指向第一个节点，形成一个环。
静态链表：常常使用一维数组来描述链式结构，其中每个数组元素由数据域和指针域组成，以数组索引作为指针。

优点

动态内存分配：链式存储结构可以在运行时动态地分配内存，不需要事先声明数据结构的大小，这对于不确定数据量的应用场景非常有用。
灵活的内存使用：由于是动态分配内存，链式存储结构可以更加高效地使用内存，只分配实际需要的内存空间。
方便的元素插入和删除：在链表中插入或删除元素时，只需改变相应节点的指针即可，时间复杂度为 O(1)，相比于数组结构的插入和删除（可能需要移动大量元素），链式存储结构更加高效。
灵活的数据管理：链式存储结构可以更容易地实现各种复杂的数据结构，如链表、树和图等。

缺点

增加了内存开销：每个节点除了存储数据外，还需要存储至少一个指针，这增加了额外的内存开销。
访问时间长：与数组相比，链式存储结构的访问时间较长。数组支持随机访问，而访问链表中的元素需要从头开始遍历，时间复杂度为 O(n)。
内存碎片：动态分配内存可能会导致内存碎片的问题，影响程序的性能和效率。
指针的使用增加了错误的可能性：由于使用了指针，不当的操作可能会导致指针丢失或内存泄漏等问题。

两种存储结构各有优缺点，通常顺序存储结构适用于元素大小确定并且很少进行插入和删除操作的情况，链式存储结构适用于元素大小不确定或者需要频繁插入删除操作的情况。

单链表 (Singly Linked List)

单链表是由节点组成的数据结构，每个节点包含两部分：数据域和指针域。

数据域：存储数据元素。
指针域：存储指向下一个节点的指针。

特点:

单向性：节点的链接是单向的，每个节点只有指向下一个节点的指针。
头节点：链表有一个特殊的节点称为头节点，它用来标识链表的起始。
尾节点：链表的最后一个节点称为尾节点，它的指针指向nullptr或者链表的结束。

操作:

插入：可以在 O(1)时间内在任意节点之后插入新节点，但如果要在特定位置插入，则需要先遍历到该位置。
删除：可以在 O(1)时间内删除任意节点，前提是你有指向这个节点的指针，否则需要遍历到要删除的节点。
搜索：搜索特定值的节点通常需要 O(n)时间，因为可能需要遍历整个链表。

typescript

class SinglyListNode<T extends any> {
  private value: T;
  next: SinglyListNode<T> | null = null;

  constructor(value: T, next?: SinglyListNode<T>) {
    this.value = value;

    if (next) {
      this.next = next;
    }
  }

  getValue() {
    return this.value;
  }
}

const node1 = new SinglyListNode(1);
const node2 = new SinglyListNode(2);

node1.next = node2;

双链表 (Doubly Linked List)

双链表与单链表类似，但它的每个节点包含两个指针，一个指向前一个节点，另一个指向下一个节点。

特点:

双向性：节点之间的链接是双向的，可以很容易地访问前一个节点和后一个节点。
头尾节点：和单链表一样，双链表也有头节点和尾节点。

操作:

插入：在任意节点之前或之后插入新节点都是 O(1)的操作，但找到这个位置可能需要 O(n)的时间。
删除：在 O(1)时间内删除任意节点，但可能需要遍历来找到特定节点。
搜索：和单链表一样，可能需要 O(n)时间。

class DoublyListNode<T> {
  private value: T;
  next: DoublyListNode<T> | null = null;
  prev: DoublyListNode<T> | null = null; // 新增的前驱节点引用

  constructor(value: T, next?: DoublyListNode<T>, prev?: DoublyListNode<T>) {
    this.value = value;
    if (next) {
      this.next = next;
    }
    if (prev) {
      this.prev = prev;
    }
  }

  getValue() {
    return this.value;
  }
}

const node1 = new DoublyListNode(1);
const node2 = new DoublyListNode(2);

node1.next = node2;
node2.prev = node1; // 设置node2的前驱节点为node1

链表 ​

线性表 ​

顺序存储结构： ​

链式存储结构： ​

单链表 (Singly Linked List) ​

双链表 (Doubly Linked List) ​

链表

线性表

顺序存储结构：

链式存储结构：

单链表 (Singly Linked List)

双链表 (Doubly Linked List)