JDK底层实现源码分析系列(三) LinkedList源码分析
“合抱之木 生于毫末 九层之台 起于累土 千里之行 始于足下”
前言
JDK 版本1.7
Collection 大家族
LinkedList 继承树
LinkedList从数据结构层面上说算是一个双向链表 继承于AbstractSequentialList实现了List、Deque、Cloneable、Serializable
有三个重要的成员变量first(链表的头节点)、last(链表的尾节点)、size(链表的长度)
Node为存储数据的类 共有3个变量item(元素)、next(此元素的下一个节点)、prev(此元素的上一个节点)
分析
链表和数组
数组：
数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。链表：
链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。区别：
数组静态分配内存，链表动态分配内存；
数组在内存中连续，链表不连续；
数组元素在栈区，链表元素在堆区；
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
new
LinkedList一共有俩个构造方法，一个是无参的，新new一个size为空的LinkedList，另一个是传入一个Collection类型的集合使用addAll(size,c)把集合中的全部数据加入到新建的LinkedList
/**
* 在链表指定位置插入集合中所有数据
*
* @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) {
// index >= 0 && index <= size;
// false throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0) // 传入集合为空
return false;
Node<E> pred, succ;
// pred为被插入节点前一个节点 succ为index节点 index<size时用于移动index节点succ.prev = pred;
if (index == size) { // 即插入链表的最后
succ = null;
pred = last; // 获取最后一个节点
} else { // 插入链表中间
succ = node(index);
pred = succ.prev; // 获取index前一个节点
}
for (Object o : a) {
E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
// 新new节点 pred指向 (index == size)(pred->last)
// 新new节点 pred指向 (index < size)(pred->succ.prev)
if (pred == null) // 链表为空
first = newNode; // 新节点为头节点
else
pred.next = newNode; // 上次循环的节点的next设置为本次循环节点
pred = newNode; // 设置下次循环的pred节点为本次循环增加的节点
}
if (succ == null) { // index == size
last = pred; // 设置last节点为循环的最后一个节点
} else {
pred.next = succ; // 设置循环的最后一个节点的next为index节点
succ.prev = pred; // 设置设置index的prev为循环的最后一个节点
}
size += numNew;
modCount++; // fail-fast
return true;
}
插入数据
LinkedList插入数据的方法有
- public boolean add(E e)
- public void add(int index, E element)
- public boolean addAll(Collection<? extends E> c)
- public boolean addAll(int index, Collection<? extends E> c)
- public void addFirst(E e)
- public void addLast(E e)
- private void linkFirst(E e)
- void linkLast(E e)
- void linkBefore(E e, Node
succ) - public boolean offerFirst(E e)
- public boolean offerLast(E e)
- public void push(E e)
- public E set(int index, E element)
- 等
由于添加方法太多 本篇只会讲add(int index, E element) 其他插入方法都类似
/**
* 在index之前插入element元素
*/
public void add(int index, E element) {
checkPositionIndex(index);
// 判断索引 index >= 0 && index <= size
if (index == size) // 即链表尾部增加
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 在index之前插入element元素 (建议画图看)
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev; // 获取index节点的前一个节点
final Node<E> newNode = new Node<>(pred, e, succ); // 新建节点 赋值 把index的prev赋给新建节点prev
succ.prev = newNode; // 设置index节点的prev为新节点
if (pred == null) // 即链表为空
first = newNode; // 设置新节点为头节点
else
pred.next = newNode; // 设置index节点的前一个节点的下个节点为newNode
size++;
modCount++;
}
删除数据
LinkedList删除数据的方法有
- public void clear()
- public E poll()
- public E remove()
- public E remove(int index)
- public boolean remove(Object o)
- public E removeFirst()
- public boolean removeFirstOccurrence(Object o)
- public boolean removeLastOccurrence(Object o)
- public E removeLast()
- public E pollFirst()
- public E pollLast()
- public E pop()
- private E unlinkFirst(Node
f) - 等
由于方法太多 而且都类似 本篇只会选择unlinkFirst()方法分析
/**
* 移除first节点
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item; // 获取first的元素
final Node<E> next = f.next; // 获取first的下一个元素
f.item = null; // 删除first的元素
f.next = null; // 删除first指向的元素 让GC回收
first = next; // 设置first为删除节点的下一个节点
if (next == null) // 下个节点为空
last = null; // 说明只有一个first节点不为null
else
next.prev = null; // 设置first的下个节点为null
size--;
modCount++;
return element; // 返回删除数据
}
修改数据
/**
* 替换指定位置的元素
*
*/
public E set(int index, E element) {
checkElementIndex(index); // 检查index是否越界
Node<E> x = node(index); // 获得指定index元素
E oldVal = x.item; // 活动被替换的元素
x.item = element; // 修改元素
return oldVal; // 返回被修改的元素
}
查询数据
LinkedList查询数据的方法有
- public E getFirst():获取First节点元素
- public E getLast():获取Last节点元素
- Node
node(int index):获取指定index节点元素 - public E peek():获取First节点元素
- public E peekFirst():获取First节点元素
- public E peekLast():获取Last节点元素
- public E poll():删除First节点并返回删除元素
- public E pollFirst():删除First节点并返回删除元素
- public E pollLast():删除Last节点并返回删除元素
- public E pop():删除First节点并返回删除元素
- 等
由于方法太多 而且都类似 本篇只会选择get()方法分析
/**
* 获取指定index元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 返回指定index的节点元素 会更具index的值判断是从前找还是从后找
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // index < size / 2
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // index > size / 2
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
总结
LinkedList本质上就是一个双向链表，不会像ArrayList那样，空间不足时去扩容(array copy是一件效率非常低的操作)这样做的好处就是处理大量数据时，存储数据的时间比ArrayList要低很多。
另外LinkedList实现了Deque接口，可以通过内部,实现FIFO(先进先出)的队列或者LIFO(后进先出)的栈
著作权声明
本文首次发布于 Binux Blog，转载请保留以上链接