双向链表：每个个节点有两个链表；一个指向前一个节点，当此节点为第一个时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值


双链表 - 图1

双链表的操作

方法名 说明
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos,item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在

构造节点

  1. class Node(object):
  3.     def __init__(self,item):构造函数初始化
  5.         self.prev=None  #定义前驱节点
  7.         self.elem=item  #定义传入的值数据区
  9.         self.next=None  #定义后继节点

链表的构造

  2. class DoubleLinkList(object):
  3.     def __init__(self,node=None):
  4.         self.__head=node

方法与单链表类似

1.判断链表是否为空

  2.     def is_empty(self):
  3.         return (self.__head==None)

方法与单链表类似

2.计算链表长度

  1. def length(self):
  2.     cur = self.__head
  3.     count=0
  4.     while cur != None:
  5.         count+=1
  6.         cur=cur.next
  7.     return count

方法与单链表类似

3.遍历链表

  1. def travel(self):
  2.     cur = self.__head
  3.     while cur != None:
  4.         print(cur.elem)
  5.         cur=cur.next

方法与单链表类似

4.尾部添加元素

尾部插入也和单链表类似，需要创建一个指针，进行循环

  1. 将尾结点指向node的next指向新节点node
  2. 再将节点的prev指向前一个节点（cur所指向的）

双链表 - 图2

  1. def append(self,item):
  2.     node=Node(item)
  3.     cur=self.__head
  4.     while cur.next !=None: #注意是cur.next
  5.         cur=cur.next
  6.     #找到了。就赋值    
  7.     cur.next=node
  8.     node.prev=cur

特殊情况

当链表为空时

插入的节点就是头节点
可以调用is_empty()函数来判断是否为空

  1. def append(self,item):
  2.     node=Node(item)
  3.     if self.is_empty():
  4.         self.__head=node
  5.     else:
  6.         while cur.next !=None:
  7.             cur=self.__head
  8.             cur=cur.next
  11.         cur.next=node
  12.         node.prev=cur

5.头部添加元素

方法一：

  1. 将传入节点next于指向头节点所指向的节点

双链表 - 图3

  1. 再将头节点指针指向新建节点

双链表 - 图4

  1. 最后将头节点所指向的节点的prev（后继节点）指向传入的节点

双链表 - 图5

  1. def add(self,item):
  3.     node=Node(item)
  5.     node.next=self.__head
  7.     node.next.prev=node
  8.    # slef.__head.prev=node
  10.     self.__head=node

特殊情况

当链表为空时

插入的节点就是头节点
可以调用is_empty()函数来判断是否为空

  1. def add(self,item):
  2.     #创建节点
  3.     node=Node(item)
  4.     if self.is_empty():
  5.         self.__head=node
  6.     else
  7.         node.next=self.__head
  8.         self.__head=node
  9.         node.next.prev=node

6.指定位置添加元素

单链表类似，但不同的是，双链表有前驱，可以找到上一个节点，所以不需要再定义指针prev

基本思路：

  1. 将传入的节点next指向cur

双链表 - 图6

  1. 将插入的节点的前驱指向cur的前驱prev

双链表 - 图7

  1. 打断原本的链接，将前面的节点的next指向插入的node

双链表 - 图8

  1. 再将cur的前驱prev指向插入的节点

双链表 - 图9

  1. def insert(self,pos,item):
  2.     node=Node(item)
  3.     cur=self.__head
  4.     count=0
  5.     while count < (pos-1):
  6.         count+=1
  7.         cur=cur.next
  9.     node.next=cur
  10.     node.prev=cur.prev
  11.     cur.prev.next=node
  12.     cur.prev=node

特殊情况

  • 当插入的数为负数pos<=0

    • 调用头插法self.add()

  • 当插入的数大于链表的长度（尾节点）pos>length()-1【0开始，长度为length-1】

    • 注意位置≠链表长度【pos=length()-1：就代表时pos-1处断开节点】
    • 调用尾插法self.append()

  • 这时的没有所谓的pre指针，所有插入条件也不需要为pos-1作为条件；双链表有前驱节点可以直接向，所以插入时候，直接在pos的位置插入，即当count=pos，就进行插入操作

    1. def insert(self,pos,item):
    2.   node=Node(item)
    3.   if pos<=0:
    4.       self.add(item)
    6.   elif  pos >self.length()-1:
    7.       self.append(item)
    9.   else:
    10.       count=0
    11.       cur=self.__head
    12.       while count <pos:
    13.           count+1
    14.           cur=cur.next
    16.       node.next=cur
    17.       node.prev=cur.prev
    18.       cur.prev.next=node
    19.       cur.prev.node

7.查找元素

与单链表类似

  1. def search(self,item):
  2.     cur=self.__head
  3.     while cur != None:
  4.         if cur.elem==item:
  5.             return True
  6.         else:
  7.             cur=cur.next
  8.     return False

8.删除节点

基本思路：

定义指针cur
双链表 - 图10

当删除的数是cur所指
双链表 - 图11

把cur的前节点指向cur的后节点
双链表 - 图12

把cur的后节点指向cur的前节点
双链表 - 图13

  1. def remove(self,item):
  2.     cur=self.__head
  3.     while cur != None:
  4.         if cur.elem==item:
  5.             cur.prev.next=cur.next
  6.             cur.next.prev=cur.prev
  7.             break
  9.         else:
  10.             cur=cur.next

特殊情况

当删除的是首节点

情况1：当是首节点

需要判要删除节点的后一个节点是否存在
存在就按照基本思路解决
不存在就不要写cur.next.prev=None

双链表 - 图14
双链表 - 图15

  1. def remove(self, item):
  2.     cur=self.__head
  4.     while cur !=None:
  6.         if cur.elem==item:
  8.             if self.__head==cur:   
  9.                 slef.__head=cur.next
  10.                 if cur.next:
  11.                     cur.next.prev=None
  13.             else:
  14.                 cur.prev.next=cur.next
  15.                 cur.next.prev=cur.prev
  16.             break
  18.         else:
  19.             cur=cur.next

情况2：当删除的节点时最后的节点

需要判要删除节点的后一个节点是否存在
存在就按照基本思路解决
不存在就不要写cur.next.prev=None
双链表 - 图16
双链表 - 图17

  1. def remove(self,item):
  2.     #定义cur
  3.     cur=self.___head#指向头节点
  4.     while cur !=None: #循环找
  6.         if cur.elem==item:  #找到了
  7.             if cur ==self.__head:    #找到的是头节点
  8.                 self.__head=cur.next
  10.                 if cur.next:        #cur.next不为None
  11.                     cur.next.prev=None
  13.             else:   #找到的不是头节点（尾结点或中间节点）  
  14.                 cur.prev.next=cur.next
  16.                 #找到的不是尾结点
  17.                 if    cur.next:
  18.                     cur.next.prev=cur.prev
  20.              break
  24.         else:
  25.             cur=cur.next   #没找到，直接移到下一位