基础知识--线性表

线性表

线性表是⼀对⼀的逻辑结构，线性表中除了表头元素每个元素有且仅有唯⼀⼀个前驱元素，除了表尾元素，每个结点都有唯⼀⼀个后继节点。

顺序表随机存取，存取某个元素的时间复杂度为O(1)。

平均时间复杂度O(n)

平均时间复杂度O(n)，删除插⼊元素需要移动⼤量元素。（如果是删除最后⼀个元素或者在最后⼀个节点后⾯插⼊⼀个新的节点，则复杂度为O(1)，因为不需要移动元素）

链表因其链状的结构，能方便地删除、插入数据，操作次数是 O(1)。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 O(n)。

单链表的基本组成单元是节点 (Node)。每个节点通常包含两个主要部分：

数据域 (Data): 用于存储实际的数据元素。数据域可以是任何数据类型，例如整数、浮点数、字符、字符串，甚至更复杂的数据结构。
指针域 (Pointer) 或下一个节点指针 (Next Pointer): 用于存储指向链表中下一个节点的地址（或引用）。对于单链表，每个节点只有一个指针，指向它后面的节点。链表的最后一个节点的指针域通常指向一个特殊值，表示链表的末尾，这个特殊值通常是 空指针 (NULL 或 None)。

**头插法：**每次在链表头结点后⾯插⼊新的结点。头插法的元素顺序与插⼊顺序相反，类似于栈。

**尾插法：**每次在链表的尾结点插⼊新的结点，并且是尾结点更新（使尾指针指向新的尾结点）。尾插法得到的顺序与插⼊顺序相同，类似于队列。

查找方式是线性的，平均和最坏情况下的时间复杂度均为 O(n)，其中 n 是链表中的节点数。

插入删除

在链表中插入或删除节点，通常只需要修改指针的指向，而不需要像数组那样移动大量的元素（特别是插入和删除中间位置的元素时）。时间复杂度通常为 O(1) (在已知插入/删除位置的前驱节点的情况下)。

访问效率较低: 要访问链表中的某个特定节点，必须从头节点开始顺序遍历，直到找到目标节点。无法像数组那样通过索引直接访问，访问时间复杂度为 O(n)，其中 n 是链表的长度。
存储开销: 每个节点除了存储数据外，还需要额外的空间存储指针，增加了存储开销。
不适合随机访问: 由于只能顺序访问，链表不适合需要频繁随机访问的应用场景。

双链表的节点 (Node) 结构在单链表的基础上增加了一个前驱指针：

前驱指针域 (Previous Pointer): 存储指向链表中前一个节点的地址（或引用）。链表的头节点 (Head) 的前驱指针通常指向一个特殊值，表示链表头部，这个值通常是 空指针 (NULL 或 None)。
数据域 (Data): 与单链表相同，用于存储数据元素。
后继指针域 (Next Pointer): 与单链表相同，存储指向链表中下一个节点的地址（或引用）。链表的尾节点 (Tail) 的后继指针通常指向一个特殊值，表示链表尾部，这个值通常是 空指针 (NULL 或 None)。

创建一个空的双链表，通常将头指针和尾指针都初始化为 NULL。

与单链表类似，双链表的查找也是线性的，时间复杂度为 O(n)。

双向遍历: 可以从头到尾，也可以从尾到头双向遍历，提高了数据访问的灵活性。
删除节点更高效: 删除节点时，特别是删除中间节点和尾节点时，由于有前驱指针，可以更方便地找到前一个节点，无需像单链表那样需要从头开始遍历找到前驱节点。这在某些情况下可以提高删除操作的效率。
某些操作更方便: 例如，在已知节点指针的情况下，插入和删除操作更加直接，不需要总是从头开始查找前驱节点。