Java `LinkedList`

原文： https://www.programiz.com/java-programming/linkedlist

在本教程中，我们将通过许多示例详细了解LinkedList类。

Java 集合框架的LinkedList类提供了链表数据结构的功能。

由LinkedList实现的接口

• Java List接口
• Java Queue接口
• Java Deque接口

Java 中的LinkedList实现

Java LinkedList类提供了一个双向链表实现。

链表中的每个元素称为节点。 它包含 3 个字段：

• 上一个 - 将上一个元素的地址存储在列表中。 第一个元素为null。
• 下一个 - 在列表中存储下一个元素的地址。 最后一个元素为null。
• 数据 - 存储实际数据。

链表中的元素未按顺序存储。 相反，它们分散并通过链接（上一个和下一个）连接。

在这里，链表中有 3 个元素。

• Dog - 它是第一个将null作为先前地址并将Cat作为下一个地址的元素
• Cat - 它是持有Dog作为先前地址的地址以及Cow作为下一地址的地址的第二个元素
• Cow - 它是保留Cat地址作为前一个地址，而null作为下一个元素的最后一个元素

创建一个LinkedList

这是我们如何用 Java 创建链表的方法：

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

在此，Type表示链表的类型。 例如，

// create Integer type linked list
LinkedList<Integer> linkedList = new LinkedList<>();
// create String type linked list
LinkedList<String> linkedList = new LinkedList<>();

使用接口创建LinkedList

让我们举个例子。

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

在这里，我们使用List接口声明了一个链表animals1。 链表只能访问List接口的方法。

让我们再举一个例子。

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

在这里，animals2可以访问Queue接口的方法。

但是，animals3只能访问Deque和Queue接口的方法。 这是因为Deque是Queue的子接口。

LinkedList的方法

LinkedList提供了多种方法，可让我们在链表中执行不同的操作。

将元素添加到LinkedList

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

要将元素（节点）添加到链表的末尾，我们使用add()方法。 例如，

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        // Add elements to LinkedList
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);
    }
}

输出

LinkedList: [Dog, Cat, Horse]

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

我们还可以使用索引将元素添加到链表中。 例如，

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        // Add elements using indexes
        animals.add(0,"Dog");
        animals.add(1,"Cat");
        animals.add(2,"Horse");
        System.out.println("LinkedList: " + animals);
    }
}

输出：

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");
        // Add all elements of mammals in animals
        animals.addAll(mammals);
        System.out.println("Animals: " + animals);
    }
}

输出：

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<>();
        // Creating an object of ListIterator
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.add("Dog");
        listIterate.add("Cat");
        System.out.println("LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Cat]

访问LinkedList元素

1.访问元素：使用get()方法

要访问链表中的元素，我们可以使用get()方法。 例如，

import java.util.LinkedList;
class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();
        // Add elements in the linked list
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);
        // Get the element from the linked list
        String str = animals.get(1);
        System.out.print("Element at index 1: " + str);
    }
}

输出：

LinkedList: [Dog, Horse, Cat]
Element at index 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<>();
        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        // Creating an object of Iterator
        Iterator<String> iterate = animals.iterator();
        System.out.print("LinkedList: ");
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

输出：

LinkedList: Dog, Cat, Horse,

这里，

• hasNext() - 如果存在下一个元素，则返回true
• next() - 返回下一个元素

要了解有关Iterator的更多信息，请访问 Java Iterator接口。

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<>();
        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        // Create an object of ListIterator
        ListIterator<String> listIterate = animals.listIterator();
        System.out.print("LinkedList: ");
        while(listIterate.hasNext()) {
            System.out.print(listIterate.next());
            System.out.print(", ");
        }
        // Iterate backward
        System.out.print("\nReverse LinkedList: ");
        while(listIterate.hasPrevious()) {
            System.out.print(listIterate.previous());
            System.out.print(", ");
        }
    }
}

输出：

LinkedList: Dog, Horse, Cat,
Reverse LinkedList: Cat, Horse, Dog,

Here,

• hasNext() - 如果存在下一个元素，则返回true
• next() - 返回下一个元素
• hasPrevious() - 如果先前存在元素，则返回true
• previous() - 返回上一个元素

要了解有关ListIterator的更多信息，请访问 Java ListIterator接口。

搜索LinkedList元素

1.搜索元素：使用contains()方法

要检查链表是否包含特定元素，我们使用contains()方法。 例如，

import java.util.LinkedList;
class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();
        // Add elements in the linked list
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);
        // Checks if Dog is in the linked list
        if(animals.contains("Dog")) {
            System.out.println("Dog is in LinkedList.");
        }
    }
}

输出：

LinkedList: [Dog, Horse, Cat]
Dog is in LinkedList.

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

• indexOf() - 返回元素首次出现的索引
• lastIndexOf() - 返回元素最后一次出现的索引

例如，

import java.util.LinkedList;
class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();
        // Add elements in the linked list
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);
        // First Occurrence of Dog
        int index1 = animals.indexOf("Dog");
        System.out.println("First Occurrence of Dog: " + index1);
        // Last Occurrence of Dog
        int index2 = animals.lastIndexOf("Dog");
        System.out.println("Last Occurrence of Dog: " + index2);
    }
}

输出：

