理解双向链表的插入排序

Question

所以我理解插入排序是如何工作的，但是试图将这个概念应用到双向链表让我的大脑变得模糊。有人可以解释该算法在这种情况下的工作原理吗？在给定一个预先存在的链表的情况下，我无法理解在每次逐个节点比较之后节点指针如何变化。我目前在 Java 工作并参考此代码示例：https://www.geeksforgeeks.org/insertion-sort-doubly-linked-list/

下面是两个函数，sortedInsert 和 insertionSort，前者是辅助函数

sortedInsert 中的 else 子句有什么作用？另外为什么作者在insertionSort函数中“删除所有链接以创建当前”？

// function to insert a new node in sorted way in
// a sorted doubly linked list
static Node sortedInsert(Node head_ref, Node newNode)
{
    Node current;
 
    // if list is empty
    if (head_ref == null)
        head_ref = newNode;
 
    // if the node is to be inserted at the beginning
    // of the doubly linked list
    else if ((head_ref).data >= newNode.data)
    {
        newNode.next = head_ref;
        newNode.next.prev = newNode;
        head_ref = newNode;
    }
 
    else
    {
        current = head_ref;
 
        // locate the node after which the new node
        // is to be inserted
        while (current.next != null &&
            current.next.data < newNode.data)
            current = current.next;
 
        //Make the appropriate links /
 
        newNode.next = current.next;
 
        // if the new node is not inserted
        // at the end of the list
        if (current.next != null)
            newNode.next.prev = newNode;
 
        current.next = newNode;
        newNode.prev = current;
    }
    return head_ref;
}
 
// function to sort a doubly linked list using insertion sort
static Node insertionSort(Node head_ref)
{
    // Initialize 'sorted' - a sorted doubly linked list
    Node sorted = null;
 
    // Traverse the given doubly linked list and
    // insert every node to 'sorted'
    Node current = head_ref;
    while (current != null)
    {
 
        // Store next for next iteration
        Node next = current.next;
 
        // removing all the links so as to create 'current'
        // as a new node for insertion
        current.prev = current.next = null;
 
        // insert current in 'sorted' doubly linked list
        sorted=sortedInsert(sorted, current);
 
        // Update current
        current = next;
    }
 
    // Update head_ref to point to sorted doubly linked list
    head_ref = sorted;
     
    return head_ref;
}

Answer 1

What is the else clause doing in sortedInsert?

前两个块（在 else 之前）处理两种边界情况：

列表为空时怎么办
如果新节点必须插入到列表的第一个节点之前怎么办。

所以 else 块正在处理所有其他情况，即新节点将不是列表的新头，但当前头节点将保持原样。

它首先找到一个节点 (current)，下一个 节点持有一个值，该值应该在之后新节点的值（或者，它后面没有下一个节点）。结果（并且由于前面的边界情况），我们知道 current 节点的值应该在之前新节点的值。所以如果我们找到这样一个current，我们就知道新节点一定是插入在current和current.next之间。

简而言之，while 循环找到插入 newNode 的位置。这是任何插入排序算法中的典型阶段。

注释为“制作适当的 links”的部分将最多进行 4 次重新布线。

这是一个例子。假设 linked 列表有 3 个值 10、20 和 30，此时 sortedInsert 被一个值为 25 的新节点调用：

 head_ref
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐
│data: 10   │    │data: 20   │    │data: 30   │
│next: ────────> │next: ────────> │next: null │
│prev: null │    │prev: ─┐   │    │prev: ─┐   │ 
└───────────┘    └───────│───┘    └───────│───┘
           ^             │  ^             │
           └─────────────┘  └─────────────┘

┌───────────┐ 
│data: 25   │
│next: null │
│prev: null │
└───────────┘
  ↑
 newNode

因为 head_ref 不为空且 head_ref.data < newNode.data，我们进入 else 块，其中定义了 current。 while 循环将迭代一次，并使 current 引用停止在该点：

 head_ref         current
  ↓                ↓
┌───────────┐    ┌───────────┐    ┌───────────┐
│data: 10   │    │data: 20   │    │data: 30   │
│next: ────────> │next: ────────> │next: null │
│prev: null │    │prev: ─┐   │    │prev: ─┐   │ 
└───────────┘    └───────│───┘    └───────│───┘
           ^             │  ^             │
           └─────────────┘  └─────────────┘

现在 current.next.data >= newNode.data 所以我们找到了 newNode 的插入点。

