java之LinkedList详细介绍

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1 LinkedList介绍

LinkedList简介

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。

LinkedList构造函数

// 默认构造函数
LinkedList()// 创建一个LinkedList，保护Collection中的全部元素。
LinkedList(Collection<? extends E> collection)

LinkedList的API

LinkedList的API
boolean add(E object)
void add(int location, E object)
boolean addAll(Collection<? extends E> collection)
boolean addAll(int location, Collection<? extends E> collection)
void addFirst(E object)
void addLast(E object)
void clear()
Object clone()
boolean contains(Object object)
Iterator<E> descendingIterator()
E element()
E get(int location)
E getFirst()
E getLast()
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
boolean offer(E o)
boolean offerFirst(E e)
boolean offerLast(E e)
E peek()
E peekFirst()
E peekLast()
E poll()
E pollFirst()
E pollLast()
E pop()
void push(E e)
E remove()
E remove(int location)
boolean remove(Object object)
E removeFirst()
boolean removeFirstOccurrence(Object o)
E removeLast()
boolean removeLastOccurrence(Object o)
E set(int location, E object)
int size()
<T> T[] toArray(T[] contents)
Object[] toArray()

AbstractSequentialList简介

在介绍LinkedList的源码之前，先介绍一下AbstractSequentialList。毕竟，LinkedList是AbstractSequentialList的子类。

AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。

此外，我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

2 LinkedList数据结构

LinkedList的继承关系

java.lang.Object
↳ java.util.AbstractCollection<E>
↳ java.util.AbstractList<E>
↳ java.util.AbstractSequentialList<E>
↳ java.util.LinkedList<E>public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

LinkedList与Collection关系如下图：

LinkedList的本质是双向链表。
(01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
(02) LinkedList包含两个重要的成员：header 和 size。
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
size是双向链表中节点的个数。

3 LinkedList源码解析

总结：
(01) LinkedList 实际上是通过双向链表去实现的。
它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
(02) 从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。
(03) LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。
(04) LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
(05) 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

总结起来如下表格：

第一个元素（头部）最后一个元素（尾部）
抛出异常特殊值抛出异常特殊值
插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
移除 removeFirst() pollFirst() removeLast() pollLast()
检查 getFirst() peekFirst() getLast() peekLast()

(06) LinkedList可以作为FIFO(先进先出)的队列，作为FIFO的队列时，下表的方法等价：

队列方法等效方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

(07) LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：

栈方法等效方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

4 LinkedList遍历方式

LinkedList遍历方式

LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。

for(Iterator iter = list.iterator(); iter.hasNext();)
iter.next();

(02) 通过快速随机访问遍历LinkedList

int size = list.size();
for (int i=0; i<size; i++) {
list.get(i);
}

(03) 通过另外一种for循环来遍历LinkedList

for (Integer integ:list)
;

(04) 通过pollFirst()来遍历LinkedList

while(list.pollFirst() != null)
;

(05) 通过pollLast()来遍历LinkedList

while(list.pollLast() != null)
;

(06) 通过removeFirst()来遍历LinkedList

try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
}

(07) 通过removeLast()来遍历LinkedList

try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
}

测试这些遍历方式效率的代码如下：

import java.util.List;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;/*
* @desc 测试LinkedList的几种遍历方式和效率
*
* @author skywang
*/
public class LinkedListThruTest {
public static void main(String[] args) {
// 通过Iterator遍历LinkedList
iteratorLinkedListThruIterator(getLinkedList()) ; // 通过快速随机访问遍历LinkedList
iteratorLinkedListThruForeach(getLinkedList()) ; // 通过for循环的变种来访问遍历LinkedList
iteratorThroughFor2(getLinkedList()) ; // 通过PollFirst()遍历LinkedList
iteratorThroughPollFirst(getLinkedList()) ; // 通过PollLast()遍历LinkedList
iteratorThroughPollLast(getLinkedList()) ; // 通过removeFirst()遍历LinkedList
iteratorThroughRemoveFirst(getLinkedList()) ; // 通过removeLast()遍历LinkedList
iteratorThroughRemoveLast(getLinkedList()) ;
} private static LinkedList getLinkedList() {
LinkedList llist = new LinkedList();
for (int i=0; i<100000; i++)
llist.addLast(i); return llist;
}
/**
* 通过快迭代器遍历LinkedList
*/
private static void iteratorLinkedListThruIterator(LinkedList<Integer> list) {
if (list == null)
return ; // 记录开始时间
long start = System.currentTimeMillis(); for(Iterator iter = list.iterator(); iter.hasNext();)
iter.next(); // 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorLinkedListThruIterator：" + interval+" ms");
} /**
* 通过快速随机访问遍历LinkedList
*/
private static void iteratorLinkedListThruForeach(LinkedList<Integer> list) {
if (list == null)
return ; // 记录开始时间
long start = System.currentTimeMillis(); int size = list.size();
for (int i=0; i<size; i++) {
list.get(i);
}
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorLinkedListThruForeach：" + interval+" ms");
} /**
* 通过另外一种for循环来遍历LinkedList
*/
private static void iteratorThroughFor2(LinkedList<Integer> list) {
if (list == null)
return ; // 记录开始时间
long start = System.currentTimeMillis(); for (Integer integ:list)
; // 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughFor2：" + interval+" ms");
} /**
* 通过pollFirst()来遍历LinkedList
*/
private static void iteratorThroughPollFirst(LinkedList<Integer> list) {
if (list == null)
return ; // 记录开始时间
long start = System.currentTimeMillis();
while(list.pollFirst() != null)
; // 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughPollFirst：" + interval+" ms");
} /**
* 通过pollLast()来遍历LinkedList
*/
private static void iteratorThroughPollLast(LinkedList<Integer> list) {
if (list == null)
return ; // 记录开始时间
long start = System.currentTimeMillis();
while(list.pollLast() != null)
; // 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughPollLast：" + interval+" ms");
} /**
* 通过removeFirst()来遍历LinkedList
*/
private static void iteratorThroughRemoveFirst(LinkedList<Integer> list) {
if (list == null)
return ; // 记录开始时间
long start = System.currentTimeMillis();
try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
} // 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughRemoveFirst：" + interval+" ms");
} /**
* 通过removeLast()来遍历LinkedList
*/
private static void iteratorThroughRemoveLast(LinkedList<Integer> list) {
if (list == null)
return ; // 记录开始时间
long start = System.currentTimeMillis();
try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
} // 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughRemoveLast：" + interval+" ms");
}}

