目录

一、链表

链表类的定义：

创建链表——头插法

创建链表——尾插法

二、双链表

定义双链表

双链表——插入p节点

双链表——删除

小结

三、链栈

四、链队列

自学视频：B站-路飞学城-清华大学博士讲解python数据结构与算法

一、链表

介绍：链表是由一系列节点组成的元素集合，每个节点包含两个部分，数据域item 和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表

讯享网

链表类的定义：

class Node(object): def __init__(self, item): self.item = item # 存数据 self.next = None # 存当前节点的下一个节点

测试：

讯享网if __name__ == '__main__': n1 = Node(1) n2 = Node(2) n3 = Node(3) n1.next = n2 n2.next = n3 print(n1.next.item) # 2 print(n1.next.next.item) # 3 print(n1.next.next.next.item) # 报错

创建链表——头插法

新来的节点成为新的头结点head，倒序排列

def create_linklist(li): head = Node(li[0]) for element in li[1:]: node = Node(element) # 创建一个节点 node.next = head head = node return head

测试：

讯享网lk = create_linklist([1, 2, 3]) print_linklist(lk)

创建链表——尾插法

新来的节点成为尾结点tail，顺序排列

def create_link_tail(li): head = Node(li[0]) tail = head for element in li[1:]: node = Node(element) # 创建一个节点 tail.next = node tail = node return head

测试：

讯享网lk1 = create_link_tail([1,2,3]) print_linklist(lk1)

二、双链表

定义双链表

class Node(object): def __init__(self, item): self.item = item self.next = None self.prior = None

双链表——插入p节点

p.next = curNode.next

curNode.prior = p

p.prior = curNode

curNode.next = p

双链表——删除

定义p指向要删除的节点

p = curNode.next

curNode.next = p.next

p.next.prior = curNode

小结

链表与顺序表

链表在插入删除的操作上明显快于顺序表
链表的内存可更灵活的分配
利用链表实现栈和队列
链表的链式存储结构对树和图的结构有很大的启发性

三、链栈

讯享网# 定义链节点类 class LinkNode(object): def __init__(self, data): self.data = data # 存数据 self.next = None # 存当前节点的下一个节点 # 链栈 class LinkStack(object): def __init__(self): self.top = LinkNode(None) # 定义栈顶为空 # 进栈 def push(self, e): node = LinkNode(e) # 创建一个新节点 node.next = self.top # 新节点的下一个指向top self.top = node # top指向新节点 # 出栈 def pop(self): if self.top is None: print("栈为空！") exit() out_data = self.top.data self.top = self.top.next return out_data # 判空 def is_empty(self): return self.top is None # 取栈顶元素 def get_top(self): if self.top is None: print("栈为空！") return None return self.top.data

测试：

if __name__ == '__main__': ls = LinkStack() for element in range(5): ls.push(element) print(ls.get_top()) print(ls.pop()) print(ls.is_empty())

结果：

四、链队列

讯享网# 定义一个链表类 class LinkNode(object): def __init__(self, data): self.data = data self.next = None # 定义一个链队列 class QueueLink(object): def __init__(self): temp_node = LinkNode(None) # 创建一个空的链表节点 self.rear = temp_node # 队尾指针，指向空节点 self.front = temp_node # 队首指针，指向空节点 # 创建一个链队列 def create_linkQueue(self, li): for element in li: self.EnQueue(element) # 判空 def is_empty(self): if self.front == self.rear: return True else: return False # 求队长 def LenghQueue(self): head = self.front count = 0 while head.next: count += 1 head = head.next return count # 入队 def EnQueue(self, e): node = LinkNode(e) # 创建一个新节点 if self.is_empty(): self.front.next = node self.rear.next = node self.rear = node # 出队 def DeQueue(self): if self.is_empty(): print("队列为空！") exit() else: temp = self.front.next # 定义temp指向队首元素 self.front.next = temp.next # 让front的next指针指向队首元素的下一个 if self.rear == temp: # 该节点为尾结点 self.front = self.rear return temp.data def Traverse(self): head = self.front while head.next: head = head.next print(head.data, end=" ") print(" ") def GetQueue(self): return self.front.next.data 

测试：

if __name__ == '__main__': q1 = QueueLink() q1.create_linkQueue([1, 2, 3, 4, 5, 6]) print("队列元素如下") q1.Traverse() print("队列的长度为{}".format(q1.LenghQueue())) print("队首元素为{}".format(q1.GetQueue())) for element in range(q1.LenghQueue()): print(q1.DeQueue(), end=" ")

结果：