本篇内容主要讲解“怎么理解LinkedList源码”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“怎么理解LinkedList源码”吧!
LinkedList是也是非常常见的集合类,LinkedList是基于链表实现的集合。它拥有List集合的特点:
存取有序
带索引
允许重复元素
还拥有Deque集合的特点:
先入先出
双端操作
它本身的特点是:
对元素进行插入或者删除,只需要更改一些数据,不需要元素进行移动。
依然是通过源码来看看LinkedList如何实现自己的特性的。
Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations,and permits all elements (including {@code null}).
对于List接口和Deque接口的双链表实现。实现了所有List接口的操作并且能存储所有的元素。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可以看到LinkedList实现了一个Deque接口,其实是说,LinkedList除了有List的特性,还有Deque的特性,那么Deque是什么呢?
public interface Deque<E> extends Queue<E>
public interface Queue<E> extends Collection<E>
原来是继承了Collection集合的另一个接口。
Queue就是我们常说的队列,它的特性是FIFO( First In First Out )先进先出,它的操作只有两个:
把元素存进队列尾部
从头部取出元素
就像排队办事一样的。
而它的子接口Deque除了这两操作以外,还能比Queue队列有更多的功能
既可以添加元素到队尾,也可以添加元素到队头
既可以从队尾取元素,也可以从队头取元素
如此看来就像两边都可以当队头和队尾一样,所以Deque又叫双端队列 。
理所应当的,LinkedLisk也实现了这些特性,并且有Doubly-linked(双链表的特性)。
那么什么又是链表呢?
其实链表是一种线性的存储结构,意思是将要存储的数据存在一个存储单元里面,这个存储单元里面除了存放有待存储的数据以外,还存储有其下一个存储单元的地址。
双链表顾名思义,存储单元除了存储其下一个存储单元的地址,还存储了上一个存储单元的地址。每次查找数据的时候,就通过存储单元里存储的地址信息进行查找。
成员变量:
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
只有三个,size代表LinkedList存储的元素个数。那这个Node是什么?
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内部的数据结构Node,作为LinkedList的基本存储单元,也最能体现LinkedList双链表的特性。
像这样的。
其中prev存储上一个节点的引用(地址),next存储下一个单元的引用,item就是具体要存的数据。
First和Last用来标明队头跟队尾。
添加数据:
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);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
默认是调用添加到尾部的方法。前面说过,LinkedList的基本存储单元是Node,所以添加进来的数据会被封装进Node的item属性里,而且这个新Node的prev会指向前一个Node,前一个Node的next会指向这个新Node。
类似这样,但是注意画线只是一种形象的表达方法,就如上面所说,在Node里的prev属性和next属性是用来存储引用的,通过这个引用就能找到前一个Node或者后一个Node。
public void addFirst(E e) {
linkFirst(e);
}
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;
size++;
modCount++;
}
public void addLast(E e) {
linkLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
其实LinkedList很多不同名的方法,但是实现方式都是类似的,这是因为我们有可能用LinkedList表达不同的数据结构,虽然都是添加元素到队首/队尾,但是清晰的描述对代码的可读性是有好处的。像如果要用LinkedList表示Stack(栈)数据结构时候用push()/pop()/peek()等方法来描述,用LinkedList表示Queue(队列)数据结构时候用add()/offer()等方法来描述。(当然,更好的实现方式是多态。)
删除数据:
//删除头Node
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(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;
else
next.prev = null;
size--;
modCount++;
return element;
}
//删除尾Node
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//删除操作
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//拿到最后一个元素存放的数据
final E element = l.item;
//拿到最后一个元素的prev前元素的引用
final Node<E> prev = l.prev;
//将它们赋值为null
l.item = null;
l.prev = null; // help GC
//现在前元素是list(最后一个Node)
last = prev;
//如果前元素已经是null说明没有Node了
if (prev == null)
first = null;
else
//说明前面还有元素,那么前元素的next就存放null
prev.next = null;
size--;
modCount++;
return element;
}
先看看简单的删除, 这里是指定删除最前跟最后的元素,所以只要判断删除后Node的prev或者next是否还有值,有就说明还有Node,没有就说明LinkedList已经为空了。
怎样才算删除了头/尾Node,只要它的next/prev为空,说明没有引用指向它了,那么我们就认为它从LinkedList里删除了,因为我们无法通过存储单元的引用找到这个Node,所以GC很快也会来回收掉这个Node。
这只是删除头尾Node,那要是删除中间的Node呢?这要跟下面的查找和插入一起看。
查找元素:
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//如果索引小于元素个数的一半,就从前遍历
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;
}
}
数组默认是有下标的,可以一次就取出所在位置的元素,但是LinkedList底层可没有维护这么一个数组,那怎么知道第几个元素是什么呢?
笨方法,我有size个元素,我不知道你指定的index在哪,那我一个一个找过去不就完事了?毕竟我的存储单元Node记得它旁边的单元的引用(地址)。
如果你的index比我size的一半还大,那我就从后面找,因为我是双端队列,有Last的引用(地址),所以可以调换两头。
所以,在LinkedList里面找元素可不容易,最多可能要找size/2次才能找到。
只要找到了想要的位置,那么插入和删除指定的这个Node就很简单了。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
//拿到所要删除的Node的item
final E element = x.item;
//后一个Node
final Node<E> next = x.next;
//前一个Node
final Node<E> prev = x.prev;
//如果前一个Node为null(说明是第一个Node)
if (prev == null) {
//那么后一个Node作为first
first = next;
} else {//否则说明前面有Node
//那前一个Node的下一个Node引用变为后一个Node
prev.next = next;
//当前的前引用变成null
x.prev = null;
}
//如果后一个Node为null(说明是最后一个Node)
if (next == null) {
//那么前一个Node作为last
last = prev;
} else {//否则说明后面还有Node
//那后一个Node的下一个Node引用变为前一个Node
next.prev = prev;
//当前的后引用变为null
x.next = null;
}
//保存的元素也设为null
x.item = null;
//元素-1
size--;
//修改次数+1
modCount++;
return element;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//要插入位置的前一个Node
final Node<E> pred = succ.prev;
//新Node,前引用是前一个Node,后引用是当前位置的Node
final Node<E> newNode = new Node<>(pred, e, succ);
//后一个Node的前引用变为这个新Node
succ.prev = newNode;
//如果没有前一个Node
if (pred == null)
//说明添加的就是第一个Node了
first = newNode;
else//说明前面还有Node
//将前一个Node的后引用变为这个新的Node
pred.next = newNode;
//元素+1
size++;
modCount++;
}
只是改变了存储单元Node里的prev和next,我们就可以认为这个Node被插入/删除了。
代码的注释配合着下图看,就会方便理解很多,其中注意区分源代码中的命名,最好拿笔记一下容易区分一些。
如果是插入元素,倒着看就可以了。
关于遍历:
我们可以了解到,LinkedList最大的性能消耗就在node(index)这步,这会需要去查找大量的元素。但是只要找到了这个元素所在的Node,插入跟删除就非常的方便了。
所以对于get(index)这个方法,我们需要非常小心的去使用,如果只想看一看这个位置的元素,可以用这个方法,但是如果是遍历LinkedList,千万不可以这样写:
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i).equals(Obj);
}
这样对于每次循环,get总会从前或者从后走i次,不考虑get方法中>>1的优化的话,这是一种O(n^2)时间复杂度的做法,效率十分低下。
所以LinkedList提供了内部的Iterator迭代器供我们使用:
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
其实就是通过不断调用next()方法取得Node,然后再对Node做操作,这样时间复杂度就是O(n)了,不会有大量重复无用的遍历。
到此,相信大家对“怎么理解LinkedList源码”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4829153/blog/4731048