数据结构系列之链表

3
1,592次阅读

A+

所属分类：数据结构

链表不是一块连续的空间，它是通过“指针”将一组零散的内存块串联起来使用。

我们来看看链表与数组的差异

很明显，数组在内存中是一连串相邻的区域组成的，而链表则是由不连续的指针而组成的。

链表的分类

链表分为最常见的三种类型：单链表、循环链表和双向链表。

单链表

单链表如图所示，除了data中存储数据结构以外，还有一个next元素，为指向下一个节点内存地址的后继指针。单链表有两个特殊节点，一个是头节点，一般可以使用头节点循环遍历整个单链表。一个是尾节点，尾节点属于单链表的最后一个节点，所以一般为null。

单链表的插入和删除

数组在插入与删除操作时(由于是一连串的内存地址)需要进行一些列的搬迁工作，所以效率很低，时间复杂度为O(n)但是链表的插入和操作，只需要更改相邻节点的指针，时间复杂度为O(1)，所以很高效。

循环链表

循环链表其实是一个特殊的单链表，它与单链表的区别就是尾节点，我们知道单链表的尾节点为null，而循环链表的尾节点对应链表的头节点，形成了一个循环的状态，所以称为循环链表。

双向链表

它有两个方向的指针，分别是前驱指针指向前一个节点，与后继指针指向后面一个节点。

双向链表由于多一个指针用来指向前一个节点，所以势必会在空间上比单链表占用更多内存，但是双向链表可以支持在O(1)复杂度下找到前驱节点，所以在某种情况下，删除与插入比单链表更加高效，简单。

双向循环链表

顾名思义就是双向链表的循环版本，尾节点的next指针指向头节点的data元素，头节点的前驱节点prev指向尾节点的data元素。

链表与数组的性能对比

如上图

数组由于是一连串的内存空间，所以在进行元素插入和删除时，往往会进行数据搬移工作，这样就会造成性能上的损耗，所以时间复杂度为O(n)，而数组在访问某一个元素时，可以通过下标位置访问元素单元，不需要进行循环查找，所以时间复杂度为O(1)。

链表在是一连串不连续的内存空，在元素插入和删除时，可以通过元素的前驱节点或者后继节点直接查询到元素的所在位置，可以通过更改元素的前驱节点或者后续节点的指针指向，所以时间消耗几乎很小，对性能影响微乎其微，所以时间复杂度为O(1)，而在查找元素时恰恰与数组相反，链表需要通过头节点，依次遍历所有节点查找元素，故时间复杂度为O(n)。

所以，在项目中，要根据场景的不同，择优选择是使用数组还是链表。

如何写好正确的链表代码？

一、理解指针或引用

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

例如： p -> next = q 这段代码的意思就是 p节点中的next指针存储了q节点的内存地址。
p -> next = p -> next -> next 这段代码的意思就是 p节点的next指针存储了p节点的下下一个节点的内存地址。

二、警惕指针丢失和泄露

插入节点时，要注意操作的顺序

删除节点时，要手动释放内存空间

三、利用哨兵简化难度

哨兵节点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵节点，把这种带有哨兵节点的链表叫做带头链表。相反，没有哨兵节点的链表叫做不带头链表。