参考【易百教程】用Python实现链表及其功能
"""
python链表的基本操作：节点、链表、增删改查
"""
import sys class Node(object):
"""
节点类，实例化后的对象用来表示链表中的一个节点
"""
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None class SLinkedList(object):
"""
链表类，用于初始化一个链表，及多链表的一些操作
"""
def __init__(self):
self.headval = None def listprint(self):
"""
打印链表
"""
val = self.headval
while val is not None:
print(val.dataval, end=' ')
val = val.nextval
print() def insertStart(self, newdata):
"""
从链表头插入一个节点
param@newdata: 插入的新节点，为Node类实例对象的dataval
"""
newdata = Node(newdata)
newdata.nextval = self.headval
self.headval = newdata def insertEnd(self, newdata):
"""
从链表尾部插入一个节点
param@newdata: 插入的新节点，为Node类实例对象的dataval
"""
newdata = Node(newdata)
if self.headval == None:
self.headval = newdata
return
else:
temp = self.headval
while temp.nextval:
temp = temp.nextval
temp.nextval = newdata def insertBetween(self, node, newdata):
"""
在链表的node节点后插入一个新元素
param@node: 链表中的一个节点，新插入的元素将插入其后面
param@newdata: 插入的新节点，为Node类实例对象的dataval
"""
if (not node) or node == None:
raise Exception('参数异常！')
else:
newdata = Node(newdata)
newdata.nextval = node.nextval
node.nextval = newdata def removeNode(self, node_val):
"""
从链表中删除值为node_val的节点
param@node_val: 被删除节点的值，即Node类实例对象的dataval
"""
if self.headval == None:
print('链表为空链表！')
else:
if self.headval.nextval == None:
if self.headval == node_val:
sefl.headval = None
else:
return
else:
temp = self.headval
if temp.dataval == node_val:
self.headval = temp.nextval
else:
temp = self.headval
while temp.nextval:
if temp.nextval.dataval == node_val:
temp.nextval = temp.nextval.nextval
break
temp = temp.nextval li = SLinkedList()
e1 = Node('one')
e2 = Node('two')
e3 = Node('three')
li.headval = e1
e1.nextval = e2
e2.nextval = e3
li.listprint()
以上为单向链表一些基本操作的Python实现，接下来也展示一下双向链表的一些简单实现
"""
双向链表
"""
import sys
import collections # 双向链表的节点类
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
self.prev = None # 双向链表类
class DoubleLinkedList(object):
def __init__(self):
self.head = None def push(self, newdata):
"""
尾插法插入数据,也就是向链表的结尾追加元素
param@newdata: 新插入的数据，为Node类的实例对象的data
"""
newdata = Node(newdata)
if self.head == None:
self.head = newdata
elif self.head.next == None:
newdata.next = self.head.next
self.head.next = newdata
newdata.prev = self.head
else:
data = self.head
while data.next:
data = data.next
newdata.next = data.next
data.next = newdata
newdata.prev = data # 正向打印出链表值的函数
def listprint(self):
data = self.head
while data is not None:
print(data.data, end=' ')
data = data.next
print() # # 反向打印出链表值的函数
def listprint_2(self):
data = self.head
while data.next:
data = data.next
while data is not None:
print(data.data, end=' ')
data = data.prev
print() def insert(self, prev_node, newdata):
"""
在链表的一个节点后插入一个节点
param@prev_node: 要插入节点的前一个节点
param@newdata: 插入的节点的值，为Node类实例对象的data
"""
newdata = Node(newdata)
if prev_node is None:
return
elif prev_node.next is None:
newdata.next = prev_node.next
prev_node.next = newdata
newdata.prev = prev_node
else:
prev_node.next.prev = newdata
newdata.prev = prev_node
newdata.next = prev_node.next
prev_node.next = newdata dlist = DoubleLinkedList()
dlist.push('one')
dlist.push('two')
dlist.push('three')
dlist.insert(dlist.head, 'hhh')
dlist.listprint()
dlist.listprint_2()
暂时到这里