Java LinkedList特性

• 双向链表实现，实现了 List 和 Deque 接口。因此，它也可以用作队列、双端队列或者堆栈。
• 允许所有元素，包括重复项和 NULL。
• LinkedList 维护元素的插入顺序。
• 它不是同步的。如果多个线程并发访问一个链表，并且至少有一个线程在结构上修改了链表，则必须进行外部同步。
• 使用 Collections.synchronizedList(new LinkedList()) 获取同步链表。
• 此类返回的迭代器是快速失败的，可能会抛出 ConcurrentModificationException。
• 它没有实现 RandomAccess 接口。

LinkedList 链表层次结构

LinkedList 类扩展了 AbstractSequentialList 类并实现了 List 和 Deque 接口。
这里的“E”是链表存储的值的类型。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
	//implementation
}

Java LinkedList 类是List和Deque接口的双向链表实现。
它实现了所有可选的列表操作，并允许所有元素（包括空值）。

LinkedList的构造函数

• LinkedList() ：初始化一个空的 LinkedList 实现。
• LinkedListExample(Collection c) ：初始化包含指定集合元素的 LinkedList，按照集合迭代器返回的顺序。

Java LinkedList 示例

添加、删除、迭代LinkedList

import java.util.LinkedList;
import java.util.ListIterator;
public class LinkedListExample 
{
    public static void main(String[] args) 
    {
        //创建链表
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");

        System.out.println(linkedList);

        // 添加元素到指定位置
        linkedList.add(4, "A");
        linkedList.add(5, "A");

        System.out.println(linkedList);

        // 删除元素
        linkedList.remove("A");		//removes A
        linkedList.remove(0);		//removes B

        System.out.println(linkedList);

        //迭代
        ListIterator<String> itrator = linkedList.listIterator();
        while (itrator.hasNext()) {
            System.out.println(itrator.next());
        }
    }
}

输出:

[A, B, C, D]
[A, B, C, D, A, A]
[C, D, A, A]
C
D
A
A

在 Array 和 LinkedList 之间转换

将 LinkedList 转换为数组并将数组转换为LinkedList

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

linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
//1. Java 将linkedList 转换为数组
String array[] = new String[linkedList.size()];
linkedList.toArray(array);
System.out.println(Arrays.toString(array));
//2. Java 将 Array 转换为 LinkedList
LinkedList<String> linkedListNew = new LinkedList<>(Arrays.asList(array));
System.out.println(linkedListNew);

输出:

[A, B, C, D]
[A, B, C, D]

Java如何对链表进行排序

使用 Collections.sort() 方法对 LinkedList 进行排序的 Java 示例。
请注意，对于对象的自定义排序，我们可以使用 Collections.sort(linkedList,comparator) 方法。

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("C");
linkedList.add("B");
linkedList.add("D");
//Unsorted
System.out.println(linkedList);
//1. 排序列表
Collections.sort(linkedList);
System.out.println(linkedList);

//2. 自定义排序
Collections.sort(linkedList, Collections.reverseOrder());
System.out.println(linkedList);

输出:

[A, C, B, D]
[A, B, C, D]
[D, C, B, A]

LinkedList的方法

• boolean add(Object o) ：将指定的元素添加到列表的末尾。
• void add(int index, Object element) ：在列表中的指定位置索引处插入指定元素。
• void addFirst(Object o) ：在列表的开头插入给定的元素。
• void addLast(Object o) ：将给定元素添加到列表的末尾。
• int size() : 返回列表中元素的数量
• boolean contains(Object o) : 如果列表包含指定元素，则返回 true，否则返回 false。
• boolean remove(Object o) ：删除列表中第一次出现的指定元素。
• Object getFirst() ：返回列表中的第一个元素。
• Object getLast() ：返回列表中的最后一个元素。
• int indexOf(Object o) ：返回指定元素第一次出现在列表中的索引，如果列表不包含指定元素，则返回 -1.
• lastIndexOf(Object o) ：返回指定元素最后一次出现在列表中的索引，如果列表不包含指定元素，则返回 -1.
• Iterator iterator() ：以适当的顺序返回此列表中元素的迭代器。
• Object[] toArray() ：以适当的顺序返回一个包含此列表中所有元素的数组。
• List subList(int fromIndex, int toIndex) ：返回此列表中指定 fromIndex（包含）和 toIndex（不包含）之间的部分的视图。