Java LinkedList(链表)

Java LinkedList(链表) - Java教程

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

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

由LinkedList实现的接口

链表实现的接口

Java中的LinkedList实现

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

链表中的节点

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

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

链表中的元素不是按顺序存储的。相反，它们是分散的，并通过链接(Prev和Next)连接。

Java中LinkedList的工作

在这里，链接列表中包含3个元素。

Dog - 第一个元素将null作为前一个地址，并将Cat的地址作为下一个地址
Cat - 第二个元素将Dog的地址作为前一个地址，将Cow的地址作为下一个地址
Cow - 最后一个元素将Cat的地址作为前一个地址，并将null作为下一个元素

创建一个LinkedList

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

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

此处，Type表示链接列表的类型。例如，

//创建整数类型的链表
LinkedList<Integer> linkedList = new LinkedList<>();

//创建字符串类型的链表
LinkedList<String> linkedList = new LinkedList<>();

使用接口创建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 提供了各种方法，使我们可以在链表中执行不同的操作。

将元素添加到LinkedList

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

要将元素（节点）添加到链表的末尾，我们使用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);
    }
}

输出结果

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);
    }
}

输出结果

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);
    }
}

输出结果

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<>();

        //创建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<>();

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

        //从链表中获取元素
        String str = animals.get(1);
        System.out.print("索引1处的元素: " + str);
    }
}

输出结果

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");

        //创建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() - 返回下一个元素

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");

        //创建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(", ");
        }
    }
}

输出结果

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中。");
        }
    }
}

输出结果

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

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

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

例如，

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);

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

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

输出结果

LinkedList: [Dog, Horse, Cat, Dog]
第一次出现Dog的索引值: 0
最后一次出现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);
    }
}

输出结果

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);

        //创建ListIterator对象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();

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

输出结果

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);
    }
}

输出结果

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);

        //创建ListIterator对象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();

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

输出结果

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);
    }
}

输出结果

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表达式
       *  现在请记住
       *  removeIf()中的参数是一个条件
       */
    }
}

输出结果

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

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

LinkedList作为Deque和Queue

由于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<>();

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

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

输出结果

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);
    }
}

输出结果

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);
    }
}

输出结果

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);
    }
}

输出结果

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);
    }
}

输出结果

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);
    }
}

输出结果

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

遍历LinkedList迭代

1.使用forEach循环遍历

示例

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        //创建一个链表
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        //使用forEach循环
        System.out.println("访问链表元素:");
        for(String animal: animals) {
            System.out.print(animal);
            System.out.print(", ");
        }
    }
}

输出结果

LinkedList: [Cow, Cat, Dog]
访问链表元素:
Cow, Cat, Dog,

2.使用for循环

示例

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        //创建一个链表
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        //使用for循环
        System.out.println("访问链表元素:");
        for(int i=0; i < animals.size(); i++) {
            System.out.print(animals.get(i));
            System.out.print(", ");
        }
    }
}

输出结果

LinkedList: [Cow, Cat, Dog]
访问链表元素:
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) {
        //创建一个链表
        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(", ");
        }
    }
}

输出结果

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

LinkedList与ArrayList

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

LinkedList	ArrayList
在单个位置存储3个值（上一个地址，数据和下一个地址）	将单个值存储在单个位置
提供list的双链接列表实现	提供可调整大小的数组实现
每当添加元素时，上一个和下一个地址都会更改	每当添加元素时，该位置之后的所有元素都会移动
要访问元素，我们需要从头开始迭代到元素	可以使用索引随机访问元素。

Java Deque 接口 Java PriorityQueue

Java 教程

Java 基础教程

Java 流程控制

Java 数组

Java 面向对象(I)

Java 面向对象(II)

Java 面向对象(III)

Java 异常处理

Java 列表(List)

Java Queue(队列)

Java Map集合

Java Set集合

Java 输入输出(I/O)

Java Reader/Writer

Java 其他主题

Java LinkedList(链表) - Java教程

由LinkedList实现的接口

Java中的LinkedList实现

创建一个LinkedList

使用接口创建LinkedList

LinkedList的方法

将元素添加到LinkedList

访问LinkedList元素

查找 LinkedList 元素

更改 LinkedList 元素

删除LinkedList元素

LinkedList作为Deque和Queue

addFirst()和addLast()方法

getFirst()和getLast()方法

removeFirst()和removeLast()方法

peek()方法

poll()方法

offer()方法

遍历LinkedList迭代

LinkedList与ArrayList