Java LinkedList(鏈表)

在本教程中，我們將通過許多示例詳細了解LinkedList類。

Java集合框架的LinkedList類提供了鏈表數(shù)據(jù)結(jié)構(gòu)的功能。

由LinkedList實現(xiàn)的接口

• Java List接口

• Java Queue接口

• Java Deque接口

Java中的LinkedList實現(xiàn)

Java LinkedList類提供了雙向鏈表實現(xiàn)。

鏈表中的每個元素都稱為節(jié)點。它包含3個字段：

• Prev - 將前一個元素的地址存儲在列表中。 第一個元素為null。

• Next - 在列表中存儲下一個元素的地址。 最后一個元素為null。

• Data - 存儲實際數(shù)據(jù)。

鏈表中的元素不是按順序存儲的。相反，它們是分散的，并通過鏈接(Prev和Next)連接。

在這里，鏈接列表中包含3個元素。

• Dog - 第一個元素將null作為前一個地址，并將Cat的地址作為下一個地址

• Cat - 第二個元素將Dog的地址作為前一個地址，將Cow的地址作為下一個地址

• Cow - 最后一個元素將Cat的地址作為前一個地址，并將null作為下一個元素

創(chuàng)建一個LinkedList

這是我們?nèi)绾斡肑ava創(chuàng)建鏈接列表的方法：

LinkedList<Type> linkedList = new LinkedList<>();

此處，Type表示鏈接列表的類型。例如，

//創(chuàng)建整數(shù)類型的鏈表
LinkedList<Integer> linkedList = new LinkedList<>();

//創(chuàng)建字符串類型的鏈表
LinkedList<String> linkedList = new LinkedList<>();

使用接口創(chuàng)建LinkedList

讓我們舉個實例。

List<String> animals1 = new LinkedList<>();

在這里，我們使用List接口聲明了一個鏈表animals1，鏈表只能訪問List接口的方法。

讓我們再舉一個實例。

Queue<String> animals2 = new LinkedList<>();
Deque<String> animals3 = new LinkedList<>();

在這里，animal2可以訪問Queue接口的方法。

但是，animal3只能訪問Deque和Queue接口的方法。 這是因為Deque是Queue的子接口。

LinkedList的方法

LinkedList 提供了各種方法，使我們可以在鏈表中執(zhí)行不同的操作。

將元素添加到LinkedList

1.添加元素：使用add()方法

要將元素（節(jié)點）添加到鏈表的末尾，我們使用add()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();

        //將元素添加到LinkedList
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Cat, Horse]

2.添加元素：使用索引號

我們還可以使用索引將元素添加到鏈表中。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();

        //使用索引添加元素
        animals.add(0,"Dog");
        animals.add(1,"Cat");
        animals.add(2,"Horse");

        System.out.println("LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Cat, Horse]

3.添加元素：將一個鏈表添加到另一個鏈表

要將鏈表的所有元素添加到另一個鏈表，我們使用addAll()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args){
        LinkedList<String> mammals = new LinkedList<>();

        mammals.add("Dog");
        mammals.add("Cat");
        mammals.add("Horse");
        System.out.println("Mammals: " + mammals);

        LinkedList<String> animals = new LinkedList<>();
        animals.add("Crocodile");

        //把mammals的所有元素都添加到animals上
        animals.addAll(mammals);
        System.out.println("Animals: " + animals);
    }
}

輸出結(jié)果

Mammals: [Dog, Cat, Horse]
Animals: [Crocodile, Dog, Cat, Horse]

4.添加元素：使用listIterator()方法

我們還可以使用listsIterator()方法將元素添加到鏈表中。要使用它，我們必須導入java.util.ListIterator包。例如，

import java.util.ArrayList;
import java.util.ListIterator;

class Main {
    public static void main(String[] args) {
        ArrayList<String> animals= new ArrayList<>();

        //創(chuàng)建ListIterator對象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.add("Dog");
        listIterate.add("Cat");

        System.out.println("LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Cat]

訪問LinkedList元素

1.訪問元素：使用get()方法

要訪問鏈表中的元素，我們可以使用get()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        //從鏈表中獲取元素
        String str = animals.get(1);
        System.out.print("索引1處的元素: " + str);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat]
索引1處的元素: Horse

2.訪問元素：使用iterator()方法

要遍歷鏈表的元素，我們可以使用iterator()方法。我們必須導入java.util.Iterator包才能使用此方法。例如，

import java.util.LinkedList;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");

        //創(chuàng)建Iterator的對象
        Iterator<String> iterate = animals.iterator();
        System.out.print("LinkedList: ");

        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

輸出結(jié)果

LinkedList: Dog, Cat, Horse,

這里，

• hasNext() - 如果存在下一個元素，則返回true

• next() - 返回下一個元素

3.訪問元素：使用listIterator()方法

我們還可以使用listIterator()方法來迭代鏈接列表的元素。要使用此方法，我們必須導入java.util.ListIterator包。

listsIterator()方法更適合用于鏈表。這是因為listIterator()的對象也可以向后迭代。例如

import java.util.LinkedList;
import java.util.ListIterator;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");

        //創(chuàng)建ListIterator對象
        ListIterator<String> listIterate = animals.listIterator();
        System.out.print("LinkedList: ");

        while(listIterate.hasNext()) {
            System.out.print(listIterate.next());
            System.out.print(", ");
        }

        // 向后遍歷
        System.out.print("\n反向LinkedList: ");

        while(listIterate.hasPrevious()) {
            System.out.print(listIterate.previous());
            System.out.print(", ");
        }
    }
}

