展开链表

2024 年 8 月 28 日 | 阅读 9 分钟

展开链表（Unrolled Linked List）是一种线性数据结构，它是链表的一个变体。展开链表在每个节点中存储一个完整的数组，而不是仅存储一个元素。展开链表结合了数组的优点（低内存开销）和链表的优点（快速插入和删除），从而实现了显著的性能提升。通过在每个节点存储多个元素，展开链表有效地将链表的开销分摊到多个元素上。

因此，如果一个展开链表的每个节点都持有一个包含四个元素的数组，那么链表的开销（指针）就会被分摊到这四个元素上。当考虑到现代CPU的缓存管理时，展开链表的性能更优。与标准的单向链表相比，展开链表每个节点的开销略高。然而，在大多数情况下，与现代计算机带来的优势相比，这个缺点是微不足道的。

展开链表是一种链表，其中每个节点都包含一个值数组，而不仅仅是一个值。每个节点的数组可以包含任何传统数组可以包含的内容，包括基本类型和其他抽象数据类型。每个节点可以容纳最大数量的值，大多数实现会保持每个节点的容量在3/4左右。当特定的数组溢出时，它会通过在节点之间转移值来实现平衡。

展开链表的每个节点开销略高，因为每个节点需要存储其数组可以容纳的最大值数量。然而，与标准链表相比，它的每个值的成本要低得多。随着每个节点中数组的最大尺寸增加，每个值所需的平均存储空间会减少，当值的类型非常小时，空间优势会更加显著。展开链表是数组和链表的混合体。它利用了数组超快的索引速度和存储局部性。这两个优点都源于静态数组的底层特性。此外，它保留了链表在节点插入和删除方面的优势。

在展开链表中插入和删除元素的算法因实现而异。通常将低水位线（low-water mark）设置为50%，这意味着如果一个元素无法插入到某个节点中，就会创建一个新节点，并将当前节点的一半元素移入新节点。如果我们删除一个元素，导致该节点中的值的数量低于50%，我们会从相邻数组中插入元素到该节点，使其恢复到50%以上。如果那个相邻数组也低于50%，则将两个节点合并。

这使得节点的平均利用率大约在70-75%之间。当节点大小适中时，与链表相比，其开销非常低。链表中的每个节点大约需要两到三个单位的开销。而展开链表的开销被分摊到其元素上，使其开销为1/size，这与数组的开销相似。要调整展开链表的性能，可以更改低水位线。通过提高低水位线，可以提高每个节点的平均利用率。然而，这将需要更频繁的分裂和合并操作。

Java 代码

现在，让我们编写一个Java代码来实现一个展开链表，它将执行所有基本功能，如在展开链表上添加、删除和显示节点。

/*This is a Java Program to implement an Unrolled Linked List. An unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can dramatically increase cache performance while decreasing the memory overhead associated with storing list metadata such as references. It is related to the B-tree.*/


 // A sample Java Program to Implement Unrolled Linked List


import java.util.Scanner;

// A class named ULLNode is created that will act as a single node of the Unrolled Linked List 
class ULLNode
{
    // A variable named next of the ULLNode type is created that will be used to store the address of the next node of the Unrolled Linked Lists
    ULLNode next;
    // A variable named numElements of the integer is created that will be used to store the number of elements in that node of the Unrolled Linked List
    int numElements;
    int array[];


    // A parameterized constructor is written that will be used to initialize the class variables of the ULLNode class
    public ULLNode(int n)
    {
        next = null;
        numElements = 0;
        array = new int[n];
    }
}

// A class named UnrolledLinkedList is created that will have all the utility Functions of the Unrolled Linked List 
class UnrolledLinkedList
{

    // A private variable named start of the ULLNode type is created that will be used to represent the start of the Unrolled Linked List
    private ULLNode start;
    // A private variable named end of the ULLNode type is created that will be used to represent the end of the Unrolled Linked List
    private ULLNode end;
    // A variable named sizeNode of the integer is created that will be used to store the size of the node
    private int sizeNode;
    private int nNode;

    // A parameterized constructor is written that will be used to initialize the class variables of the UnrolledLinkedList class
    public UnrolledLinkedList(int capacity)
    {
        start = null;
        end = null;
        nNode = 0;
        sizeNode = capacity + 1;
    }


    // A public Function named isEmpty() is written that will be used to check whether the Unrolled Linked List is empty or not.
    public boolean isEmpty()
    {
        return start == null;
    }

    // A public Function named getSize() is written that will be used to get the size of the Unrolled Linked List
    public int getSize()
    {
        return nNode;
    }

    // A public Function named makeEmpty() is written that will be used to empty the Unrolled Linked List
    public void makeEmpty()
    {
        start = null;
        end = null;
        nNode = 0;
    }

