如何不再被「单链表」面试题虐得男默女泪？
作者 | Rocky0429
责编 | 胡巍巍
写在之前
在程序设计里，我们经常需要将同为某个类型的一组数据元素作为一个整体来使用，需要创建这种元素组，用变量来记录它们或者传入函数等等等等。
「线性表」就是这样一组元素的抽象，它是某类元素的集合并且记录着元素之间一种顺序关系，是最基本的数据结构之一，在实际程序中运用非常广泛，比如 Python 中的 list 和 tuple 都可以看作是线性表的实现。
基于各种实际操作等方面的综合考虑，我们提出了两种实现线性表的形式：「顺序表」和「链表」。
「顺序表」是将表中的元素顺序存放在一大块连续的存储区间里，所以在这里元素间的顺序是由它们的存储顺序来表示的。
「链表」则是将表中元素存放在一系列的结点中（结点的存储位置可以是连续的，可以是不连续的，也就意味着它们可以存在任何内存未被占用的位置），这些结点通过连接构造起来，结点分为「数据域」和「指针域」。
这次我们要学习的「单链表」就是「链表」的一种实现形式，「数据域」保存着作为表元素的数据项，「指针域」保存同一个表里的下一个结点的标识。
在正式说「单链表」之前，我先来说一下很多人在学习链表之初都傻傻分不清的两个东西：「头结点」和「头指针」。
「头结点」的设立是为了操作的统一和方便，是放在第一个元素的节点之前，它的数据域一般没有意义，并且它本身也不是链表必须要带的。
那设立头节点的目的是什么呢？其实就是为了在某些时候可以更方便地对链表进行操作，有了头结点，我们在对第一个元素前插入或者删除结点的时候，它的操作与其它结点的操作就统一了。
「头指针」顾名思义，是指向链表第一个结点的指针，如果有头结点的话，那么就是指向头结点的指针。
它是链表的必备元素且无论链表是否为空，头指针都不能为空，因为在访问链表的时候你总得知道它在什么位置，这样才能通过它的指针域找到下一个结点的位置。
也就是说知道了头指针，整个链表的元素我们都是可以访问的，所以它必须要存在，这也就是我们常说的「标识」，这也就是为什么我们一般用头指针来表示链表。
单链表
N 个结点链接成一个链表，这也就是平时书上所说的「链式存储结构」，因为这个链表中的每个结点中只包含一个指针域，所以又叫「单链表」。
单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。单链表的第一个结点的存储位置叫做「头指针」，最后一个结点的指针为「空」，一般用 “^” 表示。
上图是不带头结点的单链表，下面我们来看一下带头结点的单链表：
还有一种是空链表：
通过上面 3 个图我们发现无论单链表是否为空，是否有头结点，头指针都是存在的，这就很好的印证了之前我们所说的「头指针是链表的必备元素且无论链表是否为空，头指针都不能为空」。
为了方便后续的操作，我们一般会先定义一个简单的结点类：
class Node(object):
def __init__(self,data):
self.data = data
self.next = None
单链表的基本操作
首先我们先来创建一个链表类：
class LinkList(object):
def __init__(self):
self.head = Node(None)
# 判断链表是否为空
def IsEmpty(self):
p = self.head # 头指针
if p.next == None:
print("List is Empty")
return True
return False
# 打印链表
def PrintList(self):
if self.IsEmpty():
return False
p = self.head
while p:
print(p.data,end=' ')
p = p.next
1.创建单链表
创建单链表的过程其实就是一个动态生成链表的过程，说简单点就是从一个「空链表」开始，依次建立各个元素的结点，并把它们逐个插入链表，时间复杂度为 O(n)：
def InitList(self,data):
self.head = Node(data[0]) # 头结点
p = self.head # 头指针
for i in data[1:]:
node = Node(i)
p.next = node
p = p.next
下面我们来测试一下：
# test
lst = LinkList()
data = [1, 4, 5, 8, 2, 3]
lst.InitList(data)
lst.PrintList()
输出结果如下：
1 4 5 8 2 3
2.计算单链表的长度
在使用链表的时候，经常需要求表的长度，为此我们可以创建一个球表长的函数，这个函数就是从左到右扫描，遍历表中的所有结点并完成计数，时间复杂度为 O(n)：
def LengthList(self):
if self.IsEmpty():
return 0
p = self.head
cnt = 0
while p:
cnt += 1
p = p.next
return cnt
下面我们来测试一下：
# test
lst = LinkList()
data = [1, 4, 5, 8, 2, 3]
lst.InitList(data)
print(lst.LengthList())
输出的结果如下：
6
3.单链表的插入
假设我们要将结点 s 插入到 结点 p 的后面，只需要将结点 s 插入到结点 p 和 结点 p.next 之间即可，说起来简单，那么到底如何插入呢？请看下图：
由上图我们可以看到，单链表结点的插入根本不需要惊动其它结点，只需要让 s.next 和 p.next 的指针稍作改变即可。让 p 的后继结点改为 s 的后继结点，再把 s 的后继结点变成 p 的后继结点。
这里一定要切记，插入操作的顺序不能改变，至于为什么，你可以拿起纸笔手动的画一下，结果一下子就会出来（对于单链表的表头和表尾的特殊情况，操作是相同的）。
# 单链表的插入(在第 s 个结点后面插入 data)
def InsertList(self,s,data):
if self.IsEmpty() or s < 0 or s > self.LengthList():
print("Insert failed！")
return
p = self.head
index = 1
while index < s:
p = p.next
index += 1
node = Node(data)
node.next = p.next
p.next = node
下面我们来测试一下：
# test
lst = LinkList()
data = [1, 4, 5, 8, 2, 3]
lst.InitList(data)
lst.InsertList(0,666)
lst.PrintList()
输出的结果如下：
1 666 4 5 8 2 3
4.单链表删除
看完插入，我们现在再来看看单链表的删除。假设我们想要删除一个结点 q，其实就是将它的前继结点 p 的指针绕过 q，直接指向 q 的后继结点即可，具体操作如下图所示：
由上图可以看出，我们只需要一步就可以实现删除操作，那就是让 p.next 直接为 p 的 next 的 next，p 的 next 为 q，所以也就是 p.next = q.next，时间复杂度为 O(n)。
# 单链表的删除(删除第 s 个结点)
def DeleteList(self, s):
if self.IsEmpty() or s < 0 or s > self.LengthList():
print("Delete failed! ")
return
p = self.head
index = 1
while index < s:
pre = p
index += 1
p = p.next
pre.next = p.next
p = None
由 p = None 可以看出，在 Python 中，只需要简单的将指针赋值为 None，就抛弃了链表原有的结点，Python 解释器的存储管理系统会自动回收不用的存储。
下面我们来测试一下：
# test
lst = LinkList()
data = [1, 4, 5, 8, 2, 3]
lst.InitList(data)
lst.DeleteList(3)
lst.PrintList()
输出的结果如下：
1 4 8 2 3
5.单链表的读取
在顺序结构中，我们想要获取任意一个元素的存储位置是很容易的，但是在单链表中，第 i 个元素到底在哪我们一开始没办法知道，只能傻傻地从头开始找，所以在对于单链表获取第 i 个元素的操作，算法上相对麻烦一些。
# 单链表的读取（获取第 s 个结点的值）
def GetList(self, s):
if self.IsEmpty() or s < 0 or s > self.LengthList():
print("Read failed! ")
return
p = self.head
index = 1
while index < s:
index += 1
p = p.next
print("第 {} 个值为 {}".format(s, p.data))
从上面的代码我们可以很清楚地看出，单链表获取第 i 个元素就是从头开始找，知道第 i 个元素为止，所以我们可以很容易地估算出它的时间复杂度是 O(n)。
任何事物都不是完美的，有好的地方就有坏的地方，元素的读取就是单链表美中不足的地方之一。
写在之后
单链表的操作其实还有不少，我只是写了其中常用的几种，希望大家能自己动手尝试一下，把这几个搞懂搞透。
碰到这样的问题从哪个方面去思考，如何去做才是最重要的，只有学会了这些，你在日后碰到相关问题的时候就知道如何去下手。
我在上面每个操作的讲解中大多数给出了图，通过图来看解法题目了然。算法这个东西其实就是这样，多动手实现以下，想不明白了就动手画一下，画着画着思路就出来了。
最后我们就来总结一下链表操作的时间复杂度。
创建空表 O(1)；
创建单链表 O(n)；
插入元素：首端插入为 O(1)；尾端插入为 O(n)，因为还要找到表的最后结点；定位插入 为O(n)；
删除元素：首端删除为 O(1)；尾端删除为 O(n)，理由如上；定位删除为 O(n)。
以下是上述所有操作的代码汇总：
# 结点类
class Node(object):
def __init__(self,data):
self.data = data
self.next = None
# 链表类
class LinkList(object):
def __init__(self):
self.head = Node(None)
# 判断链表是否为空
def IsEmpty(self):
p = self.head # 头指针
if p.next == None:
print("List is Empty")
return True
return False
# 打印链表
def PrintList(self):
if self.IsEmpty():
return False
p = self.head
while p:
print(p.data,end= ' ')
p = p.next
# 创建单链表
def InitList(self,data):
self.head = Node(data[0]) # 头结点
p = self.head # 头指针
for i in data[1:]:
node = Node(i)
p.next = node
p = p.next
# 单链表的长度
def LengthList(self):
if self.IsEmpty():
return 0
p = self.head
cnt = 0
while p:
cnt += 1
p = p.next
return cnt
# 单链表的插入(在第 s 个结点后面插入 data)
def InsertList(self,s,data):
if self.IsEmpty() or s < 0 or s > self.LengthList():
print("Insert failed！")
return
p = self.head
index = 1
while index < s:
p = p.next
index += 1
node = Node(data)
node.next = p.next
p.next = node
# 单链表的删除(删除第 s 个结点)
def DeleteList(self, s):
if self.IsEmpty() or s < 0 or s > self.LengthList():
print("Delete failed! ")
return
p = self.head
index = 1
while index < s:
pre = p
index += 1
p = p.next
pre.next = p.next
p = None
# 单链表的读取（获取第 s 个结点的值）
def GetList(self, s):
if self.IsEmpty() or s < 0 or s > self.LengthList():
print("Read failed! ")
return
p = self.head
index = 1
while index < s:
index += 1
p = p.next
print("第 {} 个值为 {}".format(s, p.data))
作者：华东师范大学研一学生，ACM ICPC 亚洲区域赛银奖/铜奖获得者，CCPC 首届中国大学生程序设计竞赛银奖，ACM山东省大学生程序设计竞赛金奖。喜欢 Python & 算法。
推荐阅读：