导语：技术连载：数据结构 - 链表

数组与链表是数据结构最基础的两种，其他的诸如hash表、树、队列、栈等都是基于这两种数据结构实现，上面两篇文章介绍了数组的特性及相关的面试题，下面介绍链表；

结点

链表是由结点构成的，所以先看看链表的结点结构是怎么样的；

结点由两部分构成，一部分是结点所存储的数据，另一部分是结点相关联的结点的指针，java程序员可以理解为引用。

这里的引用可能是一个，也可能是两个，如果是一个则指向后面的结点，如果是两个则分别指向后面的和前面的结点；

链表也是一种线性表；

链表的特点

跟数组相比，链表具有如下特点（从存储与访问角度分析）：

链表不需要连续内存，整体来讲对内存比较友好；需要额外存储节点引用，但一般来讲当数据大小远大于引用的大小（一般是int型）时，这种额外开销并不算大；根据某个结点可以直接访问到其后继结点或前继结点（双向链表）虽然时线性表，结点之间也是有顺序的，但是根据位置访问元素时间复杂度很高；链表是由多个结点构成，但一般只存储头结点或者头尾结点，元素不支持随机访问，只能顺序遍历访问。通常来讲链表的插入和删除比数组高效，但也得分情况，后面详细讨论。

链表的常规操作

查找元素

查找第K个元素，时间复杂度为O(n); 只能从头开始遍历查找

插入元素

在某个元素A之后插入一个元素B，时间复杂度为O(1)；伪代码如下：

单链表：

B.next = A.next

A.next = B

双向链表：

A.next.pre = B //需要判断A.next!=null

B.next = A.next

B.pre = A

A.next = B

删除元素

删除元素A后面的元素，伪代码如下：

单向链表：

A.next = A.next.next //需要判断A.next!=null

双向链表：

A.next.next.pre = A

A.next = A.next.next

上面提到的插入删除元素的时间复杂度为O(1)时在特定条件下，假如换一个条件，比如单链表删除A结点，但并不知道A结点前面的结点，所以需要先查找指向A的结点，然后才能删除，这样时间复杂度就为O(n);

通常来讲，双向链表更有利于在比较广的适用条件下进行插入删除操作，比如删除A元素，很容易得到A前面的元素与后面的元素，删除操作时间复杂度O(1)

循环链表

循环链表是一种比较特殊的链表，普通链表的尾结点的next指向null，而循环链表指向的是头结点，关于循环链表的判断在下一篇的“链表相关面试题”中讲解

链表操作注意事项

链表虽然并不复杂，但是链表相关的代码非常容易出错，所以对于手写链表的编程题一般侧重考察面试者的逻辑思维能力与严谨性。

下面总结几个易错点：

空指针的判断

涉及到任何一个结点都需要考虑其是否为空结点，或者其next是否为空结点

指针丢失

要修改某个指针时，需要考虑这个指针的当前值是否会被用到，如果是，则应该先保留下来再修改；

指针错误

由于逻辑不严谨，导致指针所指向的值不是自己以为的值。多写，多练；培养严谨的思维。

下一篇会收集常见的链表编程题，分享给大家；

技术连载：开篇词

技术连载：连载提纲设计思路

技术连载：数据结构 - 数组

技术连载：数据结构 - 数组常见面试题汇总

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请与我联系，一经查实立刻删除内容。本文内容由快快网络小纳创作整理编辑！