Java 实现非收回链接列表

在这个问题中，我们将学习如何实现非收回链接列表。非收回链接列表是链接列表的一种特殊版本。普通的链接列表中，每个节点只包含一个元素，而非收回链接列表的每个节点包含一组元素。

此外，非收回链接列表中的插入、删除和遍历与普通的链接列表相同。在数组中进行线性搜索比在链接列表中快。因此，我们可以在数组中添加元素，并将数组添加到链接列表的每个节点中。非收回链接列表还提高了遍历的效率，并优化了内存的使用。

问题陈述 – 我们需要编写Java代码，使用数组实现非收回链接列表。

使用非收回链接列表而不是普通链接列表的好处

• 第一个好处是它提高了搜索和插入的效率，因为我们可以在o(1)的时间内插入元素到数组中。

• 在内存效率和缓存性能重要的情况下，我们可以使用非收回链接列表。

• 由于使用了数组，所以可以进行快速迭代。

• 由于不需要为每个元素添加指针，所以可以节省内存。

步骤1的步骤

步骤1 - 在这个示例中，我们定义了’listNode’类来创建链接列表的节点。

步骤2 - 声明列表大小、列表和下一个节点的变量。每个节点将包含列表的列表大小。

步骤3 - 在创建给定类的对象时，添加一个构造函数来初始化类变量。

步骤4 - 定义insertElement()函数来将元素插入非收回链接列表中。

步骤5 - 如果列表大小小于列表大小变量的值，则使用add()方法向列表添加元素。

步骤6 - 否则，我们需要将元素添加到另一个列表中。如果下一个节点为null，则需要创建一个新的列表，因为所有列表都已满。然后再次调用insertElement()函数。

步骤7 - 如果下一个节点不为null，则表示下一个列表存在并且有空间，因此可以添加一个元素。

步骤8 - 定义deleteElement()函数来从链接列表中删除元素。

步骤9 - 如果当前列表包含该元素，则从列表中将其删除，并返回true。

步骤10 - 否则，如果下一个节点为null，表示我们已经遍历了所有列表，但在链接列表中未找到该元素，因此返回false。否则，在下一个列表上调用deleteElement()方法。

步骤11 - 最后，返回true。

步骤12 - 创建一个listNode类的对象，并将元素插入其中。还要遍历列表并打印出元素。

示例1

在这个例子中，我们可以像普通的链表一样插入和删除元素。此外，如果我们从任何列表中删除任何元素，并在插入新元素之后，它将首先填充半空列表而不是创建新的列表。因此，它优化了空间。

import java.io.*;
import java.util.*;
public class Main {
   // Nested static class
   static class listNode {
      // Declaring variables
      int listSize;
      ArrayList<Integer> list;
      listNode next = null;
      // constructor
      listNode(int listsize) {
         // Initialize the listSize
         this.listSize = listsize;
         // Creating the array list
         list = new ArrayList<>();
      }
      // Inserting elements into the list
      void insertElement(int element) {
         // If the array contains space, insert an element to the list
         if (list.size() < listSize) {
            list.add(element);
         } else { // array is full // If the new array is not started, create a new node and call the insertElement() method
            if (next == null) {
               next = new listNode(listSize);
               next.insertElement(element);
            } else {
               // Insert element to the array
               next.insertElement(element);
            }
         }
      }
      // Deleting elements from the list
      boolean deleteElement(int element) {
         // If the list has the element, remove it
         if (list.contains(element)) {
            list.remove(list.indexOf(element));
            return true;
         } else { // If the list has no element and the next is null, the element doesn't exist in the
            // linked list
            if (next == null) {
               return false;
            } else {
               // Move to the next list
               next.deleteElement(element);
            }
            return true;
         }
      }
   }
   public static void printList(listNode x) {
      while (x != null) {
         System.out.println(x.list);
         x = x.next;
      }
   }
   public static void main(String args[]) {
      listNode x = new listNode(3);
      // Inserting elements to a linked list
      for (int p = 1; p <= 16; p++) {
         x.insertElement(p * 10);
      }
      printList(x);
      // delete 10, 30, 70, and 100.
      x.deleteElement(10);
      x.deleteElement(30);
      x.deleteElement(70);
      x.deleteElement(100);
      // Print updated list
      System.out.println(" ");
      System.out.println("Updated list");
      printList(x);
   }
}

输出

[10, 20, 30]
[40, 50, 60]
[70, 80, 90]
[100, 110, 120]
[130, 140, 150]
[160]

Updated list
[20]
[40, 50, 60]
[80, 90]
[110, 120]
[130, 140, 150]
[160]

时间复杂度 – O（N）遍历列表并删除元素。

空间复杂度 – O（节点*列表大小）

示例2的步骤

步骤1 - 创建名为listNode的静态类，表示链表中的节点。

步骤2 - 在类内部定义totalElements，list和nextNode变量。

步骤3 - 通过创建类对象定义四个不同的节点。

步骤4 - 将每个节点的列表初始化为元素，并通过下一个节点将它们连接起来。

步骤5 - 定义printList（）方法以打印展开链表的所有元素。

步骤6 - 在printList（）函数中，进行迭代直到开始节点不为空。

步骤7 - 然后，遍历列表的每个元素，并将它们打印出来。

示例2

在下面的示例中，我们创建了展开链表来存储一组素数。

import java.util.*;
public class Main {
   static final int maxNumbers = 5;
   // Creating the unrolled Linked list
   static class listNode {
     int totalElements;
     int[] list = new int[maxNumbers];
     listNode nextNode;
   };
   static void printList(listNode start) {
     while (start != null) {
       System.out.print("[ ");
       // print the elements of the current list
       for (int p = 0; p < start.totalElements; p++)
         System.out.print(start.list[p] + " ");
       System.out.println("] ");
       // Move to next node
       start = start.nextNode;
     }
   }
   public static void main(String[] args) {
     listNode start = null;
     listNode secondList = null;
     listNode thirdList = null;
     listNode fourthList = null;
     // Initialize nodes
     start = new listNode();
     secondList = new listNode();
     thirdList = new listNode();
     fourthList = new listNode();
     // add Values to the list
     start.totalElements = 4;
     start.list[0] = 2;
     start.list[1] = 3;
     start.list[2] = 5;
     start.list[3] = 7;
     // Link the next node to the first
     start.nextNode = secondList;
     // add elements to the second list
     secondList.totalElements = 4;
     secondList.list[0] = 11;
     secondList.list[1] = 13;
     secondList.list[2] = 17;
     secondList.list[3] = 19;
     secondList.nextNode = thirdList;
     // add elements to the third list
     thirdList.totalElements = 2;
     thirdList.list[0] = 23;
     thirdList.list[1] = 29;
     thirdList.nextNode = fourthList;
     // add elements to the fourth list
     fourthList.totalElements = 2;
     fourthList.list[0] = 31;
     fourthList.list[1] = 37;
     // assign null to the next of the fourth list
     fourthList.nextNode = null;
     printList(start);
   }
}

输出

[ 2 3 5 7 ] 
[ 11 13 17 19 ] 
[ 23 29 ] 
[ 31 37 ]

我们学会了在Java中创建一个展开的链表。程序员可以观察它如何节省内存。而且，就像第二个例子那样，我们可以使用它来在每个节点中存储一组元素。