Python数据结构之双向链表详解

什么是双向链表？

在计算机科学中，双向链表是链表的一种，每个结点除了储存下一个结点的指针外，还储存着前一个结点的指针。这个“前进”指针被称为“ next指针”，而“后退”指针被称为“previous指针”。

双向链表和单向链表的区别在于，单向链表的每个结点只储存一个指向下一个结点的指针，而双向链表储存了前一个和后一个结点的指针。

双向链表的基本形式

下面是一个基本的双向链表结构的代码示例：

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

其中，Node类表示链表的结点，包含属性data、next和prev。DoublyLinkedList类表示一个双向链表。在初始化时，它有一个头指针head，初始为None。

双向链表的基本操作

在链表头插入一个结点

从头部插入一个新节点需要执行以下步骤：

1. 创建一个新节点
2. 将新节点的next指针指向旧的头结点
3. 将旧的头结点的prev指针指向新节点
4. 将新节点赋值为头结点

示例如下：

def insert_at_beg(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

在链表尾插入一个结点

从尾部插入一个新节点需要执行以下步骤：

1. 创建一个新节点
2. 如果链表为空，将新节点赋值给头结点；否则找到链表的最后一个节点并将其next指向新节点
3. 将新节点的prev指针指向链表的最后一个节点

示例如下：

def insert_at_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        temp = self.head
        while(temp.next is not None):
            temp = temp.next

        temp.next = new_node
        new_node.prev = temp

在指定位置插入一个结点

在指定位置插入新节点需要执行以下步骤：

1. 创建一个新的节点
2. 找到要插入的位置
3. 将新节点的next指向插入位置的节点，将插入位置节点的prev指针指向新节点
4. 将新节点的prev指向插入位置的前一个节点，将前一个节点的next指针指向新节点

示例如下：

def insert_at_position(self, data, position):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    elif position == 0:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    else:
        temp = self.head
        for i in range(position-1):
            temp = temp.next
        new_node.next = temp.next
        new_node.prev = temp
        if temp.next is not None:
            temp.next.prev = new_node
        temp.next = new_node

删除链表头部结点

从链表头部删除一个节点需要执行以下步骤：

1. 判断链表是否为空
2. 如果链表长度为1，将头结点置为None
3. 否则，将头结点的下一个节点作为新的头节点，将新头节点的prev指针设置为None

示例如下：

def delete_at_beg(self):
    if self.head is None:
        return None
    if self.head.next is None:
        temp = self.head
        self.head = None
        return temp.data
    temp = self.head
    self.head = self.head.next
    self.head.prev = None
    return temp.data

删除链表尾部结点

从链表尾部删除一个节点需要执行以下步骤：

1. 判断链表是否为空
2. 如果链表长度为1，将头结点置为None
3. 否则，找到链表最后一个节点，将倒数第二个节点的next指针置为空

示例如下：

def delete_at_end(self):
    if self.head is None:
        return None
    if self.head.next is None:
        temp = self.head
        self.head = None
        return temp.data
    temp = self.head
    while(temp.next is not None):
        temp = temp.next
    temp.prev.next = None
    return temp.data

删除指定位置的结点

在指定位置删除节点需要执行以下步骤：

1. 判断链表是否为空
2. 如果删除的节点是头结点，将头节点的下一个节点作为新的头节点，并将新的头节点的prev指针置为空
3. 如果删除的节点是尾节点，将倒数第二个节点的next指针置为空
4. 否则，找到要删除的节点，并重置其前后节点的prev和next指针

示例如下：

def delete_at_position(self, position):
    if self.head is None:
        return None
    if position == 0:
        if self.head.next is None:
            temp = self.head
            self.head = None
            return temp.data
        temp = self.head
        self.head = self.head.next
        self.head.prev = None
        return temp.data
    else:
        count = 0
        temp = self.head
        while(temp is not None and count < position):
            temp = temp.next
            count += 1
        if temp is None:
            return None
        if temp.next is None:
            temp.prev.next = None
        else:
            temp.prev.next = temp.next
            temp.next.prev = temp.prev
        return temp.data

示例

插入元素

插入元素并打印链表

if __name__ == '__main__':
    dll = DoublyLinkedList()
    dll.insert_at_end(10)
    dll.insert_at_end(20)
    dll.insert_at_end(30)
    dll.insert_at_end(40)
    dll.insert_at_position(50, 2)

    temp = dll.head
    while(temp):
        print(temp.data, end=' ')
        temp = temp.next

输出：

10 20 50 30 40 

删除元素

删除元素并打印链表

if __name__ == '__main__':
    dll = DoublyLinkedList()
    dll.insert_at_end(10)
    dll.insert_at_end(20)
    dll.insert_at_end(30)
    dll.insert_at_position(15, 1)

    dll.delete_at_beg()
    dll.delete_at_position(1)
    dll.delete_at_end()

    temp = dll.head
    while(temp):
        print(temp.data, end=' ')
        temp = temp.next

输出：

20 

总结

双向链表的优势在于可以同时向前和向后遍历，但是相应的空间复杂度更高，需要在每个节点上维护prev指针。以上是双向链表的基本操作，仔细理解了这些操作，对于理解更为复杂的链表操作会有很大的帮助。