目录
一、链表是什么？
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.nextif __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
三、双向链表
双向链表（双面链表）是一种更复杂的链表。每个节点有两个链接:一个指向前一个节点，当此节点为第一个节点时，指向空值，而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
双向链表的实现：
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.nextif __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
来源地址：https://blog.csdn.net/m0_70964767/article/details/126184640