    // A public Function named insert() is written that will be used to a new element to the Unrolled Linked List
    public void insert(int x)
    {
        nNode++;
        if (start == null)
            {
                start = new ULLNode(sizeNode);
                start.array[0] = x;
                start.numElements++;
                end = start;
                return;
            }
        if (end.numElements + 1 < sizeNode)
            {
                end.array[end.numElements] = x;
                end.numElements++;
            }
        else
            {
                ULLNode nptr = new ULLNode(sizeNode);
                int j = 0;
                for (int i = end.numElements/2 + 1; i < end.numElements; i++)
                    nptr.array[j++] = end.array[i];
                nptr.array[j++] = x;
                nptr.numElements = j;
                end.numElements = end.numElements/2 + 1;
                end.next = nptr;
                end = nptr;
            }
    }

    // A public Function named display() is written that will be used to print all the elements of the Unrolled Linked List
    public void display()
    {
        System.out.print("\nUnrolled Linked List = ");
        if (nNode == 0)
            {
                System.out.print("empty\n");
                return;
            }
        System.out.println();
        ULLNode ptr = start;
        while (ptr != null)
            {
                for (int i = 0; i < ptr.numElements; i++)
                    System.out.print(ptr.array[i] +" ");
                System.out.println();
                ptr = ptr.next;
            }
    }

}

public class UnrolledLinkedListTest
{
    // main function is written to call all the functionalities functions of the Unrolled Linked List Data structure written above
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter array size of each node");
        /* Creating object of class UnrolledLinkedList */
        UnrolledLinkedList ull = new UnrolledLinkedList(scan.nextInt() );
        char ch;
       /*  Perform list operations  */
        do
            {

                System.out.println("Please Choose one of the Operations::");
                System.out.println("1. To insert Data in the Unrolled Linked List.");
                System.out.println("2. To Check List is empty or not.");
                System.out.println("3. To get the size of the Unrolled Linked List.");
                System.out.println("4. To clear the Unrolled Linked List.");
                System.out.println("5. To print/display the Data in the Unrolled Linked List.");
                int choice = scan.nextInt();
                switch (choice)
                    {
                    case 1 :
                        System.out.println("Enter integer element to insert");
                        ull.insert( scan.nextInt() );
                        break;
                    case 2 :
                        System.out.println("Empty status = "+ ull.isEmpty());
                        break;
                    case 3 :
                        System.out.println("Size = "+ ull.getSize() +"\n");
                        break;
                    case 4 :
                        System.out.println("List Cleared\n");
                        ull.makeEmpty();
                        break;
                    case 5 :
                        System.out.println("Contents of Unrolled Linked List are::");
                        ull.display();
                    default :
                        System.out.println("Wrong Entry\n ");
                        break;
                    }
                System.out.println("\nDo you want to continue (Type y or n)\n");
                ch = scan.next().charAt(0);
            }
        while (ch == 'Y'|| ch == 'y');
    }
}// end of code

输出

上述代码给出以下输出。

Enter array size of each node
8
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
1
Enter integer element to insert
12

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
1
Enter integer element to insert
2

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
1
Enter integer element to insert
3

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
1
Enter integer element to insert
4

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
5
Contents of Unrolled Linked List are::

Unrolled Linked List = 
1 2 3 4 
Wrong Entry
 

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
2
Empty status = false

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
3
Size = 4


Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
5
Contents of Unrolled Linked List are::

Unrolled Linked List = 
1 2 3 4 

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
5
Contents of Unrolled Linked List are::

Unrolled Linked List = 
1 2 3 4 
Wrong Entry
 

Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
4
List Cleared


Do you want to continue (Type y or n)

y
Please Choose one of the Operations::
1. To insert Data in the Unrolled Linked List.
2. To Check List is empty or not.
3. To get the size of the Unrolled Linked List.
4. To clear the Unrolled Linked List.
5. To print/display the Data in the Unrolled Linked List.
5
Contents of Unrolled Linked List are::

Unrolled Linked List = empty
Wrong Entry
 

Do you want to continue (Type y or n)

n

优点

以下是展开链表的优点，例如：

由于缓存行为，展开链表中的线性搜索速度要快得多。
与传统链表相比，它为指针/引用占用的存储空间更少。
在插入、删除和遍历等操作上，它比典型的链表更快（因为搜索更快）。

下一个主题稀疏矩阵的类型

展开链表

Java 代码

优点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

展开链表

Java 代码

优点

相关帖子

详细解释双端队列

最大异或

如何在 AVL 树中插入字符串

使用循环数组实现双端队列

产品数组谜题

整数流的（运行）中位数

合并重叠区间

K 反转对数组

数据结构中的迭代是什么

最小堆和最大堆的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器