輸出結(jié)果

LinkedList: Dog, Horse, Cat,
反向LinkedList: Cat, Horse, Dog,

這里，

• hasNext() - 如果存在下一個元素，則返回true

• next() - 返回下一個元素

• hasPrevious() - 如果存在先前的元素，則返回true

• previous() - 返回上一個元素

查找 LinkedList 元素

1.查找元素：使用contains()方法

要查找鏈表是否包含特定元素，我們使用contains()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        //檢查Dog是否在鏈表中
        if(animals.contains("Dog")) {
            System.out.println("Dog在LinkedList中。");
        }
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat]
Dog在LinkedList中。

2.搜索元素：使用indexOf()方法

• indexOf() - 返回元素第一次出現(xiàn)的索引

• lastIndexOf() - 返回元素最后一次出現(xiàn)的索引

例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        // 在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        //第一次出現(xiàn)Dog
        int index1 = animals.indexOf("Dog");
        System.out.println("第一次出現(xiàn)Dog的索引值: " + index1);

        //最后一次出現(xiàn)Dog
        int index2 = animals.lastIndexOf("Dog");
        System.out.println("最后一次出現(xiàn)Dog的索引值: " + index2);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat, Dog]
第一次出現(xiàn)Dog的索引值: 0
最后一次出現(xiàn)Dog的索引值: 3

注意：如果找不到指定的元素，indexOf()和lastIndexOf()都返回-1。

更改 LinkedList 元素

1.更改元素：使用set()方法

要更改鏈接列表的元素，我們可以使用set()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        //更改索引值為3的元素
        animals.set(3, "Zebra");
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat, Dog]
新的LinkedList: [Dog, Horse, Cat, Zebra]

2.更改元素：使用listIterator()方法

我們還可以使用listIterator()方法更改鏈接列表中的元素。例如，

import java.util.ArrayList;
import java.util.ListIterator;

class Main {
    public static void main(String[] args) {
        ArrayList<String> animals= new ArrayList<>();

        // 在鏈表中添加元素
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);

        //創(chuàng)建ListIterator對象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();

        //更改由next()返回的元素
        listIterate.set("Cow");
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Cat, Horse]
新的LinkedList: [Cow, Cat, Horse]

刪除LinkedList元素

1.刪除元素：使用remove()方法

要從鏈接列表中刪除元素，我們可以使用remove()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        animals.add("Zebra");
        System.out.println("LinkedList: " + animals);

        //刪除索引值為1的元素
        String str = animals.remove(1);
        System.out.println("刪除元素: " + str);

        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList : [Dog, Horse, Cat, Zebra]
刪除元素: Horse
新的LinkedList: [Dog, Cat, Zebra]

2.刪除元素：使用listIterator()方法

我們還可以使用listsIterator()方法從鏈接列表中刪除元素。例如，

import java.util.ArrayList;
import java.util.ListIterator;

class Main {
    public static void main(String[] args) {
        ArrayList<String> animals= new ArrayList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);

        //創(chuàng)建ListIterator對象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();

        //刪除next()返回的元素
        listIterate.remove();
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Cat, Horse]
新的LinkedList: [Cat, Horse]

3.刪除元素：使用clear()方法

要從鏈接列表中刪除所有元素，我們使用clear()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);

        //刪除所有元素
        animals.clear();
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Cat, Horse]
新的LinkedList: []

注意：我們還可以使用removeAll()方法刪除所有元素。但是，clear()方法比removeAll()方法更高效。

4.刪除元素：使用removeIf()方法

如果元素滿足特定條件，我們也可以從鏈表中刪除它們。為此，我們使用removeIf()方法。例如，

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        LinkedList<Integer> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add(2);
        animals.add(3);
        animals.add(4);
        animals.add(5);
        System.out.println("LinkedList: " + animals);

        // 刪除所有小于4的元素
        animals.removeIf((Integer i)->i < 4);
        System.out.println("新的LinkedList: " + animals);

       /** 在這里我們使用了lambda表達式
       *  現(xiàn)在請記住
       *  removeIf()中的參數(shù)是一個條件
       */
    }
}

輸出結(jié)果

LinkedList: [2, 3, 4, 5]
新的LinkedList: [4, 5]

注意： (Integer i)->i<4 是lambda表達式。要了解lambda表達式，請訪問Java Lambda表達式

