python实现链表

什么是链表

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

python实现一个简单链表

我们可以用python实现一个超级简单的链表

class node:# 初始化数据def __init__(self, item):self.item = itemself.next = None
# 一个一个构造链表元素
a = node(1)
b = node(2)
c = node(3)a.next = b
b.next = c# 打印我们的节点
print(a.next.next.item)

如上，我们是一个一个的去创建，那么，我们如何通过python去实现整体的链表创建呢？

python实现链表创建

这里有两种方法可以实现，一种是头插法，一种是尾插法；

这里我们先使用python实现头插法

class Node:# 初始化数据def __init__(self, item):self.item = itemself.next = None
# 一个一个构造链表元素
# a = node(1)
# b = node(2)
# c = node(3)
#
# a.next = b
# b.next = c# 打印我们的节点
# print(a.next.next.item)def create_linklist_head(li):# 头部指向第一个元素head = Node(li[0])# 接下来，循环创建这个元素for element in li[1:]:# 创建节点node = Node(element)# 节点的下一个是头部位置node.next = head# 头部位置就是加进来的节点的位置head = nodereturn headdef print_linklist(lk):while lk:print(lk.item, end=',')lk = lk.nextlk = create_linklist_head([1, 2, 3, 4, 5])
print_linklist(lk)

我们创建了实例，运行结果是：

接下俩我们实现尾插法：

def create_linklist_head(li):# 头部指向第一个元素head = Node(li[0])# 接下来，循环创建这个元素for element in li[1:]:# 创建节点node = Node(element)# 节点的下一个是头部位置node.next = head# 头部位置就是加进来的节点的位置head = nodereturn headdef create_linklist_tail(li):head = Node(li[0])tail = headfor element in li[1:]:node = Node(element)tail.next = nodetail = nodereturn headdef print_linklist(lk):while lk:print(lk.item, end=',')lk = lk.next# lk = create_linklist_head([1, 2, 3, 4, 5])
# print_linklist(lk)
lk = create_linklist_tail([1, 2, 3, 4, 5])
print_linklist(lk)

运行之后，我们发现，我们用尾插法实现了一个链表的输出