基于JDK 1.8.0。
简介：
LinkedList 底层是通过双向链表来实现的。
特点：
- 底层实现：双向链表
- 线程安全：线程不安全。
- 扩容：没有限制大小，随时增加元素，不需要扩容。
- 是否可以存放null：可以存放null
- 是否有序：
- 效率：因为是链表的实现，添加和删除元素比较快，时间复杂度都是O(1)。查找元素比较慢，时间复杂度是O(n)
- 是否可以重复：可以放入重复的元素。
源码分析：
LinkedList有3个最基础的属性： int size ， Node<E> first ， Node<E> last。 first 存放第一个元素。last存放最后一个元素。size存的是元素的个数。
Node是LinkedList的静态内部类。用于存放LinkedList的元素。Node类有3个属性item，next，prev。 item用于存放元素，next存放当前元素的下一个结点，prev存放当前元素的上一个结点。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
构造函数：
LinkedList有2个构造函数
- 默认的构造函数，构造出一个空的链表。
/**
* Constructs an empty list.
*/
public LinkedList() {
}
2.用一个集合作为构造函数的参数，构造出链表后，将集合添加入链表。
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
在分析添加方法之前，有2个方法需要了解和分析的。一个是linkFirst()，另一个是linkLast()。
linkFirst方法是在当前链表的头添加一个结点。
/**
* Links e as first element.
*/
private void linkFirst(E e) {
//声明一个不可变的结点，保存第一个结点。
final Node<E> f = first;
//声明 一个新的结点，新结点没有前结点，数据域保存当前元素，下一个结点指向链表的第一个结点。
final Node<E> newNode = new Node<>(null, e, f);
//链表的第一个结点指向新结点。
first = newNode;
//如果链表之前的第一个结点为空，则表明之前链表是空链表。
if (f == null)
last = newNode;//将最后一个结点的也指向新结点。
else
//否则，之前链表不为空。则设置之前的第一个结点的前结点为新结点，因为新结点是第一个结点。
f.prev = newNode;
//链表长度加1
size++;
//修改次数加1
modCount++;
}
linkFirst方法是在当前链表的尾添加一个结点。
/**
* Links e as last element.
*/
void linkLast(E e) {
//声明一个结点保存尾结点。
final Node<E> l = last;
//创建一个新结点，前驱结点为当前链表的尾结点，数据域为传入的元素，后继结点为空
final Node<E> newNode = new Node<>(l, e, null);
//将新结点设置为当前链表的尾结点
last = newNode;
//如果链表之前的尾结点为空，则说明链表是空链表，则将新结点也设置为头结点。因为当前链表只有1个结点，则头结点和尾结点都是同一个结点。
if (l == null)
first = newNode;
else
l.next = newNode;//链表不为空的话，则将新结点设置为之前尾结点的后继结点。
//链表长度加1
size++;
//修改次数加1
modCount++;
}
添加元素
添加元素方法有两种，一种是添加单个元素，一种是添加一个集合。添加单个元素使用add()方法，add()方法有1个重载。 添加集合使用addAll()方法，addAll()方法也有1个重载。
- 添加一个元素，不指定位置。直接将元素添加到链表末端。因为是链表结构，所以不需要移动任何元素，添加的效率非常高。时间复杂度是O(1)。
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
- 将元素添加到指定的位置。
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//检查添加的位置是否合法。index >= 0 && index <= size
checkPositionIndex(index);
//如果指定的位置是最后一位，则直接在链表尾部添加一个结点。
if (index == size)
linkLast(element);
else
//否则，则在指定的位置添加一个结点。
linkBefore(element, node(index));
}
3.在链表首部添加一个元素。
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
- 在链表尾部添加一个元素。
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
}
- 在指定的位置添加一个集合。
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
//检查添加的位置是否在范围之内。
checkPositionIndex(index);
//将需要添加的数组，转换成对象数组。
Object[] a = c.toArray();
//获取对象数组的长度。
int numNew = a.length;
//如果对象数组长度为0，则不用添加，直接返回false。
if (numNew == 0)
return false;
//声明两个新结点，一个前驱结点，一个后继结点。
Node<E> pred, succ;
if (index == size) {
//如果指定的位置为链表尾端。后继结点为空，前驱结点为链表的尾结点。
succ = null;
pred = last;
} else {
//否则，后继结点为指定位置的结点，前驱结点为指定位置结点的前驱结点。
succ = node(index);
pred = succ.prev;
}
//循环将对象数组的元素构建成结点。并设置前驱结点。
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//这里想不明白为什么后继结点为空，后面也没有进行设置了。
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//如果后继结点为空，则尾结点=前驱结点。
if (succ == null) {
last = pred;
} else {
//否则，前驱结点的后继结点为后继结点
pred.next = succ;
//后继结点的前驱结点为前驱结点
succ.prev = pred;
}
//链表的长度增加
size += numNew;
modCount++;//修改次数加1
return true;
}
- 添加一个集合到链表的尾端。其实就是调用添加集合到指定位置的方法，指定的位置为链表的尾端。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
在分析删除方法之前，有3个方法需要分析。其实这3个方法是删除元素方法的关键。
unlinkFirst(), unlinkLast(), unlink()。
unlinkFirst是删除链表首结点的方法。
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//获取结点的数据域
final E element = f.item;
//获取结点的后继结点
final Node<E> next = f.next;
//设置结点的数据域和后继结点为空，帮助垃圾回收。
f.item = null;
f.next = null; // help GC
//设置刚才获取的后继结点为链表的首结点。
first = next;
if (next == null)
last = null;//如果刚才获取的后继结点为空，则说明链表只有1个结点，并且删除了这个结点。所以链表的首结点和尾结点都为null。
else
next.prev = null;//否则，设置后继结点的前驱结点为空，因为这个结点为首结点了。
//链表长度减1
size--;
modCount++;//修改次数加1
return element;
}
unlinkLast方法是删除链表的最后一个元素。
/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//获取结点的数据域
final E element = l.item;
//获取结点的前驱结点
final Node<E> prev = l.prev;
//将数据域和前驱结点都设置为null，方便垃圾回收。
l.item = null;
l.prev = null; // help GC
//将链表的尾结点设置为perv。
last = prev;
if (prev == null)
first = null; //如果perv为空的话，说明链表只有1个结点，并且要删除，所以首结点也为空。
else
prev.next = null;//否则，设置prev的后继结点为空，因为perv为尾结点了。
//链表长度减1
size--;
//修改次数加1
modCount++;
return element;
}
unlink方法为删除一个结点，这个结点不是首结点也不是尾结点。
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
//获取目标结点的数据域
final E element = x.item;
//获取目标结点的后继结点
final Node<E> next = x.next;
//获取目标结点的前驱结点
final Node<E> prev = x.prev;
if (prev == null) {
//如果目标结点没有前驱结点的话，则说明目标结点是首结点。所以直接将链表的首结点设置为后继结点。
first = next;
} else {
//否则，设置前驱节点的后继结点为后继结点。并且设置目标结点的前驱结点为空
prev.next = next;
x.prev = null;
}
if (next == null) {
///如果目标结点没有后继结点的话，则说明目标结点是尾结点。所以直接将链表的尾结点设置为前驱结点。
last = prev;
} else {
//否则，设置后继结点的前驱结点为前驱结点。并且设置目标结点的后继结点为空
next.prev = prev;
x.next = null;
}
//设置目标结点的数据域为空。
x.item = null;
//到此目标结点的已经没有前驱和后继结点，数据域也设置为空。结点已经和链表断开连接。
size--;//链表大小减1
modCount++;//修改次数加1
return element;
}
删除元素
删除元素有7个公开的方法。删除元素使用remove()， 实质就是删除链表的首结点。有2个重载。分别是remove(int index)， 指定删除结点的索引，进行删除。 remove(Object o)删除传入的元素。删除首结点的的方法removeFirst()。 删除第一个匹配的结点removeFirstOccurrence(Object o)。删除尾结点removeLast()。 从尾部开始查找，删除第一个匹配的结点removeLastOccurrence(Object o)。
- 先看removeFirst()， 因为其他方法是基于这个方法的。
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
//获取首结点。如果首结点不为空，则删除首结点。
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
2.remove(Object o)。根据传入的对象删除结点。
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
//这里要分开null和非null来写循环，是因为null需要用==判断。而对象则需要调用equals方法判断。
if (o == null) {
//如果要删除的对象为null， 则循环找到数据域为null 的结点。然后删除该结点。
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//循环找到数据域和传入对象相等的结点。 然后删除结点。
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
3.根据索引删除一个元素。方法比较简单，就判断一下传入的索引是否在范围内，不在就抛出异常， 如果在范围内， 就调用删除结点方法，将节点删除。
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
4.根据元素对象删除元素。
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
//如果传过来的对象是null。
if (o == null) {
//循环当前的数组，找到等于null的元素，并删除。
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//如果对象不是null。循环当前数组，调用equals方法找到元素，并删除。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
//如果找到元素并删除，就会在之前返回true。如果都没有找到的话。则没有对应的元素，返回false。
return false;
}
5.remove方法，这个方法比较简单。就是直接调用removeFirst方法删除首结点。
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E remove() {
return removeFirst();
}
6.removeLast方法， 删除尾结点。这个方法也简单，就获取尾结点，判断如果尾结点不为空，就删除尾结点。
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
- removeLastOccurrence方法， 根据传入的元素，从链表尾部开始查找，找到第一个匹配的结点， 就删除。
/**
* Removes the last occurrence of the specified element in this
* list (when traversing the list from head to tail). If the list
* does not contain the element, it is unchanged.
*
* @param o element to be removed from this list, if present
* @return {@code true} if the list contained the specified element
* @since 1.6
*/
public boolean removeLastOccurrence(Object o) {
if (o == null) {
//如果参数是null。 则从尾部开始循环查找null。找到后将该结点移出链表。
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//如果参数不是null。 则从为不开始循环查找该元素。找到后，将该元素对应的结点移出链表。
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
- clear() 。 清空方法。
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
//循环将节点的数据域，前驱，后继结点都设置为空。方便垃圾回收。
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
//设置前驱和后继结点为空。
first = last = null;
size = 0;//设置链表长度为0
//修改次数加1
modCount++;
}
获取元素
LinkedArray的优势在于添加和删除元素，只需要改动结点的前驱、后继结点和数据域赋值就可以了。 由于底层是双向链表实现。所以获取结点的效率并不高，时间复杂度是O(n)。
获取方法是基于node这个方法的。
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//这里是为了提升获取的效率，就判断如果需要获取的元素的索引靠近开头，就从链表首部开始查找，如果靠近尾部，则从尾部开始查找。
//但是这里我想不明白，为什么要用移位运算，size是int类型。使用移位运算的话有可能会导致溢出。感觉直接size/2 更加准确。
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
- get方法。需要传一个索引，来表明需要获取的是哪个元素。方法实现比较简单，首先检查索引是否越界。越界的话就抛出异常， 没有的话就直接调用node方法获取结点，然后返回结点的数据域。
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
- 获取链表的首结点。实现很简单，就判断首结点是否为空，为空就抛出异常，不为空就返回首结点的数据域。
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
- 获取链表的尾结点。实现很简单，就判断尾结点是否为空，为空就抛出异常，不为空就返回尾结点的数据域。
/**
* Returns the last element in this list.
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
总结
LinkedList 没有实现同步，所以不是线程安全的。
网友评论