Java鏈表使用

鏈表(Linked List)是一種線性數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含兩部分：一部分為用于儲(chǔ)存數(shù)據(jù)元素，另部分是一種引用(指針),指向下一個(gè)節(jié)點(diǎn)。

這種結(jié)構(gòu)允許動(dòng)態(tài)地添加和刪除元素，而不需要像數(shù)組那種大規(guī)模的數(shù)據(jù)移動(dòng)。

java鏈表的定義

在java中，鏈表可以通過自定義來實(shí)現(xiàn)，也可以直接使用java.util.LinkedList 類。

LinkedList實(shí)現(xiàn)了接口，并且提供了雙向鏈接的功能，即每個(gè)節(jié)點(diǎn)不僅由指向下一個(gè)節(jié)點(diǎn)的引用，哈有指向前一個(gè)節(jié)點(diǎn)的引用。

這意味著LinkedList不僅可以作為列表使用，還可以作為?；蜿?duì)列使用，因?yàn)樗腔陔p向鏈表現(xiàn)實(shí)的。

每個(gè)節(jié)點(diǎn)通常包含兩個(gè)字段：

• data：用于存儲(chǔ)實(shí)際的數(shù)據(jù)。
• next：用于存儲(chǔ)向下一個(gè)節(jié)點(diǎn)的引用；如果是雙向鏈表，則還有一個(gè)prev字段用于存儲(chǔ)指向前一個(gè)節(jié)點(diǎn)的引用。

實(shí)例

在自定義單項(xiàng)鏈表是，可以這樣定義節(jié)點(diǎn)類：

class Node<E> {
    private E elem; // 數(shù)據(jù)域
    private Node<E> next; // 指針域

    public Node(E element, Node<E> next) {
        this.elem = element;
        this.next = next;
    }

    // Getter 和 Setter 方法...
}

對于LinkedList類而言，內(nèi)部由一個(gè)靜態(tài)內(nèi)部類Node，用來表示鏈表中的節(jié)點(diǎn)。此外，LinkedList還維護(hù)著幾個(gè)重要的成員變量，例如size（記錄鏈表大小）、first（指向第一個(gè)節(jié)點(diǎn)）和last（指向最后一個(gè)節(jié)點(diǎn)）。這些變量是的可以在O(1)時(shí)間內(nèi)完成對鏈表頭部或尾部的操作。

Java鏈表的應(yīng)用

由于鏈表具有靈活的內(nèi)存管理和高效的插入\刪除操作特性,因此適用于多種引用場景：

1. 頻繁插入和刪除：當(dāng)應(yīng)用程序需要頻繁地在集合中插入或刪除元素是，使用LinkedList會(huì)比ArrayList更有效率。這是因?yàn)?code>LinkedList不需要像ArrayList那樣在插入或刪除時(shí)調(diào)整其他元素的位置，從而避免了額外的時(shí)間開銷。
2. 作為?；蜿?duì)列使用:LinkedList實(shí)現(xiàn)了Deque接口，所以它可以很方便地用作棧（通過addFirst()、removeFirst()等方法）或者隊(duì)列（通過addList()、removeFirst()等方法）。
3. 緩存系統(tǒng)：某些緩存算法（例如LRU,Least Recentiy Used）可能需要用到LinkedList來維護(hù)元素的順序。如，可以結(jié)合HashMap和LinkedList實(shí)現(xiàn)一個(gè)簡單的LRu緩存。
4. 多線程環(huán)境下的隊(duì)列：盡管LinkedList本身不是線程安全的，但在多線程環(huán)境中，可以通過適當(dāng)?shù)耐綑C(jī)制將其用作線程安全的隊(duì)列。
5. 文件系統(tǒng)的實(shí)現(xiàn)：鏈表的概念也被應(yīng)用與文件系統(tǒng)的設(shè)計(jì)中，比如FAT32、NTFS等格式的選擇實(shí)際上就是在選擇不同類型的鏈表空間規(guī)模及格式。
6. 高級數(shù)據(jù)結(jié)構(gòu)：除了上述應(yīng)用外，java鏈表還可以用于構(gòu)建更加復(fù)雜的結(jié)構(gòu)，如雙端隊(duì)列（Deque）、循環(huán)鏈表（Circular Linked List）、跳表（Skip List）等。
7. 鏈表合并：在排序算法中，如歸并排序、合并兩個(gè)有序鏈表也是常見的操作之一。
8. 返回倒數(shù)第K個(gè)節(jié)點(diǎn):利用前后指針法可以高效地找到鏈表中的倒數(shù)第K個(gè)節(jié)點(diǎn)。

