本文共 16488 字，大约阅读时间需要 54 分钟。
目录
链表
链表是由许多数据项按特定顺序排列而成的线性表。链表的特性是其各个数据项在计算机内存中的位置是不连续且随机存放的。其优点是数据的插入和删除都相当方便，有新数据加入就向系统申请一块内存空间，而数据被删除后，就可以把这块内存空间还给系统，加入和删除都不需要移动大量数据。其缺点是设计数据结构较为麻烦，另外在查找数据时，无法像列表、元组等静态数据结构那样可随机读取数据，必须按序查找到该数据为止。
单向链表
在动态分配内存空间时，最常使用的就是单向链表。一个单向链表节点由两部分组成，一部分是数据元素（数据元素可以是多个），另一部分是指针。数据元素保存业务数据，指针指向下一个元素在内存中的地址。在单向链表中，第一个节点表示头节点。头节点可以不用来保存业务数据，仅仅用来作为链表的表头，最后一个节点的指针为None。
由于单向链表中的所有节点都知道节点本身的下一个节点在哪里，但是对于前一个节点却没有办法知道，因此在单向链表的各种操作中，“链表表头”显得相当重要。只要存在链表头，就可以遍历、操作整个链表。除非必要，否则不可移动链表表头。
建立单向链表
创建单向链表节点
class Node(object): def __init__(self, value): self.value = value self.next = None
每一个单向链表节点就是Node类的一个实例化对象。其中value表示节点的数据部分，根据实际业务数据部分可以是多个，数据类型也是根据实际业务来定。next表示节点的下一个指向节点，默认是空。
头节点
前面说过，单向链表的操作都依赖于头节点，因此找到了头节点就相当于找到了该单向链表。头节点本身的数据结构于其他节点并没有什么区别，它们都是Node类实例化出来的对象。在通常的使用中，为了操作方便和简化，可以将头节点视为单向链表的操作对象，而不是作为存储业务数据的一个节点，即头节点head的数据部分不存储任何值，仅仅指向下一个节点（可以理解为头节点就是火车的车头，车头不会搭载乘客，仅仅是为了控制火车）。
一个链表有且只有一个头节点和0个或多个数据节点，当链表只存在一个头节点而不存在任何数据节点时，该链表是一个空链表（即头节点的next值为None）。
创建单向链表
总结完上面的知识，我们可以创建一个单向链表了。创建一个单向链表本质上就是创建一个头节点。
class LinkedList(object): def __init__(self): self.head = Node("head") 通过对LinkedList类实例化得到一个空的单向链表：我们在向上封装一层函数，用来创建一个空的单向链表：
def create() -> LinkedList: return LinkedList()
链表是否为空
如果一个链表只存在头节点，我们认为该链表是一个空链表。在LinkedList类中定义一个方法empty()，用来判断链表是否为空：
class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None
添加元素
连接两个节点
链表是由若干个节点连接而成的。给列表中添加元素最基本的功能就是连接两个节点。对于两个节点A，B，我们将A.next = B即将A的下一个节点指向了B，也就是说B节点成为了A的下一个节点。
A.next = B
我们在节点Node类里重写__add__方法来连接两个链表，简化代码：
class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_node
重写__add__方法后两个节点的连接语法被我们简化了：
a = Node("A")b = Node("B")a + b 即直接使用 “+”运算符即可连接两个节点。a + b表示将b节点作为a节点的下一个节点。
插入单个节点
通常便捷的插入方式是将新的节点插入到头节点的下一个位置。如果链表只有头节点，那么将新插入的节点作为头节点的下一个节点即可。如果链表有多个节点，那么需要将头节点的下一个节点指向新节点，同时新节点的下一个节点指向插入前头节点的下一个节点。即：
链表只存在头节点：
插入前，头指针指向None
插入后，头指针指向新节点，新节点作为链表尾部指向None：
链表存在多个节点：
插入前，链表头指针指向着其他节点：
插入后，头指针指向新节点，新节点指向Node1：
下面我们使用代码来实现上面的逻辑图：
linked = create() # linked list only has head node newNode = Node("Python") linked.head.next = newNode # head -> Python -> [None] newNode = Node("C") ptr = linked.head.next linked.head.next = newNode newNode.next = ptr
根据上面的逻辑，我们在LinkedList类中封装一个add方法用来表示添加新的节点：
class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def add(self, node): if self.empty(): self.head + node else: ptr = self.head.next self.head + node node + ptr
将节点插入到链表末尾
有时候需要将新插入的节点放入链表的尾部，而不是除头节点外的第一个位置。这时只需要顺着头节点依次遍历链表，找到链表的最后一个节点，即尾节点。将尾节点的下一个节点指向新节点即可。我们在LinkedList类中定义一个append()方法用来将节点插入到链表末尾。
class LinkedList(object): def __init__(self): self.head = Node("head") # 此处省略部分无关的代码 def append(self, node): point = self.head while point.next is not None: point = point.next point + node
插入一个元素到指定索引
我们使用图解的方式展示插入一个元素到指定索引的逻辑：
待新增的节点newNode要插入到链表第1个位置：
我们发现，第1个位置在Node2处。我们让Node1的next指针指向NewNode，让NewNode的next指针指向Node2，至此，链表的插入就结束了。
我们定义一个insert(index, node)方法来将newNode插入到链表中。如果index不存在，则抛出IndexError异常。关于len()函数的实现我们放到后面的章节“计算链表长度”中详细讲解。
# 部分代码已省略, 查看完整代码请阅读最后一节class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_nodeclass LinkedList(object): def __init__(self): self.head = Node("head") def insert(self, index, node: Node): if index >= len(self): raise IndexError("Linked list index out of range.") float_index = 0 ptr = self.head.next lptr = self.head while ptr is not None: if index == float_index: lptr + node node + ptr break float_index += 1 lptr = ptr ptr = ptr.next
合并其它单向链表
假设我们要将链表B合并到链表A中。我们只需要将链表A的尾节点指向链表B的第一个节点（即头节点的下一个节点）即可。
合并前的A、B两个链表：
将链表A的尾节点A-3 指向链表B的第一个节点B-1，然后释放链表B的头节点Head-B与链表B的第一个节点B-1的连接，完成链表合并：
我们在LinkedList类中定义一个方法extend来表示链表间的合并。
# 部分代码已省略，需要完整版代码请阅读文章最后一节class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def extend(self, linked_list): if linked_list.empty(): return point = self.head.next while point.next is not None: point = point.next point + linked_list.head.next return
销毁链表
只需要将链表头节点为None即可销毁链表（将链表回到create后的状态）。 我们在LinkedList类中定义一个destroy方法用来销毁链表。
# 部分代码已省略，需要完整版代码请阅读文章最后一节class LinkedList(object): def __init__(self): self.head = Node("head") def destroy(self): self.head = Node("head")
删除元素
删除链表的第一个元素
删除链表的第一个元素，只需要将头节点指向链表的第二个元素即可。要注意对链表长度的判断。我们定义方法pop来表示删除链表的第一个元素。pop有一个关键字参数reverse=False，当其为True时表示删除链表的第一个元素。
# 部分代码已省略，需要完整版代码请阅读文章最后一节class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def pop(self, reverse=False) -> Node: if self.empty(): raise IndexError("pop from empty linked list") if reverse: element = self.head.next self.head.next = element.next return element else: # TODO: pop end of linked list element pass
删除链表的最后一个元素
要删除链表的最后一个元素（尾节点），只需要将链表的倒数第二个元素的next字段指向None即可。
是时候继续完善pop()方法了。在上一个小结中，我们的pop()方法仅仅针对reverse=True（删除链表的第一个元素）的场景，现在我们要完善reverse=False的场景，表示删除链表的最后一个元素。
# 部分代码已省略，需要完整版代码请阅读文章最后一节class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def pop(self, reverse=False) -> Node: if self.empty(): raise IndexError("pop from empty linked list") if reverse: element = self.head.next self.head.next = element.next return element else: ptr = self.head.next left_ptr = self.head while ptr.next is not None: ptr = ptr.next left_ptr = left_ptr.next left_ptr.next = None return ptr
删除链表中指定值的元素
我们定义一个方法remove()，用来删除指定值的元素。与list.remove()类似，如果链表中存在多个值与要删除的值相同，那么我们只会删除最靠近头节点的那个元素。
删除链表中的某个元素，如果该元素在链表的中间，只需要将该元素的左侧节点的next指向该元素的右侧节点即可。
怎样判断某个节点与old是否相等呢？最简单的方法是用node.value 与 old.value做比较得出结论。但是当Node节点的数据域存在多个值，且构成较为复杂时，这么做就不太好判断了。比如以学生作为Node类，那么数据域就不仅仅是一个value了，有可能会带有学号id，姓名name，性别sex等等。如果要一个个比较，不仅代码量会变得非常庞大，而且不方便维护。因此我们需要在Node类中重载方法__eq__，如果随着版本的迭代，Node类新增了数据域，那么我们只需要维护__eq__即可：（重写__eq__后，我们可以直接使用Python运算符==判断两个Node实例是否相等）
class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_node def __eq__(self, other_node): return self.value == other_node.value
# 部分代码已省略，需要完整版代码请阅读文章最后一节 class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def remove(self, target: Node): if self.empty(): raise ValueError("remove from empty linked list") ptr = self.head.next left_ptr = self.head while True: if ptr == target: break if ptr.next is None: raise IndexError("value do not exist") ptr = ptr.next left_ptr = left_ptr.next if ptr.next is None: left_ptr.next = None else: left_ptr.next = ptr.next return 删除链表中指定值的全部元素
由于remove()方法一次只能删除一个匹配的元素，因此我们需要一个新的方法将所有匹配的元素删除。定义一个新的方法remove_all，将所有匹配的值删除。
# 部分代码已省略，需要完整版代码请阅读文章最后一节class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_node def __eq__(self, other_node): return self.value == other_node.value class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def remove_all(self, target: Node): if self.empty(): raise ValueError("remove from empty linked list") ptr = self.head.next left_ptr = self.head while ptr is not None: if ptr == target: if ptr.next is None: left_ptr.next = None break left_ptr.next = ptr.next ptr = left_ptr.next ptr = ptr.next left_ptr = left_ptr.next
计算链表长度
顾名思义，链表长度就是链表实际存储元素的数量。我们重写魔法函数__len__()，来计算链表长度：
# 部分代码已省略，需要完整版代码请阅读文章最后一节class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_node def __eq__(self, other_node): return self.value == other_node.valueclass LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def __len__(self): if self.empty(): return 0 ptr = self.head.next count = 0 while ptr is not None: count += 1 ptr = ptr.next return count
修改元素值
替换元素值
我们定义一个方法replace(self, old, new, num)，用于将链表中值为old的元素替换为new。链表从链表头开始遍历，直到替换num次为止。
我们需要在Node中新增一个方法用来更新数据域：
class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_node def __eq__(self, other_node): return self.value == other_node.value def update(self, other_node): self.value = other_node.value
最后是我们的主角replace方法：
# 部分代码已省略，需要完整版代码请阅读文章最后一节class LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def replace(self, old: Node, new: Node, num=1): if self.empty() or num <= 0: return ptr = self.head.next count = 0 while ptr is not None: if ptr == old: ptr.update(new) count += 1 ptr = ptr.next if count >= num: break 修改某个索引的值
我们要使链表像list一样可以指定索引修改某个值。这个索引必须在合法的链表长度范围内。除此之外，我们也可以使用负数作为索引，表示从后往前逆序顺序。我们定义一个方法set(new_value, index)，new_value表示新的数据域，index表示要替换元素的索引值。为了方便计算，我们需要对负数索引转换成正数索引来处理。当index为负数时，链表长度length + index的结果即index对应的正数索引值。
# 部分代码已省略，需要完整版代码请阅读文章最后一节class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_node def __eq__(self, other_node): return self.value == other_node.value def update(self, other_node): self.value = other_node.valueclass LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def set(self, new_value: Node, index: int): length = len(self) if index > length-1 > 0 or index < -length < 0: raise IndexError("LinkedList index out of range.") ptr = self.head.next if index < 0: index = length + index current_index = 0 while True: if index == current_index: ptr.update(new_value) break ptr = ptr.next current_index += 1 def __len__(self): if self.empty(): return 0 ptr = self.head.next count = 0 while ptr is not None: count += 1 ptr = ptr.next return count
遍历线性表
我们定义一个方法list()，将链表转换为列表。并提供一个参数reverse，当reverse为True时，将链表逆序转换。
# 部分代码已省略，需要完整版代码请阅读文章最后一节class LinkedList(object): def __init__(self): self.head = Node("head") def list(self, reverse=False): result = [] ptr = self.head while ptr.next is not None: ptr = ptr.next result.append(ptr) if reverse: result = result[::-1] return result
完整代码
class Node(object): def __init__(self, value): self.value = value self.next = None def __add__(self, other_node): self.next = other_node def __eq__(self, other_node): return self.value == other_node.value def update(self, other_node): self.value = other_node.valueclass LinkedList(object): def __init__(self): self.head = Node("head") def empty(self) -> bool: return self.head.next is None def add(self, node): if self.empty(): self.head + node else: ptr = self.head.next self.head + node node + ptr def append(self, node): point = self.head while point.next is not None: point = point.next point + node def insert(self, index, node: Node): if index >= len(self): raise IndexError("Linked list index out of range.") float_index = 0 ptr = self.head.next lptr = self.head while ptr is not None: if index == float_index: lptr + node node + ptr break float_index += 1 lptr = ptr ptr = ptr.next def extend(self, linked_list): if linked_list.empty(): return point = self.head.next while point.next is not None: point = point.next point + linked_list.head.next return def destroy(self): self.head = Node("head") def pop(self, reverse=False) -> Node: if self.empty(): raise IndexError("pop from empty linked list") if reverse: element = self.head.next self.head.next = element.next return element else: ptr = self.head.next left_ptr = self.head while ptr.next is not None: ptr = ptr.next left_ptr = left_ptr.next left_ptr.next = None return ptr def remove(self, target: Node): if self.empty(): raise ValueError("remove from empty linked list") ptr = self.head.next left_ptr = self.head while True: if ptr == target: break if ptr.next is None: raise IndexError("value do not exist") ptr = ptr.next left_ptr = left_ptr.next if ptr.next is None: left_ptr.next = None else: left_ptr.next = ptr.next return def remove_all(self, target: Node): if self.empty(): raise ValueError("remove from empty linked list") ptr = self.head.next left_ptr = self.head while ptr is not None: if ptr == target: if ptr.next is None: left_ptr.next = None break left_ptr.next = ptr.next ptr = left_ptr.next ptr = ptr.next left_ptr = left_ptr.next def replace(self, old: Node, new: Node, num=1): if self.empty() or num <= 0: return ptr = self.head.next count = 0 while ptr is not None: if ptr == old: ptr.update(new) count += 1 ptr = ptr.next if count >= num: break def set(self, new_value: Node, index: int): length = len(self) if index > length-1 > 0 or index < -length < 0: raise IndexError("LinkedList index out of range.") ptr = self.head.next if index < 0: index = length + index current_index = 0 while True: if index == current_index: ptr.update(new_value) break ptr = ptr.next current_index += 1 def __len__(self): if self.empty(): return 0 ptr = self.head.next count = 0 while ptr is not None: count += 1 ptr = ptr.next return count def list(self, reverse=False): result = [] ptr = self.head while ptr.next is not None: ptr = ptr.next result.append(ptr) if reverse: result = result[::-1] return result def print(self): result = [data.value for data in self.list()] print(result)def create() -> LinkedList: return LinkedList()
转载地址：http://udsoi.baihongyu.com/