概念

雙向鏈表（Double_linked_list）也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有
兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可
以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

實(shí)現(xiàn)

class Node:
    def __init__(self, data):
        self.data = data    # 數(shù)據(jù)域
        self.next = None    # 指針域(直接后繼)
        self.prev = None    # 指針域(直接前驅(qū))


class DoubleLinkedList:
    """
    雙向鏈表
    """

    def __init__(self):
        self._head = None

    # 判斷鏈表是否為空
    def is_empty(self):
        return bool(self._head)

    # 返回鏈表長度
    @property
    def size(self):
        current = self._head
        count = 0
        while current is not None:
            count += 1
            current = current.next
        return current

    # 遍歷鏈表
    def travel(self):
        current = self._head
        while current is not None:
            print(current.data)
            current = current.next

    # 在鏈表頭部插入元素
    def add(self, value):
        new_node = Node(value)
        if self.is_empty():
            self._head = new_node
        else:
            new_node.next, self._head.prev = self._head, new_node
            self._head = new_node

    # 在鏈表尾部插入元素
    def append(self, value):
        new_node = Node(value)
        if self.is_empty():
            self._head = new_node
        else:
            _current = self._head
            while _current.next is not None:
                _current = _current.next
            _current.next, new_node.prev = new_node, _current

    # 查找元素是否存在
    def search(self, value):
        _current = self._head
        while _current is not None:
            if _current.data == value:
                return True
            _current = _current.next
        return False

    # 在指定位置插入節(jié)點(diǎn)
    def insert(self, position, value):
        if position < 0 or position > self.size:
            raise IndexError("Position out of range.")
        if position == 0:
            self.add(value)
        else:
            _node = Node(value)
            _current = self._head
            i = 0
            while i != position:
                i += 1
                _current = _current.next
            _prev = _current.prev
            _prev.next, _node.prev = _node, _prev
            _node.next, _current.prev = _current, _node

    # 刪除指定位置的節(jié)點(diǎn)
    def remove(self, position):
        if self.is_empty():
            return None
        if position < 0 or position > self.size - 1:
            raise IndexError("Position out of range.")
        _current = self._head
        i = 0
        while i != position:
            i += 1
            _current = _current.next
        _prev = _current.prev
        _next = _current.next
        _prev.next, _next.prev = _next, _prev
        _current.next, _current.prev = None, None