python双向链表的实现

1. 什么是双向链表

在计算机科学中，双向链表（Doubly linked list）是一种链表，它的每个结点都包含两个指向前一个结点和后一个结点的指针。双向链表可以从头到尾或从尾到头遍历链表，在某些情况下，双向链表比单向链表更加方便。

1.1 单向链表与双向链表的区别

单向链表是线性表的一种常见数据结构，每个结点只有一个指针指向下一个结点。但是在双向链表中，一个结点包含两个指向相邻节点的指针，一个指向前一个结点，一个指向后一个结点。如下图所示：

class Node:

    def __init__(self, data):
        self.data = data
        self.nextNode = None
        self.prevNode = None

其中prevNode是指向前一个结点的指针。

2. 双向链表的实现

2.1 双向链表结构

双向链表具有三个成员变量：头结点、尾结点和链表长度。下面是其结构定义：

class DoubleLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

其中head和tail分别指向链表的头结点和尾结点。

2.2 双向链表插入元素

在双向链表中插入元素，首先需要找到插入位置的前一个结点，然后将前一个结点的nextNode指向插入结点，插入结点的prevNode指向前一个结点，插入结点的nextNode指向插入位置的后一个结点。

def insert(self, position, data):

    if position < 0 or position > self.length:
        raise IndexError('position out of range')
    newNode = Node(data)
    if self.length == 0:
        self.head = newNode
        self.tail = newNode
    elif position == 0:
        newNode.nextNode = self.head
        self.head.prevNode = newNode
        self.head = newNode
    elif position == self.length:
        newNode.prevNode = self.tail
        self.tail.nextNode = newNode
        self.tail = newNode
    else:
        currentNode = self.head
        for i in range(position - 1):
            currentNode = currentNode.nextNode
        newNode.nextNode = currentNode.nextNode
        newNode.prevNode = currentNode
        currentNode.nextNode.prevNode = newNode
        currentNode.nextNode = newNode
    self.length += 1

以下是各个情况的插入操作：

1. 空链表插入元素

list = DoubleLinkedList()

list.insert(0, 2)
print(list.head.data) #2

2. 在链表的头部插入元素

list = DoubleLinkedList()

list.insert(0, 2)
list.insert(0, 1)
print(list.head.data) #1

3. 在链表的尾部插入元素

list = DoubleLinkedList()

list.insert(0, 2)
list.insert(1, 3)
print(list.tail.data) #3

4. 在链表的中间插入元素

list = DoubleLinkedList()

list.insert(0, 1)
list.insert(1, 3)
list.insert(1, 2)
print(list.head.nextNode.data) #2

2.3 双向链表删除元素

在双向链表中删除元素，首先需要找到要删除的结点，然后将删除结点的前一个结点的nextNode指向删除结点的后一个结点，删除结点的后一个结点的prevNode指向删除结点的前一个结点。

def delete(self, position):

    if position < 0 or position >= self.length:
        raise IndexError('position out of range')
    if position == 0:
        self.head = self.head.nextNode
        if self.length == 1:
            self.tail = None
        else:
            self.head.prevNode = None
    elif position == self.length - 1:
        self.tail = self.tail.prevNode
        self.tail.nextNode = None
    else:
        currentNode = self.head
        for i in range(position):
            currentNode = currentNode.nextNode
        currentNode.prevNode.nextNode = currentNode.nextNode
        currentNode.nextNode.prevNode = currentNode.prevNode
    self.length -= 1

以下是各个情况的删除操作：

1. 删除唯一的元素

list = DoubleLinkedList()

list.insert(0, 2)
list.delete(0)
print(list.length) #0

2. 删除头部元素

list = DoubleLinkedList()

list.insert(0, 1)
list.insert(1, 2)
list.delete(0)
print(list.head.data) #2

3. 删除尾部元素

list = DoubleLinkedList()

list.insert(0, 1)
list.insert(1, 2)
list.delete(1)
print(list.tail.data) #1

4. 删除中间元素

list = DoubleLinkedList()

list.insert(0, 1)
list.insert(1, 2)
list.insert(2, 3)
list.delete(1)
print(list.head.nextNode.data) #3

2.4 双向链表遍历

在双向链表中遍历时可以从头部向尾部遍历，也可以从尾部向头部遍历。以下代码展示了如何从头部向尾部遍历：

def traverse(self):

    currentNode = self.head
    while currentNode != None:
        print(currentNode.data)
        currentNode = currentNode.nextNode

以下代码展示了如何从尾部向头部遍历：

def reverseTraverse(self):

    currentNode = self.tail
    while currentNode != None:
        print(currentNode.data)
        currentNode = currentNode.prevNode

3. 总结

双向链表是一种线性数据结构，其每个结点包含指向前一个结点和后一个结点的指针。双向链表可以从头到尾或从尾到头遍历链表，在某些情况下，双向链表比单向链表更加方便。双向链表支持插入、删除和遍历等操作。在插入和删除时需要注意指针的指向。