Python 实现链表实例代码

更新时间：2020-04-29 13:18:01 作者：startmvc

Python实现链表实例代码前言算法和数据结构是一个亘古不变的话题，作为一个程序员，掌握

Python 实现链表实例代码

前言

算法和数据结构是一个亘古不变的话题，作为一个程序员，掌握常用的数据结构实现是非常非常的有必要的。

实现清单

实现链表，本质上和语言是无关的。但是灵活度却和实现它的语言密切相关。今天用Python来实现一下，包含如下操作：


['addNode(self, data)']
['append(self, value)']
['prepend(self, value)']
['insert(self, index, value)']
['delNode(self, index)']
['delValue(self, value)']
['isempty(self)']
['truncate(self)']
['getvalue(self, index)']
['peek(self)']
['pop(self)']
['reverse(self)']
['delDuplecate(self)']
['updateNode(self, index, value)']
['size(self)']
['print(self)']

生成这样的一个方法清单肯定是不能手动写了，要不然得多麻烦啊，于是我写了个程序，来匹配这些自己实现的方法。代码比较简单，核心思路就是匹配源文件的每一行，找到符合匹配规则的内容，并添加到总的结果集中。

代码如下：


# coding: utf8

# @Author: 郭 璞
# @File: getmethods.py 
# @Time: 2017/4/5 
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 获取一个模块或者类中的所有方法及参数列表

import re

def parse(filepath, repattern):
 with open(filepath, 'rb') as f:
 lines = f.readlines()
 # 预解析正则
 rep = re.compile(repattern)
 # 创建保存方法和参数列表的结果集列表
 result = []
 # 开始正式的匹配实现
 for line in lines:
 res = re.findall(rep, str(line))
 print("{}的匹配结果{}".format(str(line), res))
 if len(res)!=0 or res is not None:
 result.append(res)
 else:
 continue
 return [item for item in result if item !=[]]


if __name__ == '__main__':
 repattern = "def (.[^_0-9]+\(.*?\)):"
 filepath = './SingleChain.py'
 result = parse(filepath, repattern)
 for item in result:
 print(str(item))

链表实现


# coding: utf8

# @Author: 郭 璞
# @File: SingleChain.py 
# @Time: 2017/4/5 
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 单链表实现

class Node(object):
 def __init__(self, data, next):
 self.data = data
 self.next = next