常用方法

上述列來自于菜鳥教程，下方為更多API方法

LinkedList (Java SE 11 & JDK 11 )

鏈表應(yīng)用定義總結(jié)

Java中的鏈表不僅是一個(gè)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，而且因其靈活性和效率，在許多不同的編程場景中都有著廣泛的應(yīng)用。

無論是作為簡單的容器還是構(gòu)建更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)組件，鏈表都扮演著不可或缺的角色。

鏈表應(yīng)用實(shí)例

創(chuàng)建鏈表

首先，我們可以創(chuàng)建一個(gè)空的LinkedList實(shí)例：

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個(gè)新的空LinkedList
        LinkedList<String> list = new LinkedList<>();
    }
}

這段代碼展示了如何導(dǎo)入java.util.LinkedList包，并創(chuàng)建了一個(gè)存儲(chǔ)字符串類型的LinkedList對象。

添加元素

接下來，我們可以在鏈表中添加元素?？梢允褂?code>add()方法向鏈表末尾添加元素，或者使用addFirst()、addLast()分別向鏈表頭部或尾部插入元素。

// 向鏈表末尾添加元素
list.add("Apple");
list.add("Banana");

// 向鏈表頭部添加元素
list.addFirst("Orange");

// 向鏈表尾部添加元素
list.addLast("Grape");

這里展示了如何使用不同的方法向鏈表中添加元素。值得注意的是，addFirst()和addLast()提供了更明確的操作意圖，而不僅僅是默認(rèn)地添加到鏈表末尾。

訪問元素

訪問鏈表中的元素可以通過索引進(jìn)行，也可以遍歷整個(gè)鏈表。對于前者，可以使用get()方法；對于后者，則可以使用增強(qiáng)型for循環(huán)或迭代器。

// 通過索引訪問元素
String element = list.get(1); // 獲取第二個(gè)元素

// 使用增強(qiáng)型for循環(huán)遍歷鏈表
for (String fruit : list) {
    System.out.println(fruit);
}

// 使用迭代器遍歷鏈表
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

這里介紹了兩種常見的遍歷方式：一種是直接通過索引獲取特定位置的元素，另一種則是利用迭代器逐一訪問每個(gè)元素。

刪除元素

刪除鏈表中的元素同樣支持多種方式，包括根據(jù)索引刪除、根據(jù)值刪除以及移除鏈表頭尾的元素。

// 根據(jù)索引刪除元素
list.remove(0); // 移除第一個(gè)元素

// 根據(jù)值刪除元素
list.remove("Banana"); // 移除值為"Banana"的第一個(gè)匹配項(xiàng)

// 移除鏈表頭部元素
list.removeFirst();

// 移除鏈表尾部元素
list.removeLast();

插入元素

除了簡單的添加和刪除外，還可以在鏈表的任意位置插入新元素。這通常涉及到先找到目標(biāo)位置，然后將新元素插入到該位置之前或之后。

// 在指定位置插入元素
list.add(1, "Peach"); // 在索引1處插入"Peach"

查找元素

如果想要檢查某個(gè)元素是否存在於鏈表中，可以使用contains()方法。

boolean exists = list.contains("Apple");
if (exists) {
    System.out.println("The list contains Apple.");
} else {
    System.out.println("The list does not contain Apple.");
}

這段代碼用來驗(yàn)證鏈表中是否包含特定元素，并輸出相應(yīng)的消息。

這些例子涵蓋了Java中LinkedList的基本用法，包括創(chuàng)建、添加、訪問、刪除、插入以及查找元素。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評論