链表基础知识
链表是在物理内存中不连续，数据通过链表中的指针来链接到下一个元素。
链表由一系列节点组成，节点在运行时动态生成，节点一般包括两个部分：存储数据的数据域，存储下一个节点的指针域
链表的常用操作：节点的插入和删除。节点一般包括一个根节点，其他节点都是根据根节点生成。
单链表
# 链表的创建
#第一次加入加入节点，链表为空 ，第二次加入节点，先找到原有链表的最后一个节点
# 怎么判断到最后一个节点，但节点指向为空的时候则判断该节点为最后一个节点
# 节点类
class ListNode:
def __init__(self,val=0,next=None):
self.val=val
self.next=next
class LinkedList:
# 初始化
def __init__(self):
self.head=None #头节点指向为空
# 创建一个链表
def create(self,data):
self.head=ListNode(0) #定义一个头节点
cur=self.head
for i in range(len(data)):
node=ListNode(data[i]) #一个新的节点
cur.next=node #头节点指向新的节点
cur=cur.next #更新
# 获取链表的长度
def length(self):
count=0
cur=self.head #当前节点
while cur: #遍历节点，当节点为None的时候表示当前节点为空
count+=1
#更新节点
cur=cur.next
return count
# 添加元素
def insert(self,index,val):
#在头部 尾部 中间添加
#首先定义一个新的节点
node=ListNode(val)
if index==0:
#表示在头部插入元素
node.next=self.head
self.head=node
elif index==self.length()-1:
# 表示在尾部插入元素
#定义一个指针表示当前节点
cur=self.head #当前节点从头节点开始
while cur.next:
cur=cur.next
cur.next=node
elif index>0 and index<self.length()-1:
#在中间插入节点
cur=self.head
count=0
while cur and count<index-1: #当前节点不是尾节点
count+=1
cur=cur.next
node.next=cur.next
cur.next=node
else:
print('插入位置超出索引')
#删除元素
def remove(self,index):
pass
#修改元素
def change(self,index,val):
pass
#打印链表
def display(self):
cur=self.head
count=0
while cur:
print('第{}个节点，值为{}'.format(count,cur.val))
count+=1
cur=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=node
else:
current.next=node
current=current.next
return self.head
#打印链表的长度
def Len_Link(self):
count=0
current=self.head
while(1):
if current is not None: #判断是不是尾节点，如果不是则链表长度加1
count+=1
current=current.next
else:
break
# print('共有{}个节点'.format(count))
return count
#打印链表
def display(self):
print('开始打印链表')
current=self.head
count=0
while current:
count+=1
print("第{}个节点".format(count),current.data)
current=current.next
#插入一个节点
def insert(self,index,data):
lenth=self.Len_Link()
node=ListNode(data)
current=self.head
if index==0+1:
#插入头节点
if current :
#头节点不为空
node.next=current
self.head=node
else:
#头节点为空
self.head=node
elif index==lenth+1:
#在尾部插入节点
while current:
if current.next is None:
current.next=node
break
else:
current = current.next
elif index<=lenth and index>0:
count=0
while current:
count+=1
if count==index:
node.next=current.next
current.next=node
break
else:
current=current.next
return self.head
def remove(self,index):
#删除一个节点
#删除头节点
lenth=self.Len_Link()
current=self.head
if index==1:
if current is None:
pass
else:
current=current.next
self.head=current
else:
#删除尾节点
count=0
while current:
count+=1
if count==index-1:
current.next=None
break
else:
current=current.next
return self.head
if __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() 
参考：
链表基础知识详解（非常详细简单易懂）-CSDN博客
链表python基础知识_python链表长度-CSDN博客
Python编写单链表_python 单链表是什么-CSDN博客
