資料結構
網路
關係資料庫管理系統 (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 次瀏覽
