python实现双向链表 -- 详细思路分析

双链表的每个节点都有两个指针，一个指向直接后继，一个指向直接前驱。在双向链表的任意一个节点都能很方便的访问其前后节点。其基本结构如下：

双向链表结构图

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: