代码收藏家 Python链表操作指南
目录
一、链表是什么？
1.定义：链表（Linked list）是一种常见的基础数据结构，是一种线性表，在每一个节点（数据存储单元）里存放下一个节点的位置信息
2.优点：顺序表的构建需要预知数据大小来申请连续存储空间，扩充时需要进行数据迁移，使用不灵活，链表充分利用计算机内存空间，实现灵活内存动态管理
二、单向链表
1.定义：单向链表（单链表）是链表中最简单一种形式，它的每个节点包含两个域——信息域（元素域）和链接域
(1)表元素域elem用来存放具体的数据
(2)链接域next用来存放下一个节点的位置
(3)变量p指向链表的头节点(首节点)的位置，从p出发能找到表中的任意节
2.链表相关方法：
| 方法 | 说明 |
| is_empty() | 链表是否为空 |
| length() | 链表长度 |
| travel() | 遍历整个链表 |
| add(item) | 链表头部添加元素 |
| append(item) | 链表尾部添加元素 |
| insert(pos,item) | 在指定位置添加元素 |
| remove(item) | 删除节点 |
| search(item) | 查找结点是否存在 |
#定义节点
class Node(object):
def __init__(self,elem):
self.elem=elem
self.next=None
#构造单向链表
class SingleLinkedList:
#判断链表是否为空：_head指向None，则为空
def is_empty(self):
'''
if self._head==None:
print("True")
else:
print("False")
'''
return self._head==None
#单向链表初始化
def __init__(self,node=None):
#判断node是否为空
if node!=None:
headNode=Node(node)
self._head=headNode
else:
self._head=node
#计算链表长度
def length(self):
count=0
curNode=self._head
while curNode!=None:
count+=1
curNode=curNode.next
return count
#遍历链表
def travel(self):
curNode=self._head
while curNode!=None:
print(curNode.elem,end='\t')
curNode=curNode.next
print(" ")
#在头部添加元素
def add(self,item):
#将传入的值构造成节点
node=Node(item)
#将新节点的链接域next指向头节点
node.next=self._head
#将链表的头_head指向新节点
self._head=node
#在尾部添加元素
def append(self,item):
#将传入的值构造成节点
node=Node(item)
if self.is_empty(): #单链表为空
self._head=node
else: #单链表不为空
curNode=self._head
while curNode.next!=None:
curNode=curNode.next
#修改节点，最后一个节点的next指向node
curNode.next=node
#在指定位置添加元素
def insert(self,pos,item):
#如果pos<=0，默认插入到头部
if pos<=0:
self.add(item)
#如果pos>链表长度，直接在尾部追加
elif pos>(self.length()-1):
self.append(item)
else:
#构造节点
node=Node(item)
count=0
preNode=self._head
while count<(pos-1): #查找前一个节点
count+=1
preNode=preNode.next
#修改指向
#将前一个节点的next指向插入节点
node.next=preNode.next
#将插入位置的前一个节点next指向新节点
preNode.next=node
#查找节点是否存在
def search(self,item):
curNode=self._head
while curNode!=None:
if curNode.elem==item:
return True
curNode=curNode.next
return False
#删除节点
def remove(self,item):
curNode=self._head
preNode=None
while curNode!=None:
if curNode.elem==item:
#判断是否是头节点
if preNode==None:#是头节点
self._head=curNode.next
else:
#删除
preNode.next=curNode.next
break
else:
preNode=curNode
curNode=curNode.next
if __name__=="__main__":
#初始化元素值为10单向链表
singleLinkedList=SingleLinkedList(30)
print("是否为空链表：",singleLinkedList.is_empty())
print("链表长度为：",singleLinkedList.length())
print("----遍历链表----")
singleLinkedList.travel()
print("-----查找-----",singleLinkedList.search(30))
print("-----头部插入-----")
singleLinkedList.add(1)
singleLinkedList.add(2)
singleLinkedList.add(3)
singleLinkedList.travel()
print("-----尾部追加-----")
singleLinkedList.append(10)
singleLinkedList.append(20)
singleLinkedList.travel()
print("-----链表长度-----",singleLinkedList.length())
print("-----指定位置插入-----")
singleLinkedList.insert(-1,100)
singleLinkedList.travel()
print("-----删除节点-----")
singleLinkedList.remove(100)
singleLinkedList.travel()是否为空链表： False
链表长度为： 1
—-遍历链表—-
30
—–查找—– True
—–头部插入—–
3 2 1 30
—–尾部追加—–
3 2 1 30 10 20
—–链表长度—– 1
—–指定位置插入—–
100 3 2 1 30 10 20
—–删除节点—–
3 2 1 30 10 20
三、双向链表
1.双向链表（双面链表）是一种更复杂的链表。每个节点有两个链接:一个指向前一个节点，当此节点为第一个节点时，指向空值，而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
2.双向链表的实现：
class Node:
def __init__(self,elem):
self.elem=elem
self.next=None #下一个节点
self.prev=None #前一个节点
class DoubleLinkedList:
# 双向链表初始化
def __init__(self, node=None):
# 判断node是否为空
if node != None:
headNode=Node(node)
self._head=headNode
else:
self._head=node
def is_empty(self):
'''
if self._head==None:
print("True")
else:
print("False")
'''
return self._head==None
#计算链表长度
def length(self):
count=0
curNode=self._head
while curNode!=None:
count+=1
curNode=curNode.next
return count
#遍历链表
def travel(self):
curNode=self._head
while curNode!=None:
print(curNode.elem,end='\t')
curNode=curNode.next
print(" ")
#在头部添加元素
def add(self,item):
#判断是否空链表
node = Node(item)
if self.is_empty():
self._head=node
else:
#将传入的值构造成节点
node=Node(item)
#将新节点的链接域next指向头节点
node.next=self._head
#将_head的头节点的prev指向node
self._head.prev=node
#将链表的头_head指向新节点
self._head=node
#在尾部追加元素
def append(self,item):
#将传入的值构造成节点
node=Node(item)
if self.is_empty(): #双向链表为空
self._head=node
else: #双向链表不为空
curNode=self._head
while curNode.next!=None:
curNode=curNode.next
#修改节点，最后一个节点的next指向node
curNode.next=node
#将node节点的前驱指向当前节点
node.prev=curNode
#在指定位置添加元素
def insert(self,pos,item):
#如果pos<=0，默认插入到头部
if pos<=0:
self.add(item)
#如果pos>链表长度，直接在尾部追加
elif pos>(self.length()-1):
self.append(item)
else:
#构造节点
node=Node(item)
count=0
curNode=self._head
while count<(pos-1): #查找前一个节点
count+=1
curNode=curNode.next
#修改指向
#node节点前驱指向当前节点
node.prev=curNode
#node节点的next指向当前节点的下一个节点
node.next=curNode.next
#当前节点的下一个节点的前驱指向node节点
curNode.next.prev=node
#当前节点的下一个节点指向node节点
curNode.next=node
#查找节点是否存在
def search(self,item):
curNode=self._head
while curNode!=None:
if curNode.elem==item:
return True
curNode=curNode.next
return False
#删除节点
def remove(self,item):
curNode=self._head
while curNode!=None:
if curNode.elem==item:
#判断是否是头节点
if curNode==self._head:#是头节点
self._head=curNode.next
#判断当前节点是否只有一个节点
if curNode.next:
curNode.next.prev==None
else:
#删除
curNode.prev.next=curNode.next
#判断当前节点是否是最后一个节点，若是，不需要移动下一个
if curNode.next:
curNode.next.prev=curNode.prev
break
else:
curNode=curNode.next
if __name__=="__main__":
doubleLinkedList=DoubleLinkedList()
print("-----头部添加-----")
doubleLinkedList.add(11)
doubleLinkedList.add(22)
doubleLinkedList.add(33)
doubleLinkedList.travel()
print("-----尾部追加-----")
doubleLinkedList.append(44)
doubleLinkedList.travel()
print("指定位置插入")
doubleLinkedList.insert(3,100)
doubleLinkedList.travel()
print("-----删除元素-----")
doubleLinkedList.remove(33)
doubleLinkedList.travel()
—–头部添加—–
33 22 11
—–尾部追加—–
33 22 11 44
指定位置插入
33 22 11 44 100
—–删除元素—–
22 11 44 100
