Java LinkedList(链表) - Java教程

由网友 大卫 发布 阅读 11

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() - 返回上一个元素

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接口。 但是,它们之间存在一些差异。

LinkedListArrayList

在单个位置存储3个值(上一个地址,数据和下一个地址)

将单个值存储在单个位置

提供list的双链接列表实现

提供可调整大小的数组实现

每当添加元素时,上一个和下一个地址都会更改

每当添加元素时,该位置之后的所有元素都会移动

要访问元素,我们需要从头开始迭代到元素

可以使用索引随机访问元素。

Java Deque 接口 Java PriorityQueue