LinkedList: [Dog, Horse, Cat, Dog]
First Occurrence of Dog: 0
Last Occurrence of 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<>();
        // Add elements in the linked list
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);
        // Change elements at index 3
        animals.set(3, "Zebra");
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Horse, Cat, Dog]
New 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<>();
        // Add elements
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);
        // Creating an object of ListIterator
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();
        // Change element returned by next()
        listIterate.set("Cow");
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Cat, Horse]
New 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<>();
        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        animals.add("Zebra");
        System.out.println("LinkedList: " + animals);
        // Remove elements from index 1
        String str = animals.remove(1);
        System.out.println("Removed Element: " + str);
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList : [Dog, Horse, Cat, Zebra]
Removed Element: Horse
New 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<>();
        // Add elements
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);
        // Creating an object of ListIterator
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();
        // Remove element returned by next()
        listIterate.remove();
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Cat, Horse]
New LinkedList: [Cat, Horse]

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

要从链表中删除所有元素，我们使用clear()方法。 例如，

import java.util.LinkedList;
class Main {
    public static void main(String[] args) {
        LinkedList<String> animals= new LinkedList<>();
        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);
        // Remove all the elements
        animals.clear();
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Cat, Horse]
New LinkedList: []

注意：我们也可以使用removeAll()方法删除所有元素。 但是，clear()方法被认为比removeAll()方法更有效。

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

如果元素满足特定条件，我们也可以从链表中删除它们。 为此，我们使用removeIf ()方法。 例如，

import java.util.LinkedList;
class Main {
    public static void main(String[] args) {
        LinkedList<Integer> animals= new LinkedList<>();
        // Add elements in LinkedList
        animals.add(2);
        animals.add(3);
        animals.add(4);
        animals.add(5);
        System.out.println("LinkedList: " + animals);
        // Remove all elements less than 4
        animals.removeIf((Integer i)->i < 4);
        System.out.println("New LinkedList: " + animals);
       /** Here we have used the lambda expression
         * For now just remember
         * parameter inside removeIf() is a condition
         */
    }
}

输出：

LinkedList: [2, 3, 4, 5]
New LinkedList: [4, 5]

注意： (Integer i)->i<4是 lambda 表达式。 要了解 lambda 表达式，请访问 Java Lambda 表达式。

LinkedList作为双端队列和队列

由于LinkedList类还实现了Queue和Deque接口，因此它也可以实现这些接口的方法。 以下是一些常用方法：

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<>();
        // Add element at starting of LinkedList
        animals.addFirst("Cow");
        animals.addFirst("Dog");
        animals.addFirst("Cat");
        System.out.println("LinkedList: " + animals);
        // Add elements at the end of LinkedList
        animals.addLast("Zebra");
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Cat, Dog, Cow]
New 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<>();
        // Add elements in the linked list
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);
        // Get the first element from the linked list
        String str1 = animals.getFirst();
        System.out.println("First Element: " + str1);
        // Get the last element from the linked list
        String str2 = animals.getLast();
        System.out.println("Last Element: " + str2);
    }
}

输出：

LinkedList: [Dog, Horse, Cat]
First Element: Dog
Last Element: 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<>();

        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        // Remove the first element from LinkedList
        String str1 = animals.removeFirst();
        System.out.println("Removed Element: " + str1);

        // Remove the last element from LinkedList
        String str2 = animals.removeLast();
        System.out.println("Removed Element: " + str2);

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

输出：

LinkedList: [Dog, Horse, Cat]
Removed Element: Dog
Removed Element: Cat
New 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<>();

        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        // Access the first element of LinkedList
        String str = animals.peek();
        System.out.println("Element Accessed: " + str);
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Horse, Cat]
Element Accessed: Dog
New 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<>();

        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Horse");
        animals.add("Cat");
        System.out.println("LinkedList: " + animals);

        // Returns and removes the first element
        String str = animals.poll();
        System.out.println("Removed Element: " + str);
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Horse, Cat]
Removed Element: Dog
New 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<>();

        // Add elements in LinkedList
        animals.add("Dog");
        animals.add("Horse");
        System.out.println("LinkedList: " + animals);

        // Adds element at the end of LinkedList
        animals.offer("Cat");
        System.out.println("New LinkedList: " + animals);
    }
}

输出：

LinkedList: [Dog, Horse]
New LinkedList: [Dog, Horse, Cat]

迭代LinkedList

1.使用forEach循环

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        // Creating a linked list
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        // Using forEach loop
        System.out.println("Accessing linked list elements:");
        for(String animal: animals) {
            System.out.print(animal);
            System.out.print(", ");
        }
    }
}

输出：

LinkedList: [Cow, Cat, Dog]
Accessing linked list elements:
Cow, Cat, Dog,

2.使用for循环

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        // Creating a linked list
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        // Using for loop
        System.out.println("Accessing linked list elements:");
        for(int i=0; i < animals.size(); i++) {
            System.out.print(animals.get(i));
            System.out.print(", ");
        }
    }
}

输出：

LinkedList: [Cow, Cat, Dog]
Accessing linked list elements:
Cow, Cat, Dog,

在两个示例中，我们都使用循环访问了链表的各个元素。

3.使用iterator()方法

我们可以使用iterator()方法访问链表的元素。 为了使用此方法，我们必须导入java.util.Iterator包。

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

class Main {
    public static void main(String[] args) {
        // Creating a linked list
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        // Using the iterator() method
        System.out.println("LinkedList using the iterator() method:");
        Iterator<String> iterate = animals.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

输出：

LinkedList: [Cow, Cat, Dog]
LinkedList using the iterator() method:
Cow, Cat, Dog,

LinkedList与ArrayList

LinkedList和ArrayList都实现Collections框架的List接口。 但是，它们之间存在一些差异。