LinkedList简介

LinkedList简介

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

LinkedList 实现 Queue 接口，能对它进行队列操作。

1
2
3

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.poll();

LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。

Deque<Integer> deque = new LinkedList<>();

Deque接口的方法：
// 从头增
addFirst(element);
offerFirst(element):如果增加成功，返回true
push(element);

// 从尾增
add(element);
addLast(element);
offer(element) ;  如果增加成功，返回true
offerLast(element); 如果增加成功，返回true

// 迭代
iterator();
descendingIterator();: 逆序迭代

// 从头删
pop(element) ; 返回删除的元素
removeFirst();

// 从尾删
removeLast();

// 需要注意的是
Collection-->Queue-->Deque--实现-->LinkedList(实现类)
  
- Deque接口继承了Queue接口,而Queue接口继承了Collection接口,
- LinkedList实现了Deque接口

// 一个值得注意的现象：

LinkedList<Integer> test = new LinkedList<>();
test.addFirst(1);

List<Integer> ret = test;
ret.addFirst(1);// 非法操作！

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 方法即可。

#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是双向链表中节点的个数。

参考文献

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

甲乙小朋友的房子

Java-LinkedList

LinkedList简介

参考文献