Algorithms 101: Deque Implementation Using Doubly Linked List

Deque Implementation Using Doubly Linked List (双端队列用双链表的实现)

A deque can be efficiently implemented using a doubly linked list. This approach allows constant-time insertions and deletions at both the front and rear of the deque. In a doubly linked list, each node contains three parts: the data, a pointer to the previous node, and a pointer to the next node. By maintaining pointers to both the head (front) and tail (rear) of the deque, we can implement all deque operations efficiently.

双端队列可以使用双链表高效地实现。这种方法允许在双端队列的前端和后端进行常数时间的插入和删除操作。在双链表中，每个节点包含三个部分：数据、指向前一个节点的指针和指向下一个节点的指针。通过维护指向队列头部（前端）和尾部（后端）的指针，我们可以高效地实现所有双端队列的操作。

Structure of the Node Class (节点类的结构):

Each node in the doubly linked list is represented by a Node class. The Node class has three attributes: data, prev, and next.

双链表中的每个节点由 Node 类表示。Node 类有三个属性：data、prev 和 next。

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

Structure of the Deque Class (双端队列类的结构):

The Deque class manages the doubly linked list by maintaining references to the head and tail of the list. It includes methods to insert and delete elements from both ends of the deque.

Deque 类通过维护对链表 head 和 tail 的引用来管理双链表。它包括从双端队列的两端插入和删除元素的方法。

class Deque:
    def __init__(self):
        self.head = None
        self.tail = None

    def isEmpty(self):
        return self.head is None

    def insertFront(self, data):
        new_node = Node(data)
        if self.isEmpty():
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def insertLast(self, data):
        new_node = Node(data)
        if self.isEmpty():
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def deleteFront(self):
        if self.isEmpty():
            return "Deque is empty"
        data = self.head.data
        self.head = self.head.next
        if self.head is not None:
            self.head.prev = None
        else:
            self.tail = None
        return data

    def deleteLast(self):
        if self.isEmpty():
            return "Deque is empty"
        data = self.tail.data
        self.tail = self.tail.prev
        if self.tail is not None:
            self.tail.next = None
        else:
            self.head = None
        return data

    def getFront(self):
        if self.isEmpty():
            return "Deque is empty"
        return self.head.data

    def getRear(self):
        if self.isEmpty():
            return "Deque is empty"
        return self.tail.data

Operations Explanation (操作说明):

Insert Front (插入前端):
- We create a new node and insert it at the front. If the deque is empty, both head and tail point to this new node. Otherwise, the new node is linked to the current head, and head is updated to the new node.
- 创建一个新节点并将其插入前端。如果双端队列为空，则 head 和 tail 都指向这个新节点。否则，新节点与当前 head 链接，并将 head 更新为新节点。
Big O Analysis:
- Time Complexity: O(1) – Insertion is done in constant time.
- Space Complexity: O(1) – No additional space is required beyond the new node.
Insert Last (插入后端):
- We create a new node and insert it at the rear. If the deque is empty, both head and tail point to this new node. Otherwise, the new node is linked to the current tail, and tail is updated to the new node.
- 创建一个新节点并将其插入后端。如果双端队列为空，则 head 和 tail 都指向这个新节点。否则，新节点与当前 tail 链接，并将 tail 更新为新节点。
Big O Analysis:
- Time Complexity: O(1) – Insertion is done in constant time.
- Space Complexity: O(1) – No additional space is required beyond the new node.
Delete Front (删除前端):
- We remove the node at the front of the deque. If the deque becomes empty after this operation, both head and tail are set to None. Otherwise, head is updated to the next node, and the previous pointer of the new head is set to None.
- 我们移除双端队列前端的节点。如果操作后双端队列为空，则 head 和 tail 都设置为 None。否则，head 更新为下一个节点，并将新 head 的前一个指针设置为 None。
Big O Analysis:
- Time Complexity: O(1) – Deletion is done in constant time.
- Space Complexity: O(1) – No additional space is required.
Delete Last (删除后端):
- We remove the node at the rear of the deque. If the deque becomes empty after this operation, both head and tail are set to None. Otherwise, tail is updated to the previous node, and the next pointer of the new tail is set to None.
- 我们移除双端队列后端的节点。如果操作后双端队列为空，则 head 和 tail 都设置为 None。否则，tail 更新为上一个节点，并将新 tail 的下一个指针设置为 None。
Big O Analysis:
- Time Complexity: O(1) – Deletion is done in constant time.
- Space Complexity: O(1) – No additional space is required.
Get Front (获取前端元素):
- We simply return the data at the head of the deque without removing it.
- 我们仅返回双端队列 head 处的元素，而不移除它。
Big O Analysis:
- Time Complexity: O(1) – Access is done in constant time.
- Space Complexity: O(1) – No additional space is required.
Get Rear (获取后端元素):
- We return the data at the tail of the deque without removing it.
- 我们返回双端队列 tail 处的元素，而不移除它。
Big O Analysis:
- Time Complexity: O(1) – Access is done in constant time.
- Space Complexity: O(1) – No additional space is required.

Summary (总结):

Implementing a deque using a doubly linked list provides an efficient way to perform insertions and deletions at both ends of the deque. All operations are executed in constant time, making this implementation suitable for scenarios where the flexibility of a deque is required without sacrificing performance.

使用双链表实现双端队列提供了一种高效的方法，可以在双端队列的两端进行插入和删除操作。所有操作都在常数时间内执行，使这种实现适用于需要双端队列灵活性的场景，同时不牺牲性能。

Post Views: 23

CODEBITWAVE