简介：
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双向链表
节点：
class Node():
""" 节点 """
def __int__(self,item):
self.itme = item
self.next = next
双向链表:
.class Single_cycle_link_list(object,SingleLinkList):
“”“单向循环链表”“”
def __init__(self,node=None):
self.__head = node
if node: #如果节点不为空，则节点后继指向链表头，完成循环
ode.next = self.__head
判空方法：
def is_empty(self):
“”“判断链表是否为空”“”
:return: self.__head == None
求链表长度：
def length(self):
“”“返回链表长度”“”
if self.is_empty():
return True
else:
cur = self.__head
count = 1
while cur.next != self.__head: #如果游标不等于链表头，一直偏移数数
count += 1
cur = cur.next
return count
打印元素展示
def travel():
“”“打印链表元素”“”
if self.is_empty():
return None
cur = self.__head # 游标
while cur.next != self.__head:
print(cur.elem,end='')
cur = cur.next
print(cur.elem) #退出循环，游标偏移停止的时候，再打印最后的元素
尾部插入：
def append(self,item):
“”“尾部插入”“”
node = Node()
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head
while cur.next != self.__head: #游标位置未指向头结点，则继续偏移
cur = cur.next
node.next = self.__head #退出循环后，游标位置则为最后
cur.next = node
头插法：
def add(self,item):
“”“头部插入元素”“”
node = Node() #实例化节点
if self.is_empty: #如果是空链表则：空节点next指向头结点
self.__head = node
node.next = self.__head
else:
while cur.next != self.__head: #只要指针不是指向首节点
cur = cur.next #开始偏移
#当退出循环，游标cur当前指向是尾节点
node.next = self.__head
位置插入:
def insert(self,pos,item):
""索引位置进行插入""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1)::
self.append(item)
else:
cur = self.__head
count = 0
while count < pos:
count += 1
cur = cur.next #偏移到末尾
node = Node(item)
node.next = cur
node.perv = cur.perv
cur.perv.next = cur.perv
cur.perv = node
查找元素：
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
#如果单节点，且next是指向首节点，则不进入循环，再加判断
if cur.elem == item:
return True
return False
删除元素
def remove(self,pos,item):
“”“删除元素”“”
cur = self.__head
per = None
while cur.next != self.__head： #如果游标的next不是指向链表头（尾节点），则进入循环偏移
if cur.elem == item: #如果游标指向的元素恰巧是传入的参数
if cur == self.__head： #再判断是不是头节点
self.__head = cur.next
else: #中间节点的情况
per.next = cur.next
break
else:
#如果不是指向传入的参数，游标per指向游标curs
per = cur
cur = cur.next
#直到退出循环，游标遍历位置是指向尾节点
if cur.elem == item: #如果是尾节点，是不会进入上面的循环，再加判断
if cur == self.__head: #如果只有一个节点
self.__head = None
else:
pre.next = cur.next
网友评论