单链表
我们介绍单链表这种数据结构，链表结构为基于数组的序列提供了另一种选择（例如 Python 列表）。
基于数组的序列也会有如下缺点：
- 一个动态数组的长度可能超过实际存储数组元素所需的长度
- 在实时系统中对操作的摊销边界是不可接受的
- 在一个数组内部执行插入和删除操作的代价太高
基于数组的序列和链表都能够对其中的元素保持一定的顺序，但采用的方式截然不同。
- 数组是采用一整块的内存，能够为许多元素提供存储和引用。
- 链表则是用更为分散的结构，采用称为节点的轻量级对象，分配给每一个元素。每个节点维护一个指向它的元素的引用，并含一个或多个指向相邻节点的引用。
链式结构
什么是线性表的链式存储，即采用一组任意的存储单元存放线性表的元素，这组存储元素可以是连续的，也可以是不连续的。连续的我们当然好理解，那如果不连续呢？就可以通过一条链来连接，什么是链？最直观的感受如下图：
我们知道，C 语言中有指针，指针通过地址来找到它的目标。如此说来，一个节点不仅仅有它的元素，还需要有一个它的下一个元素的地址。这两部分构成的存储结构称为节点（node），即节点包含两个域：数据域和指针域，结构的结构图如下：
Python 中的引用
那么，这里需要指针和地址，我们在学习基础的时候没听说 Python 有 C 或 C++中的指针啊，Python 中指针是什么？我们先把这个概念放一放，一提到指针可能初学 C 和 C++的人都害怕（本人也害怕），先来理解一下 Python 里面变量的本质。
>>> a = 100 >>> b = 100 >>> id(a) 4343720720 >>> id(b) 4343720720 >>> >>> a, b = 10, 20 >>> id(a) 4343717840 >>> id(b) 4343718160 >>> a, b = b, a >>> id(a) 4343718160 >>> id(b) 4343717840 >>>
- 当声明
a = 100和b = 100的时候，能发现id(a) == id(b)，为什么 a 和 b 的 id 值是一样的呢？我们来看一下这个图：
我们利用上图来打一个比喻，可能不是很准确但方便我们进行理解。如果计算机被当成是一栋楼，那么内存空间就相当楼中的每个房间，内存地址就是这个房间的门牌号，这个房间内可以存储数据（比如数字 100，数字 10 或者其他类型）。
假如有一天，来了个要租房的小 a，小 a 说：“我看中了门牌号为（内存地址 4343720720）的这个房间”，并且放心的租用了这个房，所以 a = 100。小 a 就住在了这个房间里，当我们查询 id(a)的时候，计算机就返回给我们这个房间的门牌号（也就是内存地址 4343720720）。 同理，小 b 也看中了这个房子，并且也放心的住了下来。而且因为房间里存储的数据都是 100，即使虽然 a 和 b 的名字不同，但他们住同一房间，所以内存地址就相同。
- 当声明
a = 10和b = 20的时候，情况发生了改变，这个过程其实也好理解，就是相当于小 a 和小 b 分别看中了不同的房间（小 a 看中的是门牌号 4343717840 的房间，小 b 看中的是门牌号 4343718160），当他们住下来后，这个房间存着不同数据（a=10, b=20）。当他们进行交换的时候a, b = b, a，就相当于交换了房间，但是房间里的数据是没有变。最后a=20, b =10，因为内存地址 4343717840 存的数字就是 10，4343718160 存的数字是 20。
本来是要介绍单链表的，为什么讲到 Python 中的引用呢？因为我们要介绍的单链表这一数据结构就要利用到对象的引用 这一概念。变量本身就存储的一个地址，交换他们的值就是把自己的指向更改。Python 中没有指针，所以实际编程一般用引用来代替。这里对 Python 引用的介绍不是很详细，如果读者还是不明白，可以通过其他的资料进行深入了解。
节点定义与 Python 代码实现
节点，用于构建单链表的一部分，有两个成员：元素成员、指针域成员。
元素成员：引用一个任意的对象，该对象是序列中的一个元素，下图中的 a1、a2、…、an
指针域成员：指向单链表的后继节点，如果没有后继节点，则为空。
熟悉完链式结构，我们就能很好的写出节点的 Python 代码了。
class Node(object): """声明节点""" def __init__(self, element): self.element = element # 给定一个元素 self.next = None # 初始设置下一节点为空
那么，什么是单链表
单链表 最简单的形式就是由多个节点的集合共同构成一个线性序列。每个节点存储一个对象的引用，这个引用指向序列中的一个元素，即存储指向列表的下一个节点。
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
其实，上面的术语用生活中的大白话来解释，就是我们现在有三个人——我、你、他。当我用手指指向你（注意：因为是单链表，所以你不能指向我），你用手指指向他，这样就形成了一个单链表。手指就是一个引用，而“我、你、他”就是序列中的元素。“我->你->他”方式就是一个简单单链表，不知道你理解了没有？
- 头结点：链表的第一个节点
- 尾节点：链表的最后一个节点 从头节点开始，通过每个节点的“next”引用，可以从一个节点移动到另一个节点，从而最终到达列表的尾节点。 若当前节点的“next”引用指向空时，我们可以确定该节点为尾节点。这一过程，我们通常叫做
遍历链表。
单链表有哪些操作
链表的操作并不是很难，只要明白节点的结构：数据域 element 和指针域 next。而各种操作其实就是对指针的操作，不论是增删改查，都是先找指针，再取元素。具体有哪些基础操作是我实现的呢？如下（当然，还有更多的操作可能使我没想到的，希望你能在评论中提出来。）
增
- 头插法
- 尾插法
- 指定位置将元素插入
删
- 删除头结点
- 删除尾节点
- 删除指定元素
改
- 修改指定位置上的元素
查
- 遍历整个单链表
- 查询指定元素是否存在
其他操作
- 链表判空
- 求链表长度
- 反转整个链表（面试高频考点）
Python 实现单链表的上述操作
# -*- coding: utf-8 -*- # @Author : yuzhou1su # @File : singly_linked_list.py # @Software : PyCharm class Node(object): """声明节点""" def __init__(self, element): self.element = element # 给定一个元素 self.next = None # 初始设置下一节点为空 class Singly_linked_list: """Python实现单链表""" def __init__(self): self.__head = None # head设置为私有属性，禁止外部访问 def is_empty(self): """判断链表是否为空""" return self.__head is None def length(self): """返回链表长度""" cur = self.__head # cur游标，用来移动遍历节点 count = 0 # count记录节点数量 while cur is not None: count += 1 cur = cur.next return count def travel_list(self): """遍历整个链表，打印每个节点的数据""" cur = self.__head while cur is not None: print(cur.element, end=" ") cur = cur.next print("\n") def insert_head(self, element): """头插法：在单链表头部插入一个节点""" newest = Node(element) # 创建一个新节点 if self.__head is not None: # 如果初始不为空，就将新节点的"next"指针指向head newest.next = self.__head self.__head = newest # 把新节点设置为head def insert_tail(self, element): """尾插法：在单链表尾部增加一个节点""" if self.__head is None: self.insert_head(element) # 如果这是第一个节点，调用insert_head函数 else: cur = self.__head while cur.next is not None: # 遍历到最后一个节点 cur = cur.next cur.next = Node(element) # 创建新节点并连接到最后 def insert(self, pos, element): """指定位置插入元素""" # 如果位置在0或者之前，调用头插法 if pos < 0: self.insert_head(element) # 如果位置在原链表长度之后，调用尾插法 elif pos > self.length() - 1: self.insert_tail(element) else: cur = self.__head count = 0 while count < pos - 1: count += 1 cur = cur.next newest = Node(element) newest.next = cur.next cur.next = newest def delete_head(self): """删除头结点""" cur = self.__head if self.__head is not None: self.__head = self.__head.next cur.next = None return cur def delete_tail(self): """删除尾节点""" cur = self.__head if self.__head is not None: if self.__head.next is None: # 如果头结点是唯一的节点 self.__head = None else: while cur.next.next is not None: cur = cur.next cur.next, cur = (None, cur.next) return cur def remove(self, element): """删除指定元素""" cur, prev = self.__head, None while cur is not None: if cur.element == element: if cur == self.__head: # 如果该节点是头结点 self.__head = cur.next else: prev.next = cur.next break else: prev, cur = cur, cur.next return cur.element def modify(self, pos, element): """修改指定位置的元素""" cur = self.__head if pos < 0 or pos > self.length(): return False for i in range(pos - 1): cur = cur.next cur.element = element return cur def search(self, element): """查找节点是否存在""" cur = self.__head while cur: if cur.element == element: return True else: cur = cur.next return False def reverse_list(self): """反转整个链表""" cur, prev = self.__head, None while cur: cur.next, prev, cur = prev, cur, cur.next self.__head = prev def main(): List1 = Singly_linked_list() print("链表是否为空", List1.is_empty()) List1.insert_head(1) List1.insert_head(2) List1.insert_tail(3) List1.insert_tail(4) List1.insert_tail(5) length_of_list1 = List1.length() print("插入节点后，List1 的长度为：", length_of_list1) print("遍历并打印整个链表: ") List1.travel_list() print("反转整个链表: ") List1.reverse_list() List1.travel_list() print("删除头节点: ") List1.delete_head() List1.travel_list() print("删除尾节点: ") List1.delete_tail() List1.travel_list() print("在第二个位置插入5: ") List1.insert(1, 5) List1.travel_list() print("在第-1个位置插入100：") List1.insert(-1, 100) List1.travel_list() print("在第100个位置插入2：") List1.insert(100, 2) List1.travel_list() print("删除元素5：") print(List1.remove(5)) List1.travel_list() print("修改第5个位置的元素为7: ") List1.modify(5, 7) List1.travel_list() print("查找元素1:") print(List1.search(1)) if __name__ == "__main__": main()
输出的测试结果
链表是否为空 True 插入节点后，List1 的长度为： 5 遍历并打印整个链表: 2 1 3 4 5 反转整个链表: 5 4 3 1 2 删除头节点: 4 3 1 2 删除尾节点: 4 3 1 在第二个位置插入5: 4 5 3 1 在第-1个位置插入100： 100 4 5 3 1 在第100个位置插入2： 100 4 5 3 1 2 删除元素5： 5 100 4 3 1 2 修改第5个位置的元素为7: 100 4 3 1 7 查找元素1: True
总结
在我们对这些基础操作熟练之后，我推荐的学习方法就是对网上（比如 LeetCode）上与单链表相关的习题进行练习。
