数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Java程序实现展开链表
在本问题中，我们将学习如何实现展开链表。展开链表是链表的一种特殊版本。普通的链表在一个节点中只包含一个元素，而展开链表在一个节点中包含一组元素。
此外，展开链表中的插入、删除和遍历操作与普通链表相同。线性搜索在数组中比在链表中更快。因此，我们可以在数组中添加元素，并在链表的每个节点中添加一个数组。此外，展开链表提高了遍历效率并优化了内存使用。
问题陈述 - 我们需要编写Java代码来使用数组实现展开链表。
使用展开链表优于普通链表的优势
第一个好处是它提高了搜索和插入效率，因为我们可以在O(1)时间内将元素插入到数组中。
在内存效率和缓存性能很重要的场合，我们可以使用展开链表。
由于我们使用数组，因此迭代速度很快。
我们可以节省内存，因为我们不需要为每个元素都使用指针。
步骤
步骤1 - 在此示例中，我们定义了“listNode”类来创建链表的节点。
步骤2 - 声明链表大小、链表和下一个节点的变量。每个节点将包含大小为listSize的列表。
步骤3 - 添加一个构造函数，以便在创建给定类的对象时初始化类变量。
步骤4 - 定义insertElement()函数，将元素插入到展开链表中。
步骤5 - 如果链表大小小于listSize变量的值，则使用add()方法将元素添加到链表中。
步骤6 - 否则，我们需要将元素添加到另一个链表。如果next为null，我们需要创建一个新的链表，因为所有链表都已满。之后，再次调用insertElement()函数。
步骤7 - 如果next不为null，则表示下一个链表存在且有空间，因此添加元素。
步骤8 - 定义deleteElement()函数，从链表中删除元素。
步骤9 - 如果当前链表包含该元素，则将其从链表中删除，并返回true。
步骤10 - 否则，如果next为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(Nodes*list_Size)
示例2步骤
步骤1 - 创建名为listNode的静态类，表示链表的节点。
步骤2 - 在类中定义totalElements、list和nextNode变量。
步骤3 - 通过创建类对象来定义四个不同的节点。
步骤4 - 使用元素初始化每个节点的列表，并通过nextNode连接列表。
步骤5 - 定义printList()方法以打印展开链表的所有元素。
步骤6 - 在printList()函数中，直到起始节点不为null才进行迭代。
步骤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中创建展开链表。程序员可以观察它如何节省内存。此外，像第二个示例一样，我们可以使用它在每个节点中存储一组元素。
126 次浏览
