【20230205】链表小结

article/2025/8/25 14:21:45

链表（list）

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null，链表的入口节点称为链表的头节点head。

链表的类型：单链表、双链表、循环链表

单链表的指针域只能指向节点的下一个节点。双链表：每个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

循环链表：链表首尾相连，可以用来解决约瑟夫环问题。

链表的存储方式：

数组在内存中是连续分布的，但链表在内存中不是连续分布的。

链表是通过指针域的指针链接在内存中的各个节点，所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

链表的操作

1、删除节点

只要将C节点的next指针指向E节点即可。最好再手动释放D节点。

2、添加节点

链表的添加和删除都是O（1）操作，也不会影响到其他节点。

但是如果要删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度为O（n）。

性能分析

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

list是一个环状的双向链表，同时它也满足STL对于前闭后开的原则，即在链表尾端可以加上空白节点。

list的迭代器设计：

迭代器是泛化的指针，所以里面重载了-> -- ++ * () 等运算符，同时迭代器是算法与容器之间的桥梁，算法需要了解容器的方方面面，于是就诞生了5种关联类型。我们知道算法传入的是迭代器或者指针，算法根据传入的迭代器或指针推断出算法所想要了解的容器里的5种关联类型的相关信息。由于光传入指针，算法推断不出来其想要的信息，所以我们需要一个中间商（萃取器），也就是iterator traits类，对于一般的迭代器，它直接提供迭代器里的关联类型值，而对于指针和常量指针，它采用的类模板偏特化，从而提供其所需要的关联类型的值。