LinkedList作為Deque和Queue

由于LinkedList類還實現(xiàn)了Queue和Deque接口，因此它也可以實現(xiàn)這些接口的方法。 以下是一些常用方法：

addFirst()和addLast()方法

• addFirst() - 將指定的元素添加到鏈接列表的開頭

• addLast() - 將指定的元素添加到鏈接列表的末尾

例如，

import java.util.LinkedList;
import java.util.Deque;

class Main {
    public static void main(String[] args){
        Deque<String> animals = new LinkedList<>();

        //在LinkedList的開始處添加元素
        animals.addFirst("Cow");
        animals.addFirst("Dog");
        animals.addFirst("Cat");
        System.out.println("LinkedList: " + animals);

        //在LinkedList的末尾添加元素
        animals.addLast("Zebra");
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Cat, Dog, Cow]
新的LinkedList: [Cat, Dog, Cow, Zebra]

getFirst()和getLast()方法

• getFirst() - 返回第一個元素

• getLast() - 返回最后一個元素

例如，

import java.util.LinkedList;
import java.util.Deque;

class Main {
    public static void main(String[] args) {
        Deque<String> animals= new LinkedList<>();

        // 在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        //從鏈表中獲取第一個元素
        String str1 = animals.getFirst();
        System.out.println("第一個元素: " + str1);

        //從鏈表中獲取最后一個元素
        String str2 = animals.getLast();
        System.out.println("最后一個元素: " + str2);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat]
第一個元素: Dog
最后一個元素: Cat

removeFirst()和removeLast()方法

• removeFirst() - 刪除第一個元素

• removeLast() - 刪除最后一個元素

例如，

import java.util.LinkedList;
import java.util.Deque;

class Main {
    public static void main(String[] args) {
        Deque<String> animals= new LinkedList<>();

        // 在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        //從LinkedList刪除第一個元素
        String str1 = animals.removeFirst();
        System.out.println("刪除的元素: " + str1);

        //從LinkedList刪除最后一個元素
        String str2 = animals.removeLast();
        System.out.println("刪除的元素: " + str2);

        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat]
刪除的元素: Dog
刪除的元素: Cat
新的LinkedList: [Horse]

peek()方法

peek()方法返回鏈表的第一個元素（頭）。例如，

import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) {
        Queue<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        //訪問LinkedList的第一個元素
        String str = animals.peek();
        System.out.println("元素訪問: " + str);
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat]
元素訪問: Dog
新的LinkedList: [Dog, Horse, Cat]

poll()方法

poll()方法返回并從鏈表中刪除第一個元素。例如，

import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) {
        Queue<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        //返回并刪除第一個元素
        String str = animals.poll();
        System.out.println("刪除的元素: " + str);
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse, Cat]
刪除的元素: Dog
新的LinkedList: [Horse, Cat]

offer()方法

該offer()方法將指定的元素添加到鏈接列表的末尾。例如，

import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) {
        Queue<String> animals= new LinkedList<>();

        //在鏈表中添加元素
        animals.add("Dog");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);

        //在LinkedList的末尾添加元素
        animals.offer("Cat");
        System.out.println("新的LinkedList: " + animals);
    }
}

輸出結(jié)果

LinkedList: [Dog, Horse]
新的LinkedList: [Dog, Horse, Cat]

遍歷LinkedList迭代

1.使用forEach循環(huán)遍歷

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        //創(chuàng)建一個鏈表
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        //使用forEach循環(huán)
        System.out.println("訪問鏈表元素:");
        for(String animal: animals) {
            System.out.print(animal);
            System.out.print(", ");
        }
    }
}

輸出結(jié)果

LinkedList: [Cow, Cat, Dog]
訪問鏈表元素:
Cow, Cat, Dog,

2.使用for循環(huán)

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        //創(chuàng)建一個鏈表
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        //使用for循環(huán)
        System.out.println("訪問鏈表元素:");
        for(int i=0; i < animals.size(); i++) {
            System.out.print(animals.get(i));
            System.out.print(", ");
        }
    }
}

輸出結(jié)果

LinkedList: [Cow, Cat, Dog]
訪問鏈表元素:
Cow, Cat, Dog,

在兩個示例中，我們都使用循環(huán)訪問鏈表的各個元素。

3.使用iterator()方法

我們可以使用iterator()方法訪問鏈表的元素。為了使用這種方法，我們必須導入java.util.Iterator包。

import java.util.LinkedList;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {
        //創(chuàng)建一個鏈表
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        //使用iterator()方法
        System.out.println("LinkedList使用iterator()方法:");
        Iterator<String> iterate = animals.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

輸出結(jié)果

LinkedList: [Cow, Cat, Dog]
LinkedList使用iterator()方法:
Cow, Cat, Dog,

LinkedList與ArrayList

LinkedList和ArrayList都實現(xiàn)Collections框架的List接口。 但是，它們之間存在一些差異。