目录
基础 知识1.1 链表的基本结构
1.2 节点类和链表节点的定义
1.3 顺序打印和逆序打印链表的基本操作
2.1 计算链表长度
2.2 从前，后插入数据
2.3 查找与删除
参考
1.基础 知识1.1 链表的基本结构
链表是通过一个个节点组成的，每个节点都包含了称为cargo的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。
如图：
链表的基本元素有：
但链表也分为单向链表和单向循环链表，双向链表和双向循环链表，如图为单向链表和单向循环链表：
写个基本程序测试一下：
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函数，且能存储下来。
链表怎么定义呢？
我们可以先定义一个一个节点，如下：
然后再把每个节点的关系表示出来，就OK了
node1.next = node2node2.next = node31.3 顺序打印和逆序打印
因为先前已经建立了关系，所以可以通过输入第一个节点，循环整个链表然后顺序打印整个链表。
def printList(node): while node: print node node = node.nextprintList(node1)123使用递归的方法来打印，主要步骤如下：
将list拆分成两个部分，head:第一个元素，tail:其余元素向后打印打印第一个元素 def printBackward(lists): if lists == None: return head = lists tail= lists.next print head,tail printBackward(tail) print head,tailprintBackward(node1)1 22 33 None3 None2 31 2事实上，还能更简便。
def printBackward(lists): if lists == None:return printBackward(lists.next) print listsprintBackward(node1) 2.链表的基本操作在链表的基本操作中，包括插入，删除等，但要注意的是一下的操作是针对非循环链表的，从头节点开始操作，而且我们不能插入 None值到链表中。
2.1 计算链表长度
class Node(object):#节点类 #功能：输入一个值data，将值变为一个节点 def __init__(self, data, next = None): self.data = data self.next = next def __str__(self): return self.dataclass 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
申请两个变量，如果遇到匹配的，不用删除，直接将匹配节点的前一节点指向匹配节点的下一节点，因此需要定义一个前节点和一个当前节点，当前节点用来判断是否与输入数据匹配，前节点用来更改链表的指向。
时间复杂度为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