Java 集合框架（三）—— LinkedList

三、链表 —— LinkedList

　　

　　ArrayList 虽然好用，但是数组和数组列表都有一个重大的缺陷：从数组的中间位置删除一个元素要付出很大的代价，其原因是数组中处于被删除元素之后的所有元素都要向数组的前端移动。但是，具有链表结构的 LinkedList 则没有这个问题。

　　LinkedList 的底层结构是类似数据结构里边的双向链表，可以代价比较小地实现元素的增加和删除。

　　

　　LinkedList 有一个如上图的内部类，这个类就是实现了双向链表的功能。

　　1、构造方法

　　LinkedList()

　　Constructs an empty list. 构造方法没什么特殊的。

　　2、常用方法

　　1）add 方法

　　默认添加元素到链表的最后一位

LinkedList<String> list = new LinkedList<>();
//----- 添加操作 ----
list.add("1");
list.add("2");
list.add("3");

// 将 "4" 添加到第一个位置
list.add(0, "4");

　　2）addFirst、removeFirst 和 getFirst 方法

　　分别为将元素添加到第一个位置，删除第一个位置的元素，获取第一个位置的元素

System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\"");
// 将 "10" 添加到第一个位置
list.addFirst("10");
System.out.println("list: " + list);
// 将第一个元素删除
System.out.println("list.removeFirst(): " + list.removeFirst());
System.out.println("list: " + list);
// 获取第一个元素
System.out.println("list.getFirst(): " + list.getFirst());

　　结果为：

Test "addFirst(), removeFirst(), getFirst()"
list: [10, 4, 1, 2, 3]
list.removeFirst(): 10
list: [4, 1, 2, 3]
list.getFirst(): 4

　　3）offerFirst、pollFirst 和 peekFirst 方法

　　比上面的上个方法多了个返回值

System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\"");
// 将 "10" 添加到第一个位置，返回 true
System.out.println(list.offerFirst("10"));
System.out.println("list: " + list);
// 将第一个元素删除，失败则返回 null
System.out.println("list.pollFirst(): " + list.pollFirst());
System.out.println("list: " + list);
// 获取第一个元素，失败则返回 null
System.out.println("list.peekFirst(): " + list.peekFirst());

　　结果为：

Test "offerFirst(), pollFirst(), peekFirst()"
true
list: [10, 4, 1, 2, 3]
list.pollFirst(): 10
list: [4, 1, 2, 3]
list.peekFirst(): 4

　　4）addLast、removeLast 和 getLast 方法

　　分别为添加一个元素到最后一个位置，删除最后一个位置的元素以及获取最后一个位置的元素

System.out.println("\nTest \"addLast(), removeLast(), getLast()\"");
// 将 "20" 添加到最后一个位置
list.addLast("20");
System.out.println("list: " + list);
// 将最后一个元素删除
System.out.println("list.removeLast(): " + list.removeLast());
System.out.println("list: " + list);
// 获取最后一个元素
System.out.println("list.getLast(): " + list.getLast());

　　结果为：

Test "addLast(), removeLast(), getLast()"
list: [4, 1, 2, 3, 20]
list.removeLast(): 20
list: [4, 1, 2, 3]
list.getLast(): 3

 　　5）offerLast、pollLast 和 peekLast 方法

　　同理，比上面的方法多个返回值

System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\"");
// 将 "20" 添加到第一个位置，返回 true
list.offerLast("20");
System.out.println("list: " + list);
// 将第一个元素删除，失败则返回 null
System.out.println("list.pollLast(): " + list.pollLast());
System.out.println("list: " + list);
// 获取第一个元素，失败则返回 null
System.out.println("list.peekLast(): " + list.peekLast());

　　结果为：

Test "offerLast(), pollLast(), peekLast()"
list: [4, 1, 2, 3, 20]
list.pollLast(): 20
list: [4, 1, 2, 3]
list.peekLast(): 3

　　6）set 和 get 方法

// 将第 3 个元素设置为 300，不建议在 LinkedList 中使用此操作，因为效率低
list.set(2, "300");
// 获取第 3 个元素，不建议在 LinkedList 中使用此操作，因为效率低
System.out.println("\nget(2): " + list.get(2));
System.out.println("list: " + list);

　　结果为：

get(2): 300
list: [4, 1, 300, 3]

　　7）toArray 方法

　　有两个实现：toArray(), toArray(T[] a)

　　第二个不需要进行强制类型转换，而且转换后的数组长度和 a 的长度有关，小于等于 list 的 size，则返回 list 的元素，大于则补 null

// 将 LinkedList 转换为数组
String[] arr = list.toArray(new String[list.size()]);
for (String str : arr) {
    System.out.println("str: " + str);
}

　　结果为：

str: 4
str: 1
str: 300
str: 3

　　如果参数数组长度大于 list 的 size，则返回 null

// 将 LinkedList 转换为数组
String[] arr = list.toArray(new String[list.size() + 5]);
for (String str : arr) {
    System.out.println("str: " + str);
}

　　结果为：

str: 4
str: 1
str: 300
str: 3
str: null
str: null
str: null
str: null
str: null

　　8）size、clear 和 isEmpty 方法

// 输出大小
System.out.println("size: " + list.size());
// 清空 LinkedList
list.clear();
// 判断 LinkedList 是否为空
System.out.println("isEmpty(): " + list.isEmpty() + "\n");

　　结果为：

size: 4
isEmpty(): true

特别感谢：

1、Java 集合系列 05 之 LinkedList 详细介绍 (源码解析) 和使用示例

2、《Core Java Volume I》