行业知识
【Python——链表】
2026-11-21 06:04:26
来源:互联网转载
���录
一、链表是什么?
二、单向链表
三、双向链表
一、链表是什么?
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(self.length()-1): self.append(item) else: #构造节点 node=Node(item) count=0 preNode=self._head while count