在日常开发中,最常用的List是ArrayList其次便是LinkedList了.上次我们已经研究过了ArrayList,
今天来深入学习下LinkedList...
LinkedList顾名思义本质上就是一个链表.它和ArrayList一样实现了List接口.
ArrayList是基于可变数组实现的,因此对于随机访问和修改ArrayList的效率会更高,而LinkedList更擅长于随机插入和删除,毕竟只需要移动"指针"即可.
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
LinkedList继承了AbstractSequentialList,同时又实现了List Deque Cloneable Serializable.
AbstractSequentialList 继承了 AbstractList是LinkedList的父类,是List的简单实现,提供了对连续访问的支持,对于随机访问数据,应优先使用AbstractList.
arraylist集合。为何又实现List的原因在此就不重复叙述了,如想了解可==点击此处(ArrayList)==.
Deque 继承自Queue, Queue是Java中所有队列实现的根接口.
public interface Queue<E> extends Collection<E> {
// 把元素插入到队列末端 插入成功返回true, 若无空间可插入,则抛异常 (不推荐使用)
boolean add(E e);
// 把元素插入到队列末端 插入成功返回true, 反之 false
boolean offer(E e);
// 从队首删除一个元素并返回该元素 若队列为空抛异常 (不推荐使用)
E remove();
// 从队首删除一个元素并返回该元素 若队列为空,返回null
E poll();
// 获取队首的元素(只是获取并不会删除) 若队列是空的会抛异常 (不推荐使用)
E element();
// 获取队首的元素(只是获取并不会删除) 若队列是空,返回null
E peek();
}
Deque是一个双端队列同时又提供了对栈的抽象,其支持在两端插入和移除元素.通常Deque的实现对容量是没有固定限制,但此接口即支持限容的双端队列,也支持无限容的双端队列.
public interface Deque<E> extends Queue<E> {
void addFirst(E e); // 队首插入元素,插入失败抛异常
void addLast(E e); // 队尾插入元素,插入失败抛异常
boolean offerFirst(E e); // 队首插入元素,插入失败返回false
boolean offerLast(E e); // 队尾插入元素,插入失败返回false
E removeFirst(); // 队首删除元素,删除失败抛异常
E removeLast(); // 队尾删除元素,删除失败抛异常
E pollFirst(); // 队首删除元素, 队列为空抛异常
E getFirst(); // 队首获取(不删除)元素,队列为空抛异常
E peekFirst(); // 队首获取(不删除)元素,队列为空返回null
...
}
它的api里提供了两种方式.一种在操作失败时抛出异常,另一种形式返回特殊值(null/false).插入操作的后一种形式是专为使用有容量限制的Deque实现设计的;在大多数实现中，插入操作不能失败.
Deque包含的栈相关api:
E peek(); // 查看栈顶元素
void push(E e); // 入栈
E pop(); // 弹栈
注意: Java堆栈Stack类已经过时,官方推荐使用Deque代替Stack使用.
/**
* arraylist linkedlist？A more complete and consistent set of LIFO stack operations is
* provided by the {@link Deque} interface and its implementations, which
* should be used in preference to this class. For example:
*
{@code
* Deque stack = new ArrayDeque();}
*/
Node是LinkedList维护链表结构的核心私有类,比较简单,直接看代码.
private static class Node<E> {
// 元素
E item;
// 指向下一个元素的指针
Node next;// 指向上一个元素的指针
Node prev;
Node(Node prev, E element, Node next) {this.item = element;this.next = next;this.prev = prev;
}
}通过first last俩节点来维护链表进行各项操作,注意transient关键字,自定义了序列化方式.
/** 版本号,用于校验正反序列化时的一致性 */
private static final long serialVersionUID = 876323262645176354L;
/** 元素数量 **/
transient int size = 0;
/** 链表的首节点 */
transient Node first;/** 链表的尾节点 */transient Node last;两个构造器.一个无参,一个插入指定集合.
// 无参构造器
public LinkedList() {}
// 构造一个包含指定集合元素的LinkedList
public LinkedList(Collection extends E> c) {
this();
// 添加指定集合中的所有元素到LinkedList中
addAll(c);
}
由于接口实现较多,各个功能的多个实现核心差不多,这里挑选每种功能里核心的来讲解.如想深入每个函数,请自行
翻阅源码.
查询函数较为简单
/**
* 返回列表中指定位置的元素。
*/
public E get(int index) {
// 检查下标是否是链表内的
checkElementIndex(index);
// node(index) 会获取到下标为index的节点
return node(index).item;
}
Node node(int index) {
// 这里通过简单的二分法,判断index于链表中间位置的距离
if (index > 1)) {
// 若和中间较近从头部开始遍历
Node x = first;for (int i = 0; i x = x.next;return x;
} else {// 否则 从尾节点开始
Node x = last;for (int i = size - 1; i > index; i--)
x = x.prev;return x;
}
}public E getFirst() {final Node f = first;if (f == null)throw new NoSuchElementException();return f.item;
}public E getLast() {final Node l = last;if (l == null)throw new NoSuchElementException();return l.item;
}node(index)函数则是根据下标查找节点.
从这里就可以看出,基于双向链表结构的LinkedList,通过索引index查询是低效的,index元素越靠近中间所耗费的实际就越长,而在链表双端进行查询则会非常高效.
/**
* 删除指定元素
*/
public boolean remove(Object o) {
// LinkedList可以接收null值
if (o == null) {
// 元素为null
for (Node x = first; x != null; x = x.next) {if (x.item == null) {
unlink(x);return true;
}
}
} else {// 元素有值for (Node x = first; x != null; x = x.next) {if (o.equals(x.item)) {
unlink(x);return true;
}
}
}return false;
}/**
* 剔除指定节点,并返回
*/E unlink(Node x) {final E element = x.item;final Node next = x.next;final Node 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相关引用,方便gc
x.item = null;
size--;
modCount++;return element;
}linkedlist arraylist，通过remove(Object o)可以看出LinkedList是支持存储null值的,而unlink(Node x)就是把x节点给置空,同时把x节点的上一个节点和下一个节点关联起来.
/**
* 用指定的元素替换列表中指定位置的元素。
*/
public E set(int index, E element) {
checkElementIndex(index);
// 定位需要修改的节点
Node x = node(index);
E oldVal = x.item;
x.item = element;return oldVal;
}set函数看起来比较简单,只要定位到节点,并修改节点内的元素就行了.
// 添加元素
public boolean add(E e);
// 在指定下标插入元素
public void add(int index, E element);
// 在指定下标插入指定集合
public boolean addAll(int index, Collection extends E> c);
// 添加指定节点为第一个节点
public void addFirst(E e);
// 添加指定节点为尾节点
public void addLast(E e);
// 把指定集合里的元素添加到该LinkedList中
public boolean addAll(Collection extends E> c);
add(E e)函数实际上是通过linklast(E e)来实现.而linklast(E e)内部也较为简单,即在老的last节点后再加入一个节点.注释较全,直接看代码
/**
* 添加元素
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 添加指定元素到尾节点
*/
void linkLast(E e) {
final Node l = last;// 创建一个新节点,同时把这个节点的pred设置为原来的尾节点final Node newNode = new Node<>(l, e, null);// 设置当前节点为last节点
last = newNode;// 如果原本无尾节点,说明当前无任何节点if (l == null)// 把这个新的节点同时设定为首节点
first = newNode;else// 设置 老的尾节点的下一个节点为newNode
l.next = newNode;// 元素数量+1 , 操作+1
size++;
modCount++;
}翻阅源码即可发现类似linkLast(E e)的函数还有俩,
/**
* 添加指定元素为当前的首节点
*/
private void linkFirst(E e) {
final Node f = first;final Node newNode = new Node<>(null, e, f);
first = newNode;if (f == null)
last = newNode;else
f.prev = newNode;
size++;
modCount++;
}/**
* 在指定节点的位置插入节点
*/void linkBefore(E e, Node succ) {final Node pred = succ.prev;final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;if (pred == null)
first = newNode;else
pred.next = newNode;
size++;
modCount++;
}其中linkFirst(E e)和linkLast(E e)没啥区别,无非是把last换成了first.
而linkBefore则是把succ的上一个节点的next指向新节点,同时把新节点的next指向succ,再把succ的prev指向新节点,如下图:
list集合转为数组，该函数用到了上述讲过的 linkLast(element)和linkBefore(element)函数.
/**
* 在指定的下标插入节点
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
先调用checkPositionIndex检测插入下标是否越界,再根据index是否是size来判断调用的插入函数.
/**
* 从指定下标开始插入指定的集合
*/
public boolean addAll(int index, Collection extends E> c) {
// 越界检查
checkPositionIndex(index);
// 转换数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 获取 index索引位置上的节点,和其上一个节点
Node pred, succ;if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}// 从index位置开始插入for (Object o : a) {
E e = (E) o;
Node newNode = new Node<>(pred, e, null);if (pred == null)
first = newNode;else
pred.next = newNode;
pred = newNode;
}// 最后把原位置上节点的prev设置为集合c的最后一个节点if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}// 修改计数
size += numNew;
modCount++;return true;
}addAll(int index, Collection extends E> c)的代码首先是把集合c转换成Object[],然后获取index索引上的节点,再以其上一个节点为起点开始插入.
只要理解了双向链表的存储结,再看LinkedList的源码就会简单很多了.LinkedList其余函数在此就不叙述了,实现上相似.源码分析的差不多了,这里来做下总结.
LinkedList是一个有序的可重复允许null值的集合,看其内部实现不存在容量不足的问题.底层使用了双向链表结构维护了first和last指针.实现了栈和队列相关接口,所以可做栈,队列,双端队列来使用.
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