第一次重新布线是用 newNode.next = current.next 完成的，结果是：

 head_ref         current
  ↓                ↓
┌───────────┐    ┌───────────┐    ┌───────────┐
│data: 10   │    │data: 20   │    │data: 30   │
│next: ────────> │next: ────────> │next: null │
│prev: null │    │prev: ─┐   │    │prev: ─┐   │ 
└───────────┘    └───────│───┘    └───────│───┘
           ^             │  ^             │ ^
           └─────────────┘  └─────────────┘ │
                                            │
                         ┌───────────┐      │
                         │data: 25   │      │
                         │next: ────────────┘
                         │prev: null │
                         └───────────┘
                           ↑
                          newNode

下一次重新布线仅在 current 不是尾节点时发生：newNode.next.prev = newNode，这是我们的情况：

 head_ref         current
  ↓                ↓
┌───────────┐    ┌───────────┐    ┌───────────┐
│data: 10   │    │data: 20   │    │data: 30   │
│next: ────────> │next: ────────> │next: null │
│prev: null │    │prev: ─┐   │    │prev: ─┐   │ 
└───────────┘    └───────│───┘    └───────│───┘
           ^             │                │ ^
           └─────────────┘                │ │
                                          │ │
                         ┌───────────┐    │ │
                         │data: 25   │ <──┘ │
                         │next: ────────────┘
                         │prev: null │
                         └───────────┘
                           ↑
                          newNode

在这个阶段，新节点正确地 link 与应该跟随它的节点（值为 30 的那个）编辑。现在还有两个赋值，用于在新节点（值为 20 的节点）之前的节点之间建立 link。第一个赋值是 current.next = newNode，结果是：

 head_ref         current
  ↓                ↓
┌───────────┐    ┌───────────┐       ┌───────────┐
│data: 10   │    │data: 20   │       │data: 30   │
│next: ────────> │next: ────────┐    │next: null │
│prev: null │    │prev: ─┐   │  │    │prev: ─┐   │ 
└───────────┘    └───────│───┘  │    └───────│───┘
           ^             │      │            │ ^
           └─────────────┘      │            │ │
                                v            │ │
                             ┌───────────┐   │ │
                             │data: 25   │ <─┘ │
                             │next: ───────────┘
                             │prev: null │
                             └───────────┘
                              ↑
                             newNode

最后重新布线完成 newNode.prev = current:

 head_ref         current
  ↓                ↓
┌───────────┐    ┌───────────┐       ┌───────────┐
│data: 10   │    │data: 20   │       │data: 30   │
│next: ────────> │next: ────────┐    │next: null │
│prev: null │    │prev: ─┐   │  │    │prev: ─┐   │ 
└───────────┘    └───────│───┘  │    └───────│───┘
           ^             │ ^    │            │ ^
           └─────────────┘ │    │            │ │
                           │    v            │ │
                           │ ┌───────────┐   │ │
                           │ │data: 25   │ <─┘ │
                           │ │next: ───────────┘
                           │ │prev: ─┐   │
                           │ └───────│───┘
                           └─────────┘
                              ↑
                             newNode

这也没什么不同：

 head_ref         current          newNode
  ↓                ↓                ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│data: 10   │    │data: 20   │    │data: 25   │    │data: 30   │
│next: ────────> │next: ────────> │next: ────────> │next: null │
│prev: null │    │prev: ─┐   │    │prev: ─┐   │    │prev: ─┐   │ 
└───────────┘    └───────│───┘    └───────│───┘    └───────│───┘
           ^             │  ^             │  ^             │  
           └─────────────┘  └─────────────┘  └─────────────┘

调用者取回头引用head_ref，实际上并没有改变。它只会在新节点成为列表中的第一个节点时发生变化，这是前两个 if 块处理的内容。

Also why does the author "removing all links so as to create current" in the insertionSort function?

这只是从输入列表中提取节点的一种干净方式：它不再是输入列表的一部分，并准备成为新列表的一部分 (sorted)。从技术上讲，对于上述情况，这不是必需的，因为 newNode 的 prev 和 next 成员无论如何都会分配新的引用，但它对于前两个边界情况仍然很重要，因为我们没有在实际需要的地方分配 null 值。

或者，您可以在 sortedInsert 中分配那些 null 引用。

希望这能说明问题。

理解双向链表的插入排序

Understanding insertion sort for doubly linked list

java

algorithm

sorting

linked-list

doubly-linked-list