目录
- 基础 知识
1.1 链表的基本结构
1.2 节点类和链表节点的定义
1.3 顺序打印和逆序打印 - 链表的基本操作
2.1 计算链表长度
2.2 从前，后插入数据
2.3 查找与删除
参考
1.基础 知识
1.1 链表的基本结构
链表是通过一个个节点组成的，每个节点都包含了称为cargo的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。
如图：
链表的基本元素有：
- 节点：每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
- head:head节点永远指向第一个节点
- tail: tail永远指向最后一个节点
- None:链表中最后一个节点的指针域为None值
但链表也分为单向链表和单向循环链表，双向链表和双向循环链表，如图为单向链表和单向循环链表：
写个基本程序测试一下：
1.2 节点类和链表节点的定义
节点类定义如下：
class Node:
def __init__(self,cargo = None, next = None):
self.cargo = cargo
self.next = next
def __str__(self):
#测试基本功能，输出字符串
return str(self.cargo)
print Node("text")
#输出text因为任何值都能通过str函数，且能存储下来。
链表怎么定义呢？
我们可以先定义一个一个节点，如下：
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)然后再把每个节点的关系表示出来，就OK了
node1.next = node2
node2.next = node31.3 顺序打印和逆序打印
因为先前已经建立了关系，所以可以通过输入第一个节点，循环整个链表然后顺序打印整个链表。
def printList(node):
while node:
print node
node = node.next
printList(node1)
1
2
3使用递归的方法来打印，主要步骤如下：
- 将list拆分成两个部分，head:第一个元素，tail:其余元素
- 向后打印
- 打印第一个元素
def printBackward(lists):
if lists == None:
return
head = lists
tail= lists.next
print head,tail
printBackward(tail)
print head,tail
printBackward(node1)
1 2
2 3
3 None
3 None
2 3
1 2事实上，还能更简便。
def printBackward(lists):
if lists == None:return
printBackward(lists.next)
print lists
printBackward(node1)在链表的基本操作中，包括插入，删除等，但要注意的是一下的操作是针对非循环链表的，从头节点开始操作，而且我们不能插入 None值到链表中。
2.1 计算链表长度
class Node(object):
#节点类
#功能：输入一个值data，将值变为一个节点
def __init__(self, data, next = None):
self.data = data
self.next = next
def __str__(self):
return self.data
class LinkedList(object):
def __init__(self, head = None):
self.head = head
def __len__(self):
#功能：输入头节点，返回链表长度
curr = self.head
counter = 0
while curr is not None:
counter += 1
curr = curr.next
return counter2.2 从前，后插入
从前插入：
- 被插入数据为空，返回
- 使用该输入数据创建一个节点，并将该节点指向原来头节点
- 设置该节点为头节点
时间复杂度和空间复杂度均为O(1)
def insertToFront(self,data):
#功能：输入data，插入到头节点前，并更改为头节点
#输出：当前头节点
if data is None:
return None
node = Node(data,self.head)
self.head = node
return node从后：append
- 若输入数据为空，返回None
- 若头节点为空，直接将输入数据作为头节点
- 遍历整个链表，直到当前节点的下一个节点为None时，将当前节点的下一个节点设置为输入数据
时间复杂度为O(n),空间O(1)
def append(self,data):
#功能：输入data,作为节点插入到末尾
if data is None:
return None
node = Node(data)
if self.head is None:
self.head = node
return node
curr_node = self.head
while curr_node.next is not None:
curr_node = curr_node.next
curr_node.next = node
return node2.3 查找与删除
查找
- 若查找的数据为空，返回
- 设置头节点为当前节点，若当前节点不为None,遍历整个链表
- 若当前节点的data与输入的data相同，但会当前节点，否则轮到下一个节点
可见时间复杂度为O(n),空间复杂度为O(1).
def find(self,data):
#功能：查找链表的节点data与data相同的节点
if data is None:
return None
curr_node = self.head
while curr_node is not None:
if curr_node.data == data:
return curr_node
curr_node = curr_node.next
return None删除1
申请两个变量，如果遇到匹配的，不用删除，直接将匹配节点的前一节点指向匹配节点的下一节点，因此需要定义一个前节点和一个当前节点，当前节点用来判断是否与输入数据匹配，前节点用来更改链表的指向。
- 若输入数据为None,返回
- 将头节点设置为前节点，头节点的下一个节点设置为当前节点
- 判断前节点是否与输入数据匹配，若匹配，将头节点设置为当前节点
- 遍历整个链表，若当前节点与输入数据匹配，将前节点的指针指向当前节点的下一个节点，否则，移到下一个节点
时间复杂度为O(n),空间复杂度为O(1).
def delete(slef,data):
#删除节点
if data is None:
return None
if self.head is None:
return None
if self.head.data == data:
self.head = self.head.next
return
prev_node = self.head
curr_node = self.head.next
while curr_node is not None:
if curr_node.data == data:
prev_node.next = curr_node.next
else:
prev_node = curr_node
curr_node = curr_node.next删除2
第二种解决办法就是只定义一个变量作为当前节点，使用它的下一个节点去判断是否与数据数据匹配，若匹配，直接将当前节点指向下下一个节点。
时间复杂度为O(n),空间复杂度为O(1).
def deleteAlt(self):
#只定义一个变量来完成删除操作
if data is None:
return
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
curr_node = self.head
while curr_node.next is not None:
if curr_node.next.data == data:
curr_node.next = curr_node.next.next
return
curr_node = curr_node.nextreference
Linked lists¶
用Python实现的数据结构与算法：链表
python数据结构-链表
Solution Notebook