class LianBiao(object):

 def __init__(self):
 self.root = None

 # 给单链表添加元素节点
 def addNode(self, data):
 if self.root==None:
 self.root = Node(data=data, next=None)
 return self.root
 else:
 # 有头结点，则需要遍历到尾部节点，进行链表增加操作
 cursor = self.root
 while cursor.next!= None:
 cursor = cursor.next
 cursor.next = Node(data=data, next=None)
 return self.root

 # 在链表的尾部添加新节点，底层调用addNode方法即可
 def append(self, value):
 self.addNode(data=value)

 # 在链表首部添加节点
 def prepend(self, value):
 if self.root == None:
 self.root = Node(value, None)
 else:
 newroot = Node(value, None)
 # 更新root索引
 newroot.next = self.root
 self.root = newroot

 # 在链表的指定位置添加节点
 def insert(self, index, value):
 if self.root == None:
 return
 if index<=0 or index >self.size():
 print('index %d 非法， 应该审视一下您的插入节点在整个链表的位置！')
 return
 elif index==1:
 # 如果index==1， 则在链表首部添加即可
 self.prepend(value)
 elif index == self.size()+1:
 # 如果index正好比当前链表长度大一，则添加在尾部即可
 self.append(value)
 else:
 # 如此，在链表中部添加新节点，直接进行添加即可。需要使用计数器来维护插入未知
 counter = 2
 pre = self.root
 cursor = self.root.next
 while cursor!=None:
 if counter == index:
 temp = Node(value, None)
 pre.next = temp
 temp.next = cursor
 break
 else:
 counter += 1
 pre = cursor
 cursor = cursor.next

 # 删除指定位置上的节点
 def delNode(self, index):
 if self.root == None:
 return
 if index<=0 or index > self.size():
 return
 # 对第一个位置需要小心处理
 if index == 1:
 self.root = self.root.next
 else:
 pre = self.root
 cursor = pre.next
 counter = 2
 while cursor!= None:
 if index == counter:
 print('can be here!')
 pre.next = cursor.next
 break
 else:
 pre = cursor
 cursor = cursor.next
 counter += 1

 # 删除值为value的链表节点元素
 def delValue(self, value):
 if self.root == None:
 return
 # 对第一个位置需要小心处理
 if self.root.data == value:
 self.root = self.root.next
 else:
 pre = self.root
 cursor = pre.next
 while cursor!=None:
 if cursor.data == value:
 pre.next = cursor.next
 # 千万记得更新这个节点，否则会出现死循环。。。
 cursor = cursor.next
 continue
 else:
 pre = cursor
 cursor = cursor.next

 # 判断链表是否为空
 def isempty(self):
 if self.root == None or self.size()==0:
 return True
 else:
 return False

 # 删除链表及其内部所有元素
 def truncate(self):
 if self.root == None or self.size()==0:
 return
 else:
 cursor = self.root
 while cursor!= None:
 cursor.data = None
 cursor = cursor.next
 self.root = None
 cursor = None

 # 获取指定位置的节点的值
 def getvalue(self, index):
 if self.root is None or self.size()==0:
 print('当前链表为空！')
 return None
 if index<=0 or index>self.size():
 print("index %d不合法！"%index)
 return None
 else:
 counter = 1
 cursor = self.root
 while cursor is not None:
 if index == counter:
 return cursor.data
 else:
 counter += 1
 cursor = cursor.next

 # 获取链表尾部的值，且不删除该尾部节点
 def peek(self):
 return self.getvalue(self.size())

 # 获取链表尾部节点的值，并删除该尾部节点
 def pop(self):
 if self.root is None or self.size()==0:
 print('当前链表已经为空！')
 return None
 elif self.size()==1:
 top = self.root.data
 self.root = None
 return top
 else:
 pre = self.root
 cursor = pre.next
 while cursor.next is not None:
 pre = cursor
 cursor = cursor.next
 top = cursor.data
 cursor = None
 pre.next = None
 return top

 # 单链表逆序实现
 def reverse(self):
 if self.root is None:
 return
 if self.size()==1:
 return
 else:
 # post = None
 pre = None
 cursor = self.root
 while cursor is not None:
 # print('逆序操作逆序操作')
 post = cursor.next
 cursor.next = pre
 pre = cursor
 cursor = post
 # 千万不要忘记了把逆序后的头结点赋值给root，否则无法正确显示
 self.root = pre

 # 删除链表中的重复元素
 def delDuplecate(self):
 # 使用一个map来存放即可，类似于变形的“桶排序”
 dic = {}
 if self.root == None:
 return
 if self.size() == 1:
 return
 pre = self.root
 cursor = pre.next
 dic = {}
 # 为字典赋值
 temp = self.root
 while temp!=None:
 dic[str(temp.data)] = 0
 temp = temp.next
 temp = None
 # 开始实施删除重复元素的操作
 while cursor!=None:
 if dic[str(cursor.data)] == 1:
 pre.next = cursor.next
 cursor = cursor.next
 else:
 dic[str(cursor.data)] += 1
 pre = cursor
 cursor = cursor.next


 # 修改指定位置节点的值
 def updateNode(self, index, value):
 if self.root == None:
 return
 if index<0 or index>self.size():
 return
 if index == 1:
 self.root.data = value
 return
 else:
 cursor = self.root.next
 counter = 2
 while cursor!=None:
 if counter == index:
 cursor.data = value
 break
 cursor = cursor.next
 counter += 1


 # 获取单链表的大小
 def size(self):
 counter = 0
 if self.root == None:
 return counter
 else:
 cursor = self.root
 while cursor!=None:
 counter +=1
 cursor = cursor.next
 return counter


 # 打印链表自身元素
 def print(self):
 if(self.root==None):
 return
 else:
 cursor = self.root
 while cursor!=None:
 print(cursor.data, end='\t')
 cursor = cursor.next
 print()


