Java數(shù)據(jù)結(jié)構(gòu)之LinkedList的用法詳解

更新時間：2023年05月08日 08:29:11 作者：無聲編碼器

鏈表（Linked?list）是一種常見的基礎數(shù)據(jù)結(jié)構(gòu)，是一種線性表。Java的LinkedList（鏈表）?類似于?ArrayList，是一種常用的數(shù)據(jù)容器，本文就來簡單講講它的使用吧

鏈表（Linked list）是一種常見的基礎數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的地址。鏈表可分為單向鏈表和雙向鏈表。

一個單向鏈表包含兩個值: 當前節(jié)點的值和一個指向下一個節(jié)點的鏈接。

一個雙向鏈表有三個整數(shù)值: 數(shù)值、向后的節(jié)點鏈接、向前的節(jié)點鏈接。

Java的LinkedList（鏈表）類似于 ArrayList，是一種常用的數(shù)據(jù)容器。與 ArrayList 相比，LinkedList 的增加和刪除的操作效率更高，而查找和修改的操作效率較低。

以下情況使用 ArrayList:

頻繁訪問列表中的某一個元素。
只需要在列表末尾進行添加和刪除元素操作。

以下情況使用 LinkedList :

你需要通過循環(huán)迭代來訪問列表中的某些元素。
需要頻繁的在列表開頭、中間、末尾等位置進行添加和刪除元素操作。

LinkedList 繼承了 AbstractSequentialList 類。分別實現(xiàn)了 Queue 接口，可作為隊列使用； List 接口，可進行列表的相關(guān)操作； Deque 接口，可作為隊列使用； Cloneable 接口，可實現(xiàn)克??； java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

LinkedList 類位于 java.util 包中，使用前需要引入它，語法格式如下：

// 引入 LinkedList 類
import java.util.LinkedList; 
LinkedList<E> list = new LinkedList<E>();   // 普通創(chuàng)建方法
//或者
LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合創(chuàng)建鏈表

創(chuàng)建一個簡單的鏈表實例：

import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        System.out.println(sites);
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// [Google, Runoob, Taobao, Weibo]

更多的情況下我們使用 ArrayList 訪問列表中的隨機元素更加高效，但以下幾種情況 LinkedList 提供了更高效的方法：

在列表開頭添加元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        // 使用 addFirst() 在頭部添加元素
        sites.addFirst("Wiki");
        System.out.println(sites);
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// [Wiki, Google, Runoob, Taobao]

在列表結(jié)尾添加元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        // 使用 addLast() 在尾部添加元素
        sites.addLast("Wiki");
        System.out.println(sites);
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// [Google, Runoob, Taobao, Wiki]

在列表開頭移除元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        // 使用 removeFirst() 移除頭部元素
        sites.removeFirst();
        System.out.println(sites);
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// [Runoob, Taobao, Weibo]

在列表結(jié)尾移除元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        // 使用 removeLast() 移除尾部元素
        sites.removeLast();
        System.out.println(sites);
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// [Google, Runoob, Taobao]

獲取列表開頭的元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        // 使用 getFirst() 獲取頭部元素
        System.out.println(sites.getFirst());
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// Google

獲取列表結(jié)尾的元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        // 使用 getLast() 獲取尾部元素
        System.out.println(sites.getLast());
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// Weibo

LinkedList 迭代元素方式

可以使用 for 配合 size() 方法來迭代列表中的元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        for (int size = sites.size(), i = 0; i < size; i++) {
            System.out.println(sites.get(i));
        }
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// Google
// Runoob
// Taobao
// Weibo

也可以使用 for-each 來迭代元素：

// 引入 LinkedList 類
import java.util.LinkedList;

public class RunoobTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        for (String i : sites) {
            System.out.println(i);
        }
    }
}
// 實例執(zhí)行輸出結(jié)果為：
// Google
// Runoob
// Taobao
// Weibo

LinkedList 常用方法

方法	描述
public boolean add(E e)	鏈表末尾添加元素，返回是否成功，成功為 true，失敗為 false
public void add(int index, E element)	向指定位置插入元素
public boolean addAll(Collection c)	將一個集合的所有元素添加到鏈表后面，返回是否成功，成功為 true，失敗為 false
public boolean addAll(int index, Collection c)	將一個集合的所有元素添加到鏈表的指定位置后面，返回是否成功，成功為 true，失敗為 false
public void addFirst(E e)	元素添加到頭部
public void addLast(E e)	元素添加到尾部
public boolean offer(E e)	向鏈表末尾添加元素，返回是否成功，成功為 true，失敗為 false
public boolean offerFirst(E e)	頭部插入元素，返回是否成功，成功為 true，失敗為 false
public boolean offerLast(E e)	尾部插入元素，返回是否成功，成功為 true，失敗為 false
public void clear()	清空鏈表
public E removeFirst()	刪除并返回第一個元素
public E removeLast()	刪除并返回最后一個元素
public boolean remove(Object o)	刪除某一元素，返回是否成功，成功為 true，失敗為 false
public E remove(int index)	刪除指定位置的元素
public E poll()	刪除并返回第一個元素
public E remove()	刪除并返回第一個元素
public boolean contains(Object o)	判斷是否含有某一元素
public E get(int index)	返回指定位置的元素
public E getFirst()	返回第一個元素
public E getLast()	返回最后一個元素
public int indexOf(Object o)	查找指定元素從前往后第一次出現(xiàn)的索引
public int lastIndexOf(Object o)	查找指定元素最后一次出現(xiàn)的索引
public E peek()	返回第一個元素
public E element()	返回第一個元素
public E peekFirst()	返回頭部元素
public E peekLast()	返回尾部元素
public E set(int index, E element)	設置指定位置的元素
public Object clone()	克隆該列表
public Iterator descendingIterator()	返回倒序迭代器
public int size()	返回鏈表元素個數(shù)
public ListIterator listIterator(int index)	返回從指定位置開始到末尾的迭代器
public Object[] toArray()	返回一個由鏈表元素組成的數(shù)組
public T[] toArray(T[] a)	返回一個由鏈表元素轉(zhuǎn)換類型而成的數(shù)組