上一篇文章
LinkedList是基于链表实现的，物理存储空间不连续，插入删除简单，查找修改都需要进行遍历。
LinkedList实现List接口，能对它进行队列操作，即可以根据索引来随机访问集合中的元素。同时它还实现Deque接口，即能将LinkedList当作双端队列使用。自然也可以被当作"栈来使用"。
Node节点
双向链表
LinkedList的节点Node包含item 、指向上一个节点的prev 、指向下一个节点的next。
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构造函数
空参构造函数，或者指定集合
不像ArrayList, 需要指定capacity，链表存储空间不连续，动态分配内存更*。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0; //包含的节点个数
transient Node<E> first; //双向链表的头结点
transient Node<E> last; //双向链表的尾节点
//空的构造函数，在使用的时候才创建节点
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //判断index是否处于0-size之间
Object[] a = c.toArray();
int numNew = a.length;
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; //size增加
modCount++;
return true;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//数据是否越界判断
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
复制代码add(Object) 增
add(E e) 在链表的尾部添加对象，创建一个新的节点（prev指向以前的last尾指针），并将以前的last尾指针的next，指向这个新的节点。如果以前的last尾指针为null, 则
public boolean add(E e) {
linkLast(e); //默认在链表的尾部添加对象
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null); //创建一个新的节点，prev指向以前的last尾指针
last = newNode; //新节点赋给last尾指针
if (l == null) //如果以前的last尾指针==null,则以前就是个空链表，需要给first头指针赋值
first = newNode;
else // 否则的话以前的尾指针的next指向新节点
l.next = newNode;
size++;
modCount++;
}
复制代码add(index, element) 增
如果index == size,则直接在链表的尾部添加对象
在指定的index插入对象，并更新相应的节点prev和next引用指向
public void add(int index, E element) {
checkPositionIndex(index);
//如果index == size,则直接在链表的尾部添加对象
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//返回指定index的节点，这里对链表进行了折半查找，提升了部分效率
Node<E> node(int index) {
if (index < (size >> 1)) { //如果index在前一半，从0-index进行遍历定位
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last; //如果index在后一半，从size-1到index 倒序遍历定位
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//在指定的index插入对象，
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
//创建新节点newNode，newNode.prev指向succ.prev, newNode.next指向succ
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode; //succ.prev指向newNode
if (pred == null) // 如果pred==null,succ则是以前的头结点，需要更新first;
first = newNode;
else //否则pred.next指向newNode
pred.next = newNode;
size++;
modCount++;
}
复制代码remove(index) 删
移除指定index的节点，更新前后节点prev和next。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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) { //如果x是头结点,则直接更新头结点first
first = next;
} else {
prev.next = next; //否则x的上一个节点的next直接指向x.next
x.prev = null;// 释放空间
}
if (next == null) { //如果x是尾节点,则直接更新尾节点last
last = prev;
} else {
next.prev = prev; //否则x的下一个节点的prev直接指向x.prev
x.next = null;// 释放空间
}
x.item = null; // 释放空间
size--;
modCount++;
return element;
}
复制代码removeFirst() & removeLast() 删
移除头结点和尾节点，并释放相应的头结点和尾节点的空间
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
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;
else
next.prev = null;
size--;
modCount++;
return element;
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
复制代码set(index, element) 改
node(index)通过index定位到节点x，将节点x.item改为element，并返回oldValue
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
复制代码get(index) 查
node(index)通过index定位到节点x，并返回。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
复制代码contains(object)
是否包含某个对象，通过equals匹配item
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
复制代码size()
返回这个list的对象个数
/**
// Returns the number of elements in this list
public int size() {
return size;
}
复制代码总结
LinkedList是基于双向链表实现的，物理存储空间不连续，插入删除简单，只需要修改上下节点的prev/next指向，查找修改需要先进行遍历定位，然后修改返回。