Algorithms 101: Singly and Doubly Linked Lists and Their Reversal – Stack Interpretation

单双链表及其反转 – 堆栈诠释

Linked lists are fundamental data structures in computer science, offering a flexible way to store and manipulate data. A singly linked list consists of nodes where each node contains data and a reference to the next node in the sequence. A doubly linked list, on the other hand, includes nodes that contain references to both the next and the previous nodes. Reversing linked lists is a common operation, and one effective way to conceptualize and implement this reversal is through the use of a stack.

链表是计算机科学中基本的数据结构，提供了一种灵活的方式来存储和操作数据。单链表由一系列节点组成，每个节点包含数据和对下一个节点的引用。而双链表的节点则包含对下一个和前一个节点的引用。反转链表是一种常见的操作，使用堆栈来实现和理解这种反转是一种有效的方法。

1. Singly Linked List and Its Reversal

单链表及其反转

Structure of a Singly Linked List

单链表的结构

A singly linked list is a linear collection of nodes where each node points to the next node in the sequence. The last node in the list points to None, signifying the end of the list.

单链表是一个线性集合的节点，每个节点指向序列中的下一个节点。链表中的最后一个节点指向 None，表示链表的结束。

Example of Singly Linked List Node Definition

单链表节点定义示例

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

Reversing a Singly Linked List

反转单链表

To reverse a singly linked list, we can use an iterative approach where we traverse the list and reverse the direction of each node’s next pointer. This can be efficiently done using a stack to store the nodes temporarily.

为了反转单链表，我们可以使用一种迭代方法，在遍历链表的同时，反转每个节点的 next 指针的方向。可以使用堆栈暂时存储节点，以高效完成这一操作。

Steps to Reverse Using a Stack

使用堆栈反转的步骤

1. Traverse the List: Push each node onto the stack as you traverse the list.

2. Pop from the Stack: As you pop each node from the stack, reverse its next pointer to point to the previous node popped.

3. Update the Head: The last node popped from the stack becomes the new head of the reversed list.

4. 遍历链表：在遍历链表时，将每个节点推入堆栈。

5. 从堆栈中弹出：在从堆栈中弹出每个节点时，将其 next 指针反转，指向前一个弹出的节点。

6. 更新头节点：堆栈中最后弹出的节点成为反转链表的新头节点。

Code Example for Reversing a Singly Linked List

反转单链表的代码示例

def reverseSinglyLinkedList(head):
    stack = []
    current = head

    # Push nodes to stack
    while current:
        stack.append(current)
        current = current.next

    # Pop from stack and reverse pointers
    head = stack.pop()
    current = head
    while stack:
        next_node = stack.pop()
        current.next = next_node
        current = next_node

    current.next = None
    return head

Time Complexity Analysis

时间复杂度分析

The time complexity of this approach is O(n), where n is the number of nodes in the linked list. Each node is visited twice—once when it is pushed onto the stack and once when it is popped.

该方法的时间复杂度为 O(n)，其中 n 是链表中的节点数。每个节点被访问两次——一次是在将其推入堆栈时，另一次是在将其弹出时。

2. Doubly Linked List and Its Reversal

双链表及其反转

Structure of a Doubly Linked List

双链表的结构

A doubly linked list is similar to a singly linked list but with an additional pointer in each node that points to the previous node in the list. This bidirectional structure allows for more flexible traversal and easier reversal.

双链表类似于单链表，但每个节点中多了一个指向前一个节点的指针。这种双向结构允许更灵活的遍历和更容易的反转。

Example of Doubly Linked List Node Definition

双链表节点定义示例

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

Reversing a Doubly Linked List

反转双链表

Reversing a doubly linked list involves swapping the next and prev pointers for each node. This operation is also easily conceptualized with a stack, although in practice, it can be done iteratively without one.

反转双链表需要交换每个节点的 next 和 prev 指针。虽然这个操作可以通过堆栈来理解，但实际上可以在没有堆栈的情况下迭代完成。

Steps to Reverse Using a Stack

使用堆栈反转的步骤

1. Traverse the List: Push each node onto the stack as you traverse.

2. Pop and Swap Pointers: As you pop nodes from the stack, swap their next and prev pointers.

3. Update the Head: The last node popped from the stack becomes the new head.

4. 遍历链表：在遍历时将每个节点推入堆栈。

5. 弹出并交换指针：在从堆栈中弹出节点时，交换它们的 next 和 prev 指针。

6. 更新头节点：堆栈中最后弹出的节点成为新头节点。

Code Example for Reversing a Doubly Linked List

反转双链表的代码示例

def reverseDoublyLinkedList(head):
    stack = []
    current = head

    # Push nodes to stack
    while current:
        stack.append(current)
        current = current.next

    # Pop from stack and reverse pointers
    head = stack.pop()
    current = head
    current.prev = None
    while stack:
        next_node = stack.pop()
        current.next = next_node
        next_node.prev = current
        current = next_node

    current.next = None
    return head

Time Complexity Analysis

时间复杂度分析

Similar to the singly linked list reversal, the time complexity is O(n). Each node is visited twice, once for pushing onto the stack and once for popping.

与单链表的反转类似，时间复杂度为 O(n)。每个节点被访问两次，一次是推入堆栈，一次是弹出。

3. Stack Interpretation of Linked List Reversal

堆栈诠释链表反转

Using a stack to reverse a linked list can be thought of as a way to temporarily store the order of nodes before reconstructing them in reverse. The stack’s LIFO (Last In, First Out) property naturally lends itself to reversing the order of elements, making it an intuitive method for reversing linked lists.

使用堆栈来反转链表可以被认为是一种在重建链表之前暂时存储节点顺序的方法。堆栈的 LIFO（后进先出）属性自然适合于反转元素的顺序，这使其成为反转链表的一种直观方法。

Conceptual Advantages

概念上的优势

• Simplicity: The stack provides a clear and simple mechanism for reversing the order of elements.

• Clarity: The use of a stack makes the process easy to understand and visualize, especially for those new to linked lists.

• 简单性：堆栈提供了一种清晰且简单的机制来反转元素的顺序。

• 清晰性：使用堆栈使得过程易于理解和可视化，特别是对于链表新手而言。

Practical Considerations

实际考虑

In practice, reversing a linked list can often be done more efficiently without a stack, especially in the case of a doubly linked list where you can directly swap pointers. However, the stack approach is valuable for understanding the process and for educational purposes.

在实际中，反转链表通常可以在没有堆栈的情况下更高效地完成，尤其是在双链表的情况下，你可以直接交换指针。然而，堆栈方法对于理解过程和教学目的来说是有价值的。

4. Conclusion

结论

Understanding the structure and reversal of singly and doubly linked lists is fundamental in computer science. The stack interpretation offers a clear and intuitive way

to approach the problem, making it easier to grasp the concepts involved. Whether using a stack or a direct iterative method, mastering these techniques is essential for working with linked lists and understanding data structures.

理解单链表和双链表的结构及其反转在计算机科学中是基本的。堆栈诠释提供了一种清晰且直观的方法来解决这一问题，使得更容易掌握所涉及的概念。无论是使用堆栈还是直接迭代方法，掌握这些技术对于操作链表和理解数据结构都是至关重要的。