为什么展开的LinkedList被半填充？

Question

浏览与展开的LinkedList实施相关的所有文章，似乎基于能力，我们生成阈值，如果元素增加了，我们会创建另一个节点并将该元素放入该节点。

阈值=（容量/2）+1

但是为什么我们不将数组填充到展开的LinkedList中，然后创建另一个节点？为什么我们需要阈值并保持阵列半填充？

引用 geeks for geeks- for geeks for geeks- introld链接列表中的插入

/* Java program to show the insertion operation
* of Unrolled Linked List */
import java.util.Scanner;
import java.util.Random;
 
// class for each node
class UnrollNode {
    UnrollNode next;
    int num_elements;
    int array[];
 
    // Constructor
    public UnrollNode(int n)
    {
        next = null;
        num_elements = 0;
        array = new int[n];
    }
}
 
// Operation of Unrolled Function
class UnrollLinkList {
 
    private UnrollNode start_pos;
    private UnrollNode end_pos;
 
    int size_node;
    int nNode;
 
    // Parameterized Constructor
    UnrollLinkList(int capacity)
    {
        start_pos = null;
        end_pos = null;
        nNode = 0;
        size_node = capacity + 1;
    }
 
    // Insertion operation
    void Insert(int num)
    {
        nNode++;
 
        // Check if the list starts from NULL
        if (start_pos == null) {
            start_pos = new UnrollNode(size_node);
            start_pos.array[0] = num;
            start_pos.num_elements++;
            end_pos = start_pos;
            return;
        }
 
        // Attaching the elements into nodes
        if (end_pos.num_elements + 1 < size_node) {
            end_pos.array[end_pos.num_elements] = num;
            end_pos.num_elements++;
        }
 
        // Creation of new Node
        else {
            UnrollNode node_pointer = new UnrollNode(size_node);
            int j = 0;
            for (int i = end_pos.num_elements / 2 + 1;
                 i < end_pos.num_elements; i++)
                node_pointer.array[j++] = end_pos.array[i];
 
            node_pointer.array[j++] = num;
            node_pointer.num_elements = j;
            end_pos.num_elements = end_pos.num_elements / 2 + 1;
            end_pos.next = node_pointer;
            end_pos = node_pointer;
        }
    }
 
    // Display the Linked List
    void display()
    {
        System.out.print("\nUnrolled Linked List = ");
        System.out.println();
        UnrollNode pointer = start_pos;
        while (pointer != null) {
            for (int i = 0; i < pointer.num_elements; i++)
                System.out.print(pointer.array[i] + " ");
            System.out.println();
            pointer = pointer.next;
        }
        System.out.println();
    }
}
 
/* Main Class */
class UnrolledLinkedList_Check {
 
    // Driver code
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
 
        // create instance of Random class
        Random rand = new Random();
 
        UnrollLinkList ull = new UnrollLinkList(5);
 
        // Perform Insertion Operation
        for (int i = 0; i < 12; i++) {
 
            // Generate random integers in range 0 to 99
            int rand_int1 = rand.nextInt(100);
            System.out.println("Entered Element is " + rand_int1);
            ull.Insert(rand_int1);
            ull.display();
        }
    }
}

Answer 1

为什么我们不将数组填充到展开的LinkedList中，然后创建另一个节点？

实际上，提供的代码 将数组填充到满容量：

if (end_pos.num_elements + 1 < size_node) {
    end_pos.array[end_pos.num_elements] = num;
    end_pos.num_elements++;
}

此处未使用阈值。只有当数组达到其容量时，阈值才能创建新数组时扮演角色：

UnrollNode node_pointer = new UnrollNode(size_node);
int j = 0;
for (int i = end_pos.num_elements / 2 + 1; i < end_pos.num_elements; i++)
    node_pointer.array[j++] = end_pos.array[i];

在这里，我们看到完整阵列的后半部分被复制到新数组中。我们可以想象这个过程将一个块分为两个块 - 就像在B树中发生的一样。

这允许在下次需要插入的值时（不是在末尾，而是）在 阵列中的特定偏移时进行快速插入。如果将其填满，它将在每个插入该数组中触发一个新块。通过将松弛空间留在阵列中，我们可以确保至少在该阵列中恰好插入的一些插入中快速插入。

Answer 2

我认为这是确保至少使用50％的利用率。

该算法不仅在完成插入的情况下将其分为一半，而且如果内容的使用率低于50％，则将其重新分布。我认为第二部分是关键：如果您不做第一部分，则无法添加重新分布的检查是否没有充分利用该节点，因为您新创建的节点会立即破坏该节点。

如果您根本不进行重新分配，则最终可能会出现很多未充分利用节点的情况。

我的第一个直觉与其他评论相同（以避免每次创建新节点），但是如果您始终在创建新节点之前始终检查下一个节点，那就不一定是一个问题，因此我不确定是否足够原因？ （但也许我在这里错过了一些东西）