上QQ阅读APP看书，第一时间看更新
4.2.1 什么是链表
链式存储结构不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的次序关系。所以它不要求逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无须移动元素，从而提高了运行效率。链式存储结构主要有单链表、循环链表、双向链表、静态链表等几种形式。
顾名思义，链表就像锁链一样，由一节一节的节点连在一起，组成一条数据链。链表的节点结构如图4-4所示。其中，data表示自定义的数据，next表示下一个节点的地址。链表的结构为：head保存首节点的地址，如图4-5所示。
图4-4 链表的节点结构
图4-5 链表的结构
使用Python语言实现链表的基本流程如下所示。
（1）定义节点类Node，代码如下所示。
class Node:
'''
data: 节点保存的数据
_next: 保存下一个节点对象
'''
def __init__(self, data, pnext=None):
self.data = data
self._next = pnext
def __repr__(self):
'''
用来定义Node的字符输出，
print用于输出data
'''
return str(self.data)
（2）定义链表操作类，例如链表头属性head，链表长度属性length。通过如下方法isEmpty()判断链表是否为空。
def isEmpty(self):
return (self.length == 0
（3）使用如下方法append()在链表末尾增加一个节点。
def append(self, dataOrNode):
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if not self.head:
self.head = item
self.length += 1
else:
node = self.head
while node._next:
node = node._next
node._next = item
self.length += 1
（4）通过如下方法delete()删除一个节点。
def delete(self, index):
if self.isEmpty():
print("this chain table is empty.")
return
if index < 0 or index >= self.length:
print('error: out of index')
return
if index == 0:
self.head = self.head._next
self.length -= 1
return
j = 0
node = self.head
prev = self.head
while node._next and j < index:
prev = node
node = node._next
j += 1
if j == index:
prev._next = node._next
self.length -= 1
（5）通过如下方法update()修改一个节点。
def update(self, index, data):
if self.isEmpty() or index < 0 or index >= self.length:
print 'error: out of index'
return
j = 0
node = self.head
while node._next and j < index:
node = node._next
j += 1
if j == index:
node.data = data
（6）通过如下方法getItem()查找一个节点。
def getItem(self, index):
if self.isEmpty() or index < 0 or index >= self.length:
print("error: out of index")
return
j = 0
node = self.head
while node._next and j < index:
node = node._next
j += 1
return node.data
（7）通过如下方法getIndex()查找一个节点的索引。
def getIndex(self, data):
j = 0
if self.isEmpty():
print("this chain table is empty")
return
node = self.head
while node:
if node.data == data:
return j
node = node._next
j += 1
if j == self.length:
print("%s not found" % str(data))
return
（8）通过如下方法insert()插入一个新的节点。
def insert(self, index, dataOrNode):
if self.isEmpty():
print("this chain tabale is empty")
return
if index < 0 or index >= self.length:
print("error: out of index")
return
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if index == 0:
item._next = self.head
self.head = item
self.length += 1
return
j = 0
node = self.head
prev = self.head
while node._next and j < index:
prev = node
node = node._next
j += 1
if j == index:
item._next = node
prev._next = item
self.length += 1
（9）通过如下方法clear()清空链表。
def clear(self):
self.head = None
self.length = 0