定义

一种更复杂的链表是“双向链表”或“双面链表”、每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
image.png

功能实现

  1. 结点定义

    1
    2
    3
    4
    5
    class Node(object):
        def __init__(self,item):
            self.item = item
            self.next = None #后指针
            self.prev = None #前指针

  2. 链表初始化

    1
    2
    3
    class DoubleLinkList(object):
        def __init__(self):
            self.__head = None

  3. 判断是否为空

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

  4. 判断链表长度

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

  5. 遍历链表

    1
    2
    3
    4
    5
    6
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.item,end=" ")
            cur = cur.next
        print()

  6. 头部添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def add(self,item):
        #头部插入
        #首先创建结点
        node = Node(item)
        # 判断是否是空列表
        if self.is_empty():
            self.__head = node
        else:
            # node结点的next指向原本的头结点
            node.next = self.__head
            # 先前头结点的前指针指向node
            self.__head.prev = node
            # __head指向node
            self.__head = node

  7. 尾部添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def append(self,item):
        # 首先创建节点
        node = Node(item)
        # 判断是否是空链表
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            # 找到最后一个节点
            while cur.next != None:
                cur = cur.next
            # 前一个节点的next指向node节点
            cur.next = node
            # node的 前指针指向前一个节点
            node.prev = cur

  8. 指定位置添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    def insert(self,pos,item):
        # 首先判断位置
        # 如果插入的位置在最前面
        if pos <0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            # 首先创建当前节点
            node = Node(item)
            cur = self.__head
            count = 0
            # 移动到当前位置的前一个节点
            while count < pos-1:
                count += 1
                cur = cur.next
            # node的前指针指向前一个节点
            node.prev = cur
            # node的后指针指向后一个节点
            node.next = cur.next
            # 前一个节点的后指针指向node节点
            cur.next = node
            # 后一个节点的前指针指向node节点
            cur.next.prev = node

  9. 查找元素

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

  10. 删除元素 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def remove(self,item):
        cur = self.__head
        while cur != None:
            # 如果是头节点
            if cur.item == item:
                if cur == self.__head:
                    # __head 直接指向头节点的下一个节点
                    self.__head = cur.next
                    # 判断链表是否只有一个节点
                    if cur.next:
                        cur.next.prev = None
                    # __head 直接指向头节点的下一个节点
                else:
                    cur.prev.next = cur.next
                    # 如果是最后一个节点的话,cur.next为none，不存在prev
                    if cur.next:
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

  11. 测试用例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    if __name__ == '__main__':
        doubleLinkList=DoubleLinkList()
        doubleLinkList.add(11)
        doubleLinkList.add(22)
        doubleLinkList.add(33)
        doubleLinkList.travel()
        print('-----------追加-----------')
        doubleLinkList.append(100)
        doubleLinkList.append(200)
        doubleLinkList.append(300)
        doubleLinkList.travel()
        print('指定位置插入')
        doubleLinkList.insert(-1,44)
        doubleLinkList.travel()
        doubleLinkList.insert(100,400)
        doubleLinkList.travel()
        doubleLinkList.insert(2,1000)
        doubleLinkList.travel()
        print('------删除节点--------')
        doubleLinkList.remove(44)
        doubleLinkList.travel()
        doubleLinkList.remove(1000)
        doubleLinkList.travel()
        doubleLinkList.remove(400)
        doubleLinkList.travel()
        print('链表的长度：',doubleLinkList.length())
        print('查找节点 11',doubleLinkList.search(11))
        print('查找节点 111',doubleLinkList.search(111))

    image.png