双链表的每个节点都有两个指针，一个指向直接后继，一个指向直接前驱。在双向链表的任意一个节点都能很方便的访问其前后节点。其基本结构如下：
双向链表结构图
1.构造双向循环链表
双向链表和单向链表只有在insert、append、remove、add方法上有差别，因此这里可以使用面向对象的思想，继承于单向链表，然后重写这四种方法。
1.1 构造节点
双向链表的节点比单向链表多一个prev指针指向前一个节点
# 定义节点
class Node(object):
"""节点"""
def __init__(self,item):
self.elem = item
self.next = None
self.prev = None
1.2 重写add函数【头插法】
作用：在链表头部添加元素
- 传入的item不是节点类型，因此需要使用Node将其转为节点。实例为node对象
- 让node指向下一个元素的指针指向当前的头节点，即self.__head。node.next = self.__head
- 将self.__head赋值为node。self.__head = node
-
让node的下一个节点的prev指针指向node【与单向链表的区别】
【注意】 - 必须先让node的下一个指针先指向当前的头节点，然后重新设置node为头节点
add函数图解
def add(self,item):
"""头部添加"""
node = Node(item)
node.next = self.__head
self.__head = node
node.next.prev = node # 让node的下一个节点的前一个节点指向node
1.3 重写insert函数
作用：在指定位置插入元素
- 创建一个cur游标,起使指向头节点的位置，即cur = self.__head
- 创建一个计数器count，用于记录索引后和pos比较
- 当count移动到pos位置【区别于单向链表移动到pos-1位置，因为存在前后指针，所以可以移动到pos位置】
- 找到pos位置后，将node的next指针指向cur当前节点；将cur当前节点的next指针指向node，node的prev指针指向cur的prev节点【先操作node，不改变原链表结构】
- 让node的prev指针指向当前cur所在节点的prev节点
- 让cur所在节点的前一个节点的next指针指向node
- 让cur当前节点的prev指针指向node
【注意】 - 当输入的pos<=0时，视为其在头部插入，直接调用add方法
- 当输入的pos>链表的长度时，视为在尾部，直接调用append方法
insert函数图解
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
# 游标直接走到pos的位置
while count < pos :
count += 1
cur = cur.next
# 当循环推出后，cur指向pos的位置
node = Node(item)
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
1.4 重写append函数【尾插法】
作用：在链表尾部添加元素
- 创建一个cur游标，起使指向头节点的位置，即cur = self.__head
- 当cur.next为None时，则处于最后一个节点，因此遍历条件为 while cur.next!=None
- 让cur游标遍历到链表最后一个节点的位置，让当前节点next指针指向node
- 让node的prev指针指向cur【与单向链表的区别】
【注意】 - 当链表为空时，不存在cur.next，因此需要考虑链表为空的情况
-
当链表为空时，直接将当前的头节点赋值为node
append函数图解
def remove(self,item):
"""删除节点"""
cur = self.__head
while cur != None:
if cur.elem == item:
# 先判断此节点是否是头节点
self.__head = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = None
else:
cur.prev.next = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = cur.prev
break
else:
cur = cur.next
1.5 重写remove函数
作用：删除指定位置元素
- 遍历链表【while cur != None】,如果当前节点不是要删除的节点，则移动cur
- 当cur指向的元素等于要删除的元素相等时，先判断是否是头节点，如果是头节点，直接让self.__head = cur.next，让cur.next.prev指向None【由于cur.next不一定存在，因此需要添加判断条件if】
- 如果不为头节点，则让cur的前一个结点的next指针指向cur的下一个节点cur.prev.next = cur.next；让cur的下一个节点的prev指针指向cur的前一个节点 cur.next.prev = cur.prev【由于cur.next不一定存在，因此需要添加判断条件if】
【注意】 - 如果要删除的节点为头节点，即cur处于head的位置，则直接让头节点指向cur的下一个节点即可
remove函数图解
def remove(self,item):
"""删除节点"""
cur = self.__head
while cur != None:
if cur.elem == item:
# 先判断此节点是否是头节点
self.__head = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = None
else:
cur.prev.next = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = cur.prev
break
else:
cur = cur.next
2.完整代码
# 双向链表可以先继承单向链表，然后重写add、travel、append、remove方法
class DoubleLinkList(SingleLinklist):
def add(self,item):
"""头部添加"""
node = Node(item)
node.next = self.__head
self.__head = node
node.next.prev = node # 让node的下一个节点的前一个节点指向node
def append(self,item):
"""尾部添加元素，只比单链表的append方法多一行代码"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head()
while cur.next != None:
cur = cur.next
cur.next = node
node.prev = cur
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
# 游标直接走到pos的位置
while count < pos :
count += 1
cur = cur.next
# 当循环推出后，cur指向pos的位置
node = Node(item)
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
def remove(self,item):
"""删除节点"""
cur = self.__head
while cur != None:
if cur.elem == item:
# 先判断此节点是否是头节点
self.__head = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = None
else:
cur.prev.next = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = cur.prev
break
else:
网友评论