python链表之双向链表实战

上篇文章说到了单链表，这次是双链表，单链表可参考文章末尾链接。

它包含了三个域，一个用于存储上一个节点的地址(直接前驱)，一个用于数据存储，一个指向下一个节点(直接后继)，而最后一个节点的直接后继指向None，最前面的直接前驱指向None。

链表包含：单向链表、双向链表、循环链表、块状链表

链表中双向链表结构图：

实践代码：

# -*- encoding: utf-8 -*-
"""
@File    : doubleLinkedList
@Author  : TopAbu.com
@Software: IntelliJ IDEA
"""


class Node(object):
    name = '节点类'

    def __init__(self, item):
        self.item = item
        self.pre = None
        self.next = None

    def __repr__(self):
        return str(self.item)


class DoubleLinkedList(object):
    name = '双向链表'

    def __init__(self):
        self.__head = None

    def is_empty(self):
        '''判断是否为空'''
        return self.__head is None

    def length(self):
        '''返回链表长度'''
        cur = self.__head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        '''遍历链表，返回链表所有item'''
        cur = self.__head
        while cur is not None:
            print(cur.item)
            cur = cur.next

    def search(self, item):
        '''查找某一参数是否在列表中'''
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

    def add(self, item):
        '''
        向链表头部增加元素
        链表中的head指向新增加的节点
        新节点指向后续节点
        后续节点指向新节点
        '''
        node = Node(item)
        node.next = self.__head
        if self.__head is not None:
            self.__head.pre = node
        self.__head = node

    def append(self, item):
        '''向链表尾部添加节点'''
        node = Node(item)
        if self.is_empty():
            self.__head = node
            return
        cur = self.__head
        while cur.next is not None:
            cur = cur.next
        cur.next = node
        node.pre = cur

    def insert(self, item, position):
        '''在指定位置添加一个元素'''
        if position <= 0:
            self.add(item)
        elif position > (self.length() - 1):
            self.append(item)
        else:
            count = 0
            cur = self.__head
            node = Node(item)
            while count < position:
                cur = cur.next
                count += 1
            node.next = cur
            node.pre = cur.pre
            cur.pre.next = node
            cur.pre = node

    def remove(self, item):
        '''删除链表中的元素'''
        cur = self.__head
        pre = None
        while cur is not None:
            if cur.item == item:
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    if cur.next:
                        cur.next.pre = cur.pre
                    cur.pre.next = cur.next
                    cur.pre = None
                    cur.next = None
                return
            pre = cur
            cur = cur.next


if __name__ == '__main__':
    dl = DoubleLinkedList()
    print(dl.is_empty())
    dl.add(1)
    dl.travel()
    print(dl.is_empty())
    dl.add('a')
    dl.travel()
    print('*'*20)
    dl.append('last')
    dl.travel()
    print('*'*20)
    dl.insert('topabu.com', 2)
    dl.travel()
    print('*'*20)
    dl.remove('last')
    dl.travel()

参考链接：python链表之单向链表实践