LinkedList和ArrayList与Vector同样实现了List接口,但它执行某些操作如插入和删除元素操作比ArrayList与Vector更高效,而随机访问操作效率低。除此之外,LinkedList还添加了可以使其用作栈、队列或双端队列的方法。

定义

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

LinkedList的特性:

  • LinkedList:说明它支持泛型。
  • extends AbstractSequentialList: AbstractSequentialList 继承自AbstractList,但AbstractSequentialList 只支持按次序访问,而不像 AbstractList 那样支持随机访问。这是LinkedList随机访问效率低的原因之一。
  • implements List:说明它支持集合的一般操作。
  • implements Deque:Deque,Double ended queue,双端队列。LinkedList可用作队列或双端队列就是因为实现了它。
  • implements Cloneable:表明其可以调用clone()方法来返回实例的field-for-field拷贝。
  • implements java.io.Serializable:表明该类是可以序列化的。

与ArrayList对比发现,LinkedList并没有实现RandomAccess,而实现RandomAccess表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。这是LinkedList随机访问效率低的原因之一。

构造方法

LinkedList提供了两种构造方法。

  1. LinkedList():构造空LinkedList。构造一个空链表。
  2. LinkedList(Collection<? extends E> c):根据指定集合c构造linkedList。先构造一个空linkedlist,在把指定集合c中的所有元素都添加到linkedList中。

###核心方法
linkFirst(E e)
方法在表头添加指定元素e

linkLast(E e)
方法在表尾插入指定元素e

linkBefore(E e, Node succ)
方法在指定节点succ之前插入指定元素e

unlinkFirst(Node f)
方法删除并返回头结点f

unlinkLast(Node l)
方法删除并返回尾结点f

unlink(Node x)
方法删除指定节点,返回指定元素的值x

getFirst()
返回链表中的头节点的值

getLast()
返回链表中的尾节点的值

removeFirst
删除并返回表头元素.

removeLast
删除并返回表尾元素.

addFirst( E e)
在表头插入指定元素.

addLast( E e)
在表尾插入指定元素.

contains( Object o)
判断链表是否包含指定对象o

size()
返回链表元素个数

add( E e)
在表尾插入指定元素.

remove(Object o)
正向遍历链表,删除出现的第一个值为指定对象的节点

addAll( Collection<? extends E> c)
插入指定集合到链尾

addAll( int index, Collection<? extends E> c)
插入指定集合到链尾的指定位置

clear()
删除链表中的所有元素

get( int index)
返回指定索引处的元素

set( int index, E element)
替换指定索引处的元素为指定元素element

add( int index, E element)
插入指定元素到指定索引处

remove( int index)
删除指定索引处的元素

isElementIndex( int index)
返回索引是否越界

isPositionIndex(int index)
返回插入操作时给定的索引是否合法

outOfBoundsMsg( int index)
索引越界时打印的信息

checkElementIndex( int index)
检查索引是否越界

checkPositionIndex( int index)
检查插入操作时给定的索引是否合法

node( int index)
返回在指定索引处的非空元素

indexOf( Object o)
正向遍历链表,返回指定元素第一次出现时的索引。如果元素没有出现,返回-1.

lastIndexOf( Object o)
逆向遍历链表,返回指定元素第一次出现时的索引。如果元素没有出现,返回-1.

peek()
返回头节点的元素,如果链表为空则返回null

element()
获取表头节点的值,头节点为空抛出异常

poll()
返回并删除头节点,如果链表为空则返回null

remove()
删除并返回头节点,如果链表为空,抛出异常

offer(E e)
添加元素到队列尾部

offerFirst( E e)
插入指定元素到双向队列头部.

offerLast( E e)
插入指定元素到双向队列尾部.

peekFirst()、
返回双向队列的头元素,如果头节点为空则返回空

peekLast()
返回双向队列的尾元素,如果尾节点为空则返回空

pollFirst()
删除并返回双向队列的第一个元素,如果头节点为空,则返回null.

pollLast()
删除并返回双向队列的最后个元素,如果尾节点为空,则返回null.

push( E e)、
插入指定元素到栈头

pop()
删除并返回栈头元素

removeFirstOccurrence( Object o)
正向遍历栈,删除指定对象第一次出现时,索引对应的元素

源码分析

  1. 概览
    基于双向链表实现,使用 Node 存储链表节点信息。
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每个链表存储了 first 和 last 指针:

transient Node<E> first;
transient Node<E> last;
  1. 与ArrayList的比较
    ArrayList 基于动态数组实现,LinkedList 基于双向链表实现。ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别:
  • 数组支持随机访问,但插入删除的代价很高,需要移动大量元素;
  • 链表不支持随机访问,但插入删除只需要改变指针。