这篇文章主要为大家展示了“python如何实现单链表”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“python如何实现单链表”这篇文章吧。
一、链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
二、单链表介绍
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成： 元素(数据元素的映象) + 指针(指示后继元素存储位置) ，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。它的每个节点包含两个域， 一个信息域（元素域）和一个链接域 。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢，使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。
三、单链表结构
表元素域elem用来存放具体的数据。
链接域next用来存放下一个节点的位置（python中的标识）
变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
四、单链表的常用操作图解
1、头插
2、尾插
3、指定为之插入
4、删除
五、单链表的python代码实现
# 创建节点
class Node(object):
def __init__(self,item):
self.element = item
self.next = None
# 创建单链表类
class SingleLinkList(object):
def __init__(self):
self.header = None
self.length = 0
# 1、判断是否为空
def is_empty(self):
if self.header == None:
return True
else:
return False
# 2、头部插入
def add(self,node):
if self.is_empty():
self.header = node
else:
node.next = self.header
self.header = node
# currentNode = self.header
self.length += 1
# 3、尾部插入
def appent(self,node):
currentNode = self.header
if self.is_empty():
self.add(node)
else:
while (currentNode.next != None):
currentNode = currentNode.next
currentNode.next = node
self.length += 1
# 4、指定位置插入
def insert(self,node,index):
currentNode = self.header
if index>self.length+1 or index<=0:
print("你要插入的位置不对，请重现选择位置")
if index == 1:
self.add(node)
elif index == 2:
node.next = self.header.next
self.header.next = node
self.length += 1
else:
for i in range(1,index-1):
currentNode = currentNode.next
node.next = currentNode.next
currentNode.next = node
self.length += 1
# 5、遍历
def travel(self):
currentNode = self.header
if self.length == 0:
print("你要遍历的链表没有数据\n")
else:
print("你要遍历的链表里面的元素有:",end=" ")
for i in range(self.length):
print("%s "%currentNode.element,end=" ")
currentNode = currentNode.next
print("\n")
# 6、排序不用交换节点的位置，只需要交换节点上的数据值
def list_sort(self):
for i in range(0,self.length-1):
currentNode = self.header
for j in range(0,self.length-i-1):
if currentNode.element > currentNode.next.element:
temp = currentNode.element
currentNode.element = currentNode.next.element
currentNode.next.element = temp
currentNode = currentNode.next
# 7、按索引删除
def remove(self,index):
if index<=0 or index>self.length:
print("你输入的下标不对，请重新输入")
return
else:
if index == 1:
self.header = self.header.next
currentNode = self.header
elif index == 2:
currentNode = self.header
currentNode.next = currentNode.next.next
else:
currentNode = self.header
for i in range(1,index-1):
currentNode = currentNode.next
currentNode.next = currentNode.next.next
self.length -= 1
# 8、查找是否包含,并返回下标
def isContain(self,num):
contain = 0
currentNode = self.header
for i in range(self.length):
if currentNode.element == num:
print("%d在链表中%d处\n"%(num,i))
contain = 1
currentNode = currentNode.next
if contain == 0:
print("%d不在链表中\n"%num)
# 9、根据下标找节点
def searchNodeByIndex(self,index):
currentNode = self.header
if index<=0 or index>self.length:
print("你输入的下标不对，请重新输入\n")
return 0
else:
for i in range(index-1):
currentNode = currentNode.next
return currentNode
# 10、根据下标修改节点的值
def modifyByIndex(self,index,num):
currentNode = self.header
if index<=0 or index>self.length:
print("你输入的下标不对，请重新输入\n")
else:
for i in range(index-1):
currentNode = currentNode.next
currentNode.element = num
def main():
# 创建一个节点对象
node1 = Node(1)
# 创建一个单链表对象
single_link_list = SingleLinkList()
print("验证空链表的遍历")
single_link_list.travel()
print("验证头插")
single_link_list.add(node1)
single_link_list.travel()
print("验证尾插")
node2 = Node(2)
single_link_list.appent(node2)
single_link_list.travel()
print("验证按位置插入")
node3 = Node(3)
single_link_list.insert(node3,1)
single_link_list.travel()
print("继续验证头插")
node4 = Node(5)
single_link_list.add(node4)
single_link_list.travel()
print("继续验证按位置插入")
node5 = Node(4)
single_link_list.insert(node5,4)
single_link_list.travel()
print("验证删除")
single_link_list.remove(3)
single_link_list.travel()
print("验证查找一个节点是否在链表中")
single_link_list.isContain(8)
print("验证按下标查找节点")
node = single_link_list.searchNodeByIndex(2)
print("第二个节点的值为：%s"%node.element)
print("\n验证排序")
single_link_list.list_sort()
single_link_list.travel()
print("验证修改")
single_link_list.modifyByIndex(2,10)
single_link_list.travel()
if __name__ == '__main__':
main()运行结果为：
验证空链表的遍历
你要遍历的链表没有数据验证头插
你要遍历的链表里面的元素有: 1验证尾插
你要遍历的链表里面的元素有: 1 2验证按位置插入
你要遍历的链表里面的元素有: 3 1 2继续验证头插
你要遍历的链表里面的元素有: 5 3 1 2继续验证按位置插入
你要遍历的链表里面的元素有: 5 3 1 4 2验证删除
你要遍历的链表里面的元素有: 5 3 4 2验证查找一个节点是否在链表中
8不在链表中验证按下标查找节点
第二个节点的值为：3验证排序
你要遍历的链表里面的元素有: 2 3 4 5验证修改
你要遍历的链表里面的元素有: 2 10 4 5
六、单链表的C语言代码实现