由此可见，遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。
无论如何，千万不要通过随机访问去遍历LinkedList！

5 LinkedList实例

下面通过一个示例来学习如何使用LinkedList的常用API

import java.util.List;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;/*
* @desc LinkedList测试程序。
*
* @author skywang
* @email kuiwu-wang@163.com
*/
public class LinkedListTest {
public static void main(String[] args) {
// 测试LinkedList的API
testLinkedListAPIs() ; // 将LinkedList当作 LIFO(后进先出)的堆栈
useLinkedListAsLIFO(); // 将LinkedList当作 FIFO(先进先出)的队列
useLinkedListAsFIFO();
} /*
* 测试LinkedList中部分API
*/
private static void testLinkedListAPIs() {
String val = null;
//LinkedList llist;
//llist.offer("10");
// 新建一个LinkedList
LinkedList llist = new LinkedList();
//---- 添加操作 ----
// 依次添加1,2,3
llist.add("1");
llist.add("2");
llist.add("3"); // 将“4”添加到第一个位置
llist.add(1, "4"); System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\"");
// (01) 将“10”添加到第一个位置。失败的话，抛出异常！
llist.addFirst("10");
System.out.println("llist:"+llist);
// (02) 将第一个元素删除。失败的话，抛出异常！
System.out.println("llist.removeFirst():"+llist.removeFirst());
System.out.println("llist:"+llist);
// (03) 获取第一个元素。失败的话，抛出异常！
System.out.println("llist.getFirst():"+llist.getFirst()); System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\"");
// (01) 将“10”添加到第一个位置。返回true。
llist.offerFirst("10");
System.out.println("llist:"+llist);
// (02) 将第一个元素删除。失败的话，返回null。
System.out.println("llist.pollFirst():"+llist.pollFirst());
System.out.println("llist:"+llist);
// (03) 获取第一个元素。失败的话，返回null。
System.out.println("llist.peekFirst():"+llist.peekFirst()); System.out.println("\nTest \"addLast(), removeLast(), getLast()\"");
// (01) 将“20”添加到最后一个位置。失败的话，抛出异常！
llist.addLast("20");
System.out.println("llist:"+llist);
// (02) 将最后一个元素删除。失败的话，抛出异常！
System.out.println("llist.removeLast():"+llist.removeLast());
System.out.println("llist:"+llist);
// (03) 获取最后一个元素。失败的话，抛出异常！
System.out.println("llist.getLast():"+llist.getLast()); System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\"");
// (01) 将“20”添加到第一个位置。返回true。
llist.offerLast("20");
System.out.println("llist:"+llist);
// (02) 将第一个元素删除。失败的话，返回null。
System.out.println("llist.pollLast():"+llist.pollLast());
System.out.println("llist:"+llist);
// (03) 获取第一个元素。失败的话，返回null。
System.out.println("llist.peekLast():"+llist.peekLast()); // 将第3个元素设置300。不建议在LinkedList中使用此操作，因为效率低！
llist.set(2, "300");
// 获取第3个元素。不建议在LinkedList中使用此操作，因为效率低！
System.out.println("\nget(3):"+llist.get(2)); // ---- toArray(T[] a) ----
// 将LinkedList转行为数组
String[] arr = (String[])llist.toArray(new String[0]);
for (String str:arr)
System.out.println("str:"+str); // 输出大小
System.out.println("size:"+llist.size());
// 清空LinkedList
llist.clear();
// 判断LinkedList是否为空
System.out.println("isEmpty():"+llist.isEmpty()+"\n"); } /**
* 将LinkedList当作 LIFO(后进先出)的堆栈
*/
private static void useLinkedListAsLIFO() {
System.out.println("\nuseLinkedListAsLIFO");
// 新建一个LinkedList
LinkedList stack = new LinkedList(); // 将1,2,3,4添加到堆栈中
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
// 打印“栈”
System.out.println("stack:"+stack); // 删除“栈顶元素”
System.out.println("stack.pop():"+stack.pop()); // 取出“栈顶元素”
System.out.println("stack.peek():"+stack.peek()); // 打印“栈”
System.out.println("stack:"+stack);
} /**
* 将LinkedList当作 FIFO(先进先出)的队列
*/
private static void useLinkedListAsFIFO() {
System.out.println("\nuseLinkedListAsFIFO");
// 新建一个LinkedList
LinkedList queue = new LinkedList(); // 将10,20,30,40添加到队列。每次都是插入到末尾
queue.add("10");
queue.add("20");
queue.add("30");
queue.add("40");
// 打印“队列”
System.out.println("queue:"+queue); // 删除(队列的第一个元素)
System.out.println("queue.remove():"+queue.remove()); // 读取(队列的第一个元素)
System.out.println("queue.element():"+queue.element()); // 打印“队列”
System.out.println("queue:"+queue);
}
}