Java Improvement Chapter (22)-----LinkedList
- 黄舟Original
- 2017-02-10 14:18:471314browse
1. Overview
LinkedList implements the List interface just like ArrayList, except that ArrayList is an implementation of a variable-sized array of the List interface, and LinkedList is an implementation of a linked list of the List interface. Based on the linked list implementation, LinkedList is better than ArrayList when inserting and deleting, while random access is inferior to ArrayList.
LinkedList implements all optional list operations and allows all elements including null.
In addition to implementing the List interface, the LinkedList class also provides a unified naming method for get, remove, and insert elements at the beginning and end of the list. These operations allow linked lists to be used as stacks, queues, or deques.
This class implements the Deque interface, providing first-in-first-out queue operations for add and poll, as well as other stack and double-ended queue operations.
All operations are performed according to the needs of double-linked lists. Indexing in a list will traverse the list from the beginning or end (from the end closer to the specified index).
At the same time, like ArrayList, this implementation is not synchronous.
(The above is taken from JDK 6.0 API).
# 2. Source code analysis
## Let’s first look at the definition of LinkedList first:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
private transient Entry<E> header = new Entry<E>(null, null, null); private transient int size = 0;
##The size represents the size of the LinkedList, and the header represents The header of the linked list, Entry is the node object.
private static class Entry<E> {
E element; //元素节点
Entry<E> next; //下一个元素
Entry<E> previous; //上一个元素
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
## The above is the source code of the Entry object, and the Entry is Inner class of LinkedList, which defines the stored elements. The previous element and the following element of this element are the typical doubly linked list definition methods.
2.3. Construction methods
LinkedList has improved two construction methods: LinkedLis() and LinkedList(Collection8ce1b3ab55adadeadb2f081cb7e43c40 c).
/**
* 构造一个空列表。
*/
public LinkedList() {
header.next = header.previous = header;
}
/**
* 构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
## LinkedList() constructs an empty list. There is no element in it, it just points the previous element and the next element of the header node to itself.
## LinkedList(Collection2d4902c92e1e7bfd574f59708c57776a c): Constructs a list containing the elements in the specified collection, which are returned by the iterator of its collection Arrange in order. The constructor first calls LinkedList() to construct an empty list, and then calls the addAll() method to add all elements in the Collection to the list. The following is the source code of addAll():
/**
* 添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 将指定 collection 中的所有元素从指定位置开始插入此列表。其中index表示在其中插入指定collection中第一个元素的索引
*/
public boolean addAll(int index, Collection<? extends E> c) {
//若插入的位置小于0或者大于链表长度，则抛出IndexOutOfBoundsException异常
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length; //插入元素的个数
//若插入的元素为空，则返回false
if (numNew == 0)
return false;
//modCount:在AbstractList中定义的，表示从结构上修改列表的次数
modCount++;
//获取插入位置的节点，若插入的位置在size处，则是头节点，否则获取index位置处的节点
Entry<E> successor = (index == size ? header : entry(index));
//插入位置的前一个节点，在插入过程中需要修改该节点的next引用：指向插入的节点元素
Entry<E> predecessor = successor.previous;
//执行插入动作
for (int i = 0; i < numNew; i++) {
//构造一个节点e，这里已经执行了插入节点动作同时修改了相邻节点的指向引用
//
Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);
//将插入位置前一个节点的下一个元素引用指向当前元素
predecessor.next = e;
//修改插入位置的前一个节点，这样做的目的是将插入位置右移一位，保证后续的元素是插在该元素的后面，确保这些元素的顺序
predecessor = e;
}
successor.previous = predecessor;
//修改容量大小
size += numNew;
return true;
}## The addAll() method involves two methods, one is entry(int index), which is a private method of LinkedList and is mainly used to find the node element at the index position.
/**
* 返回指定位置(若存在)的节点元素
*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
//头部节点
Entry<E> e = header;
//判断遍历的方向
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}从该方法有两个遍历方向中我们也可以看出LinkedList是双向链表，这也是在构造方法中为什么需要将header的前、后节点均指向自己。
如果对数据结构有点了解，对上面所涉及的内容应该问题，我们只需要清楚一点：LinkedList是双向链表，其余都迎刃而解。
由于篇幅有限，下面将就LinkedList中几个常用的方法进行源码分析。
2.4、增加方法
add(E e): 将指定元素添加到此列表的结尾。
public boolean add(E e) {
addBefore(e, header);
return true;
}该方法调用addBefore方法，然后直接返回true，对于addBefore()而已，它为LinkedList的私有方法。
private Entry<E> addBefore(E e, Entry<E> entry) {
//利用Entry构造函数构建一个新节点 newEntry，
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//修改newEntry的前后节点的引用，确保其链表的引用关系是正确的
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
//容量+1
size++;
//修改次数+1
modCount++;
return newEntry;
}在addBefore方法中无非就是做了这件事：构建一个新节点newEntry，然后修改其前后的引用。
LinkedList还提供了其他的增加方法：
add(int index, E element)：在此列表中指定的位置插入指定的元素。
addAll(Collection2d4902c92e1e7bfd574f59708c57776a c)：添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
addAll(int index, Collection2d4902c92e1e7bfd574f59708c57776a c)：将指定 collection 中的所有元素从指定位置开始插入此列表。
AddFirst(E e): 将指定元素插入此列表的开头。
addLast(E e): 将指定元素添加到此列表的结尾。
2.5、移除方法
remove(Object o)：从此列表中移除首次出现的指定元素（如果存在）。该方法的源代码如下：
public boolean remove(Object o) {
if (o==null) {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}该方法首先会判断移除的元素是否为null，然后迭代这个链表找到该元素节点，最后调用remove(Entry1a4db2c2c2313771e5742b6debf617a1 e)，remove(Entry1a4db2c2c2313771e5742b6debf617a1 e)为私有方法，是LinkedList中所有移除方法的基础方法，如下：
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
//保留被移除的元素：要返回
E result = e.element;
//将该节点的前一节点的next指向该节点后节点
e.previous.next = e.next;
//将该节点的后一节点的previous指向该节点的前节点
//这两步就可以将该节点从链表从除去：在该链表中是无法遍历到该节点的
e.next.previous = e.previous;
//将该节点归空
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}其他的移除方法：
clear()： 从此列表中移除所有元素。
remove()：获取并移除此列表的头（第一个元素）。
remove(int index)：移除此列表中指定位置处的元素。
remove(Objec o)：从此列表中移除首次出现的指定元素（如果存在）。
removeFirst()：移除并返回此列表的第一个元素。
removeFirstOccurrence(Object o)：从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
removeLast(): Remove and return the last element of this list.
removeLastOccurrence(Object o): Remove the last occurrence of the specified element from this list (when traversing the list from head to tail).
2.5. Search method
There is nothing to introduce about the source code of the search method, it is nothing more than iteration. Compare and then return the current value.
get(int index): Returns the element at the specified position in this list.
getFirst(): Returns the first element of this list.
getLast(): Returns the last element of this list.
indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if the element is not included in this list.
## lastIndexOf(Object o): Returns the index of the last specified element that appears in this list, or -1 if this element is not included in this list.
##The above is Java Improvement Chapter (22) ----- Contents of LinkedList, please pay attention to the PHP Chinese website (www.php.cn) for more related content!