if __name__ == '__main__':
 # 创建一个链表对象
 lianbiao = LianBiao()
 # 判断当前链表是否为空
 print("链表为空%d"%lianbiao.isempty())
 # 判断当前链表是否为空
 lianbiao.addNode(1)
 print("链表为空%d"%lianbiao.isempty())
 # 添加一些节点，方便操作
 lianbiao.addNode(2)
 lianbiao.addNode(3)
 lianbiao.addNode(4)
 lianbiao.addNode(6)
 lianbiao.addNode(5)
 lianbiao.addNode(6)
 lianbiao.addNode(7)
 lianbiao.addNode(3)
 # 打印当前链表所有值
 print('打印当前链表所有值')
 lianbiao.print()
 # 测试对链表求size的操作
 print("链表的size: "+str(lianbiao.size()))
 # 测试指定位置节点值的获取
 print('测试指定位置节点值的获取')
 print(lianbiao.getvalue(1))
 print(lianbiao.getvalue(lianbiao.size()))
 print(lianbiao.getvalue(7))
 # 测试删除链表中指定值， 可重复性删除
 print('测试删除链表中指定值， 可重复性删除')
 lianbiao.delNode(4)
 lianbiao.print()
 lianbiao.delValue(3)
 lianbiao.print()
 # 去除链表中的重复元素
 print('去除链表中的重复元素')
 lianbiao.delDuplecate()
 lianbiao.print()
 # 指定位置的链表元素的更新测试
 print('指定位置的链表元素的更新测试')
 lianbiao.updateNode(6, 99)
 lianbiao.print()
 # 测试在链表首部添加节点
 print('测试在链表首部添加节点')
 lianbiao.prepend(77)
 lianbiao.prepend(108)
 lianbiao.print()
 # 测试在链表尾部添加节点
 print('测试在链表尾部添加节点')
 lianbiao.append(99)
 lianbiao.append(100)
 lianbiao.print()
 # 测试指定下标的插入操作
 print('测试指定下标的插入操作')
 lianbiao.insert(1, 10010)
 lianbiao.insert(3, 333)
 lianbiao.insert(lianbiao.size(), 99999)
 lianbiao.print()
 # 测试peek 操作
 print('测试peek 操作')
 print(lianbiao.peek())
 lianbiao.print()
 # 测试pop 操作
 print('测试pop 操作')
 print(lianbiao.pop())
 lianbiao.print()
 # 测试单链表的逆序输出
 print('测试单链表的逆序输出')
 lianbiao.reverse()
 lianbiao.print()
 # 测试链表的truncate操作
 print('测试链表的truncate操作')
 lianbiao.truncate()
 lianbiao.print()

代码运行的结果如何呢？是否能满足我们的需求，且看打印的结果:


D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py
链表为空1
链表为空0
打印当前链表所有值
1 2 3 4 6 5 6 7 3 
链表的size: 9
测试指定位置节点值的获取
1
3
6
测试删除链表中指定值， 可重复性删除
can be here!
1 2 3 6 5 6 7 3 
1 2 6 5 6 7 
去除链表中的重复元素
1 2 6 5 7 
指定位置的链表元素的更新测试
1 2 6 5 7 
测试在链表首部添加节点
108 77 1 2 6 5 7 
测试在链表尾部添加节点
108 77 1 2 6 5 7 99 100 
测试指定下标的插入操作
10010 108 333 77 1 2 6 5 7 99 99999 100 
测试peek 操作
100
10010 108 333 77 1 2 6 5 7 99 99999 100 
测试pop 操作
100
10010 108 333 77 1 2 6 5 7 99 99999 
测试单链表的逆序输出
99999 99 7 5 6 2 1 77 333 108 10010 
测试链表的truncate操作

Process finished with exit code 0

刚好实现了目标需求。

总结

今天的内容还是比较基础，也没什么难点。但是看懂和会写还是两码事，没事的时候写写这样的代码还是很有收获的。