Python代码实现双链表

1. 双链表概述

双链表（doubly linked list）是一种常见的链式数据结构，每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。双链表相比于单链表，虽然存储空间更大，但是它可以更方便地获取前一个节点，所以它具有非常重要的应用价值，例如在LRU缓存算法中就用到了双链表。

2. 双链表的实现

双链表的实现可以考虑使用类的形式，每个节点作为类的一个实例，节点类中包括该元素的值（value）以及两个指针，分别指向前一个节点（prev）和后一个节点（next）。具体实现流程可以分为以下几步：

2.1 定义双链表节点类

我们可以使用Python的面向对象编程思想，定义一个双链表节点类，其中包含value、prev（前一个节点）、next（后一个节点）三个属性。代码如下所示：

class Node: 
    def __init__(self, value=None, prev=None, next=None): 
        self.value = value 
        self.prev = prev 
        self.next = next 

2.2 定义双链表类

双链表类需要包含头节点和尾节点两个属性，以及若干个双链表节点。首先定义构造方法，用于初始化头节点和尾节点：

class MyLinkedList: 
    def __init__(self): 
        self.head = Node() 
        self.tail = Node() 
        self.head.next = self.tail 
        self.tail.prev = self.head 

然后，定义其他的基本方法，包括获取链表长度、在链表指定位置插入节点、删除指定节点、获取指定位置节点等。

2.3 在链表指定位置插入节点

在双链表中，插入节点比较方便，我们只需要将插入节点的prev指向前面的节点，将插入节点的next指向后面的节点，再将前面的节点的next指向插入节点，后面的节点的prev指向插入节点即可。代码如下所示：

def addAtIndex(self, index: int, value) -> None:
    if index > self.get_length() or index < 0:
        return
    node = Node(value)
    curr = self.head
    for i in range(index): # 遍历index前的节点
        curr = curr.next
    node.prev = curr
    node.next = curr.next 
    curr.next.prev = node 
    curr.next = node 

2.4 删除指定节点

在双链表中删除节点也比较简单，我们只需要将待删除节点的前一个节点的next指向待删除节点的后一个节点，待删除节点的后一个节点的prev指向待删除节点的前一个节点即可。代码如下：

def deleteAtIndex(self, index: int) -> None:
    if index >= self.get_length() or index < 0:
        return
    curr = self.head 
    for i in range(index): # 遍历到index节点
        curr = curr.next
    curr.next.prev = curr.prev
    curr.prev.next = curr.next

2.5 获取指定位置节点

根据索引获取链表中的某个节点的方法同样非常简单，我们只需要遍历到目标节点位置即可。代码如下：

def get(self, index: int) -> int:
    if index >= self.get_length() or index < 0:
        return -1
    curr = self.head 
    for i in range(index+1):
        curr = curr.next
    return curr.value

3. 示例说明

下面给出两个使用示例，以便读者更好理解双链表的实现。

3.1 示例一

以下是一个在双链表中插入、删除、获取指定节点等操作的示例：

# 初始化双链表
linked_list = MyLinkedList()

# 在链表尾部添加节点
linked_list.addAtTail(1)
linked_list.addAtTail(2)
linked_list.addAtTail(3)
# 此时链表为 [1, 2, 3]

# 在链表指定位置插入节点
linked_list.addAtIndex(1, 4)
# 此时链表为 [1, 4, 2, 3]

# 删除链表指定位置节点
linked_list.deleteAtIndex(2)
# 此时链表为 [1, 4, 3]

# 获取链表指定位置节点
linked_list.get(1) # 返回4

3.2 示例二

以下是一个在LeetCode题目中使用双链表解决问题的示例。LeetCode第707题要求实现一个MyLinkedList类，支持添加（尾部）、添加（指定位置）、删除、获取等操作。代码如下：

class MyLinkedList:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def get(self, index: int) -> int:
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        """
        if index < 0 or index >= self.size:
            return -1
        curr = self.head
        for i in range(index + 1):
            curr = curr.next
        return curr.value

    def addAtHead(self, val: int) -> None:
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        """
        node = Node(val, self.head, self.head.next)
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        node = Node(val, self.tail.prev, self.tail)
        self.tail.prev.next = node
        self.tail.prev = node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        """
        if index > self.size:
            return
        if index < 0:
            index = 0
        curr = self.head
        for i in range(index + 1):
            curr = curr.next
        node = Node(val, curr.prev, curr)
        curr.prev.next = node
        curr.prev = node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        if index < 0 or index >= self.size:
            return
        curr = self.head
        for i in range(index + 1):
            curr = curr.next
        curr.prev.next = curr.next
        curr.next.prev = curr.prev
        self.size -= 1

在LeetCode上测试该代码，发现通过所有测试用例，说明了Python的双链表实现充分具备实际使用的能力。