python 实现链表

链表基础知识

链表是在物理内存中不连续，数据通过链表中的指针来链接到下一个元素。

链表由一系列节点组成，节点在运行时动态生成，节点一般包括两个部分：存储数据的数据域，存储下一个节点的指针域

链表的常用操作：节点的插入和删除。节点一般包括一个根节点，其他节点都是根据根节点生成。

单链表

# 链表的创建
#第一次加入加入节点，链表为空 ，第二次加入节点，先找到原有链表的最后一个节点
# 怎么判断到最后一个节点，但节点指向为空的时候则判断该节点为最后一个节点# 节点类
class ListNode:def __init__(self,val=0,next=None):self.val=valself.next=nextclass LinkedList:# 初始化def __init__(self):self.head=None  #头节点指向为空# 创建一个链表def create(self,data):self.head=ListNode(0)  #定义一个头节点cur=self.headfor i in range(len(data)):node=ListNode(data[i])  #一个新的节点cur.next=node  #头节点指向新的节点cur=cur.next  #更新# 获取链表的长度def length(self):count=0cur=self.head  #当前节点while cur: #遍历节点，当节点为None的时候表示当前节点为空count+=1#更新节点cur=cur.nextreturn count# 添加元素def insert(self,index,val):#在头部 尾部 中间添加#首先定义一个新的节点node=ListNode(val)if index==0:#表示在头部插入元素node.next=self.headself.head=nodeelif index==self.length()-1:# 表示在尾部插入元素#定义一个指针表示当前节点cur=self.head #当前节点从头节点开始while cur.next:cur=cur.nextcur.next=nodeelif index>0 and index<self.length()-1:#在中间插入节点cur=self.headcount=0while cur and count<index-1: #当前节点不是尾节点count+=1cur=cur.nextnode.next=cur.nextcur.next=nodeelse:print('插入位置超出索引')#删除元素def remove(self,index):pass#修改元素def change(self,index,val):pass#打印链表def display(self):cur=self.headcount=0while cur:print('第{}个节点，值为{}'.format(count,cur.val))count+=1cur=cur.next

# 链表的创建
#第一次加入加入节点，链表为空 ，第二次加入节点，先找到原有链表的最后一个节点
# 怎么判断到最后一个节点，但节点指向为空的时候则判断该节点为最后一个节点# 节点类
class ListNode:# 定义节点类，包含数据域和指针域def __init__(self,data=None,next=None):self.data=data #节点的数据域self.next=next  #指向下一个节点的指针class LinkedList:# 初始化def __init__(self):self.head=None  #头节点指向为空# 创建一个链表def create(self,data):self.head=None  #定义一个头节点current=self.head  #当前节点#遍历data，给每一个节点赋值，并且指向下一个节点for _ in data:#创建一个新的节点类node=ListNode(_)if current is None:#如果当前节点是空，表示是头节点为空current=self.head=nodeelse:current.next=nodecurrent=current.nextreturn self.head#打印链表的长度def Len_Link(self):count=0current=self.headwhile(1):if current is not None:  #判断是不是尾节点，如果不是则链表长度加1count+=1current=current.nextelse:break# print('共有{}个节点'.format(count))return count#打印链表def display(self):print('开始打印链表')current=self.headcount=0while current:count+=1print("第{}个节点".format(count),current.data)current=current.next#插入一个节点def insert(self,index,data):lenth=self.Len_Link()node=ListNode(data)current=self.headif index==0+1:#插入头节点if current :#头节点不为空node.next=currentself.head=nodeelse:#头节点为空self.head=nodeelif index==lenth+1:#在尾部插入节点while current:if current.next is None:current.next=nodebreakelse:current = current.nextelif index<=lenth and index>0:count=0while current:count+=1if count==index:node.next=current.nextcurrent.next=nodebreakelse:current=current.nextreturn self.headdef remove(self,index):#删除一个节点#删除头节点lenth=self.Len_Link()current=self.headif index==1:if current is None:passelse:current=current.nextself.head=currentelse:#删除尾节点count=0while current:count+=1if count==index-1:current.next=Nonebreakelse:current=current.nextreturn self.headif __name__=='__main__':data=[1,2,3,4]#定义一个链表a=LinkedList()a.create(data)#打印一个链表a.display()#链表的长度a.Len_Link()#插入一个节点a.insert(3,15)a.display()#插入一个节点a.insert(1,10)a.display()#定义一个空链表a=LinkedList()a.insert(1,100)a.display()#在尾部插入一个节点a.insert(2,1000)a.display()a.insert(1,10)a.display()#删除头部节点a.remove(1)a.display()#删除尾部节点a.remove(2)a.display()