链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
链表的定义链表——一种常见的基础数据结构，与顺序表统称为线性表，但是不像顺序表一样连续存储数据，而是在每个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。
分为数据区和连接区：数据区存放数据，链接区存放下一个数据的地址。如图所示。
- 变量a是一个存储空间，当a=10时，10也放在另一个存储空间里面，a会指向10的地址。即：等号存在就是引用一个链接。然后a=f，其中f为一个函数，此时a就会重新指向函数f的地址。
- 若int a=10,那么就意味着10存放的存储空间的别名就是a。如果a再重新换值，值就必须为整型。
如图：
#coding=utf-8
class Node(object):
'''结点的类'''
def __init__(self,elem):
self.elem=elem #数据区，保存数据
self.next=None #链接区，下一结点的位置是未知的，所以初始定义为None。
pass
pass
#node=Node(100) #elem为100
class SingleLinkList(object):
'''单链表'''
def __init__(self,node=None):
self._head=node #私有属性，头结点信息
def is_empty(self):
'''链表是否为空'''
pass
def length(self):
'''链表的长度'''
pass
def travel(self):
'''遍历整个链表'''
pass
def add(self,item):
'''头部添加元素'''
pass
def append(self,item):
'''尾部添加元素'''
pass
def insert(self,pos,item):
'''指定位置添加元素'''
pass
def remove(self,item):
'''删除节点'''
pass
def search(self,item):
'''查找节点是否存在'''
pass
single_obj=SingleLinkList()
single_obj.travel()
single_obj.add()
关于单链表的操作处理
单链表的判空、长度、遍历、尾部添加结点的代码的实现
图形示例：
#coding=utf-8
class Node(object):
'''节点'''
def __init__(self,elem):
self.elem=elem
self.next=None
pass
pass
#node=Node(100)
class SingleLinkList(object):
'''单链表'''
def __init__(self,node=None):
self.__head=node #私有属性
def is_empty(self):
'''链表是否为空'''
return self.__head==None
pass
def length(self):
'''链表的长度'''
# cur游标，用来移动遍历结点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
pass
'''
若count=1：必须先判断链表是否为空
cur = self.__head
count=1
if cur=None:
count=1
else:
while cur.next !=None:
count += 1
cur = cur.next
return count
'''
def travel(self):
'''遍历整个链表'''
cur=self.__head
while cur !=None:
print(cur.elem,end=' ')
cur=cur.next
pass
def append(self,item):
'''尾部添加元素,item是具体的数据元素，并不是结点'''
node=Node(item)
cur=self.__head
if self.is_empty():
self.__head=node
else:
while cur.next !=None:
cur=cur.next
cur.next=node
pass
# node=100
# single_obj=SingleLinkList()
# single_obj.travel()
if __name__=='__main__':
ll=SingleLinkList()
print(ll.is_empty()) #判断链表是否为空
print(ll.length()) #判断链表长度
ll.append(1) #追加1
print(ll.is_empty()) # 判断链表是否为空
print(ll.length()) # 判断链表长度
ll.append(2) # 追加2
ll.append(3) # 追加3
ll.append(4) # 追加4
ll.append(5) # 追加5
ll.travel()
单链表头部添加和在指定位置添加
#coding=utf-8
class Node(object):
'''节点'''
def __init__(self,elem):
self.elem=elem
self.next=None
pass
pass
#node=Node(100)
class SingleLinkList(object):
'''单链表'''
def __init__(self,node=None):
self.__head=node #私有属性
def is_empty(self):
'''链表是否为空'''
return self.__head==None
pass
def length(self):
'''链表的长度'''
# cur游标，用来移动遍历结点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
pass
'''
若count=1：必须先判断链表是否为空
cur = self.__head
count=1
if cur=None:
count=1
else:
while cur.next !=None:
count += 1
cur = cur.next
return count
'''
def travel(self):
'''遍历整个链表'''
cur=self.__head
while cur !=None:
print(cur.elem,end=' ')
cur=cur.next
print('')
pass
def add(self,item):
'''头部添加元素，头插法'''
node=Node(item)
node.next=self.__head #先将新结点的链接区指向原有首结点
self.__head=node #后将__head指向新结点的数据区
pass
def append(self,item):
'''尾部添加元素,尾插法，item是具体的数据元素，并不是结点'''
node=Node(item)
cur=self.__head
if self.is_empty():
self.__head=node
else:
while cur.next !=None:
cur=cur.next
cur.next=node
pass
def insert(self,pos,item):
'''
指定位置添加元素
:param pos:指定位置，从0开始
:param item:所添加的数据
:return:
'''
node = Node(item)
if pos<=0:#默认头插法
self.add(item)
elif pos>(self.length()-1):
self.append(item)
else:
pre= self.__head
count=0
while count<(pos-1):
count+=1
pre=pre.next
pass
#当循环退出后，pre指向pos-1位置的数据区
node.next=pre.next
pre.next=node
pass
# node=100
# single_obj=SingleLinkList()
# single_obj.travel()
if __name__=='__main__':
ll=SingleLinkList()
print(ll.is_empty()) #判断链表是否为空
print(ll.length()) #判断链表长度
ll.append(1) #追加1
print(ll.is_empty()) # 判断链表是否为空
print(ll.length()) # 判断链表长度
ll.append(2) # 追加2
ll.add(8)
ll.append(3) # 追加3
ll.append(4) # 追加4
ll.append(5) # 追加5
ll.insert(-1,9)
ll.travel()
ll.insert(2,100)
ll.travel()
ll.insert(10,200)
ll.travel()
查找和删除元素
def remove(self,item):
'''删除节点,item是数据'''
cur=self.__head
pre=None
while cur!=None:
if cur.elem==item:
#先判断此结点是否为头结点
if cur==self.__head: #pre=None
self.__head=cur.next
pass
else:
pre.next=cur.next
break #删除后退出循环
else:
pre=cur
cur=cur.next #以上两步使得pre=cur.next
pass
def search(self,item):
'''查找节点是否存在'''
cur=self.__head
while cur !=None:
if cur.elem==item:
return True
else:
cur=cur.next
return False
pass
ps:后继结点——一个当前结点的下一个结点
单链表与顺序表的对比- 单链表头插法/删除元素时间复杂度O(1)
顺序表在头部插入元素/删除元素时间复杂度为O(n) - 单链表尾插法/删除元素时间复杂度O(n)
顺序表在尾部插入元素/删除元素时间复杂度为O(1) - 单链表访问元素时间复杂度为O(n)
顺序表访问元素时间复杂度为O(1) - 单链表指定位置添加/删除元素时间复杂度O(n)，n花费在遍历上
顺序表指定位置添加/删除元素时间复杂度O(n)，n花费在数据搬迁上
两者的优缺点：
（1）顺序表
优点：存储元素时可通过O(1)方式一次性定位。
缺点：空间必须是连续的，如果动态改变，存储区必须全部改变；而且一旦保存数据很大，顺序表就达不到要求。
（2）
优点：对分散或者离散的空间可以达到充分利用。
缺点：存储元素时达不到O(1)的效果。
#coding=utf-8
class Node(object):
'''节点'''
def __init__(self,elem):
self.elem=elem
self.next=None
pass
pass
#node=Node(100)
class SingleCircleLinkList(object):
'''单链表'''
def __init__(self,node=None):
self.__head=node #私有属性
if node:
node.next=node
def is_empty(self):
'''链表是否为空'''
return self.__head==None
pass
def length(self):
'''链表的长度'''
if self.is_empty(): #if cur==None:
return 0
# cur游标，用来移动遍历结点
cur = self.__head
# count记录数量
count = 1
while cur.next != self.__head:
count += 1
cur = cur.next
return count
pass
def travel(self):
'''遍历整个链表'''
if self.is_empty():
return
cur=self.__head
while cur.next !=self.__head:
print(cur.elem,end=' ')
cur=cur.next
#退出循环，cur指向尾结点，但尾结点的元素未打印
print(cur.elem)
pass
def add(self,item):
'''头部添加元素，头插法'''
node = Node(item)
if self.is_empty():
self.__head=node
node.next=node
else:
cur = self.__head
while cur.next!=self.__head:
cur=cur.next
# 退出循环，cur指向尾结点
node.next=self.__head #先将新结点的链接区指向原有首结点
self.__head=node #后将__head指向新结点的数据区
cur.next=node #再将尾结点指向新结点的数据区cur.next=self.__head
pass
def append(self,item):
'''尾部添加元素,尾插法，item是具体的数据元素，并不是结点'''
node=Node(item)
if self.is_empty():
self.__head=node
node.next=node
else:
cur=self.__head
while cur.next !=self.__head:
cur=cur.next
node.next=self.__head #node.next=cur.next
cur.next=node
pass
def insert(self,pos,item):
'''
指定位置添加元素
:param pos:指定位置，从0开始
:param item:所添加的数据
:return:
'''
node = Node(item)
if pos<=0:#默认头插法
self.add(item)
elif pos>(self.length()-1):
self.append(item)
else:
pre= self.__head
count=0
while count<(pos-1):
count+=1
pre=pre.next
pass
#当循环退出后，pre指向pos-1位置的数据区
node.next=pre.next
pre.next=node
pass
def remove(self,item):
'''删除节点,item是数据'''
if self.is_empty():
return
cur=self.__head
pre=None
while cur.next!=self.__head:
if cur.elem==item:
#先判断此结点是否为头结点
if cur==self.__head:
#头结点的情况
#找尾结点
rear=self.__head
while rear.next!=self.__head:
rear=rear.next
self.__head=cur.next
rear.next=self.__head
pass
else:
#中间结点
pre.next=cur.next
return #删除后不可以退出循环，还要执行下面的if操作
else:
pre=cur
cur=cur.next #以上两步使得pre=cur.next
# 退出循环，cur指向尾结点
if cur.elem==item:
if cur==self.__head: #链表只有一个结点
self.__head=None
else:
pre.next=cur.next
def search(self,item):
'''查找节点是否存在'''
if self.is_empty():
return False
cur=self.__head
while cur.next !=self.__head:
if cur.elem==item:
return True
else:
cur=cur.next
# 退出循环，cur指向尾结点
if cur.elem == item:
return True
return False
pass
# node=100
# single_obj=SingleLinkList()
# single_obj.travel()
if __name__=='__main__':
ll=SingleCircleLinkList()
print(ll.is_empty()) #判断链表是否为空
print(ll.length()) #判断链表长度
ll.append(1) #追加1
print(ll.is_empty()) # 判断链表是否为空
print(ll.length()) # 判断链表长度
ll.append(2) # 追加2
ll.add(8)
ll.append(3) # 追加3
ll.append(4) # 追加4
ll.append(5) # 追加5
ll.insert(-1,9)
ll.travel()
ll.insert(2,100)
ll.travel()
ll.insert(10,200)
ll.travel()
ll.remove(9)
ll.travel()
单向循环列表演示：
删除头结点：
