前言
在上篇文章中我们对 ArrayList 对了详细的分析,今天我们来说一说 LinkedList.他们之间有什么区别呢?最大的区别就是底层数据结构的实现不一样,ArrayList 是数组实现的(具体看上一篇文章),LinedList 是链表实现的.至于其他的一些区别,可以说大部分都是由于本质不同衍生出来的不同应用.
LinkedList
链表
在分析 LinedList 之前先对链表做一个简单的介绍,毕竟链表不像数组一样使用的多,所以很多人不熟悉也在所难免.
链表是一种基本的线性数据结构,其和数组同为线性,但是数组是内存的物理存储上呈线性,逻辑上也是线性;而链表只是在逻辑上呈线性.在链表的每一个存储单元中不仅存储有当前的元素,还有下一个存储单元的地址,这样的可以通过地址将所有的存储单元连接在一起.
每次查找的时候,通过第一个存储单元就可以顺藤摸瓜的找到需要的元素.执行删除操作只需要断开相关元素的指向就可以了.示意图如下:
2018-01-10_114030
2018-01-10_114053
2018-01-10_114109
当然了在?LinkedList 中使用的并不是最基本的单向链表,而是双向链表.
在 LinedList 中存在一个基本存储单元,是 LinkedList 的一个内部类,节点元素存在两个属性,分别保存前一个节点和后一个节点的引用.
定义
//静态内部类
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;
}
}
在定义上和 ArrayList 大差不差,但是需要注意的是,LinkedList 实现了 Deque(间接实现了 Qeque 接口),Deque 是一个双向对列,为 LinedList 提供了从对列两端访问元素的方法.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
初始化
在分析 ArrayList 的时候我们知道 ArrayList 使用无参构造方法时的初始化长度是 10,并且所有无参构造出来的集合都会指向同一个对象数组(静态常量,位于方法区),那么 LinkedList 的初始化是怎样的呢?
打开无参构造方法
什么都没有,那么只能够去看属性了.
public LinkedList() {
}
图示初始化
//初始化长度为0
transient int size = 0;
//有前后节点
transient Node < E > first;
transient Node < E > last;
LinkedList < String > list = new LinkedList < String > ();
String s = "sss";
list.add(s);
方法
从方法中我们知道在调用添加方法之后,并不是立马添加的,而是调用了 linkLast 方法,见名知意,新元素的添加位置是集合最后.
add(E e)
public boolean add(E e) {
linkLast(e);
return true;
}
从以上代码中我们可以看到其在添加元素的时候并不依赖下标.
void linkLast(E e) {
// 将最后一个元素赋值(引用传递)给节点l final修饰符 修饰的属性赋值之后不能被改变
final Node < E > l = last;
// 调用节点的有参构造方法创建新节点 保存添加的元素
final Node < E > newNode = new Node < >(l, e, null);
//此时新节点是最后一位元素 将新节点赋值给last
last = newNode;
//如果l是null 意味着这是第一次添加元素 那么将first赋值为新节点 这个list只有一个元素 存储元素 开始元素和最后元素均是同一个元素
if (l == null) first = newNode;
else
//如果不是第一次添加,将新节点赋值给l(添加前的最后一个元素)的next
l.next = newNode;
//长度+1
size++;
//修改次数+1
modCount++;
}
而其中的处理是,通过一个 last(Node 对象)保存最后一个节点的信息(实际上就是最后一个节点),每次通过不断的变化最后一个元素实现元素的添加.(想要充分理解此处,需要理解 java 值传递和引用传递的区别和本质).
add(int index, E element)
添加到指定的位置public void add(int index, E element) {
节点元素插入图示
//下标越界检查
checkPositionIndex(index);
//如果是向最后添加 直接调用linkLast
if (index == size) linkLast(element);
//反之 调用linkBefore
else linkBefore(element, node(index));
}
//在指定元素之前插入元素
void linkBefore(E e, Node < E > succ) {
// assert succ != null; 假设断言 succ不为null
//定义一个节点元素保存succ的prev引用 也就是它的前一节点信息
final Node < E > pred = succ.prev;
//创建新节点 节点元素为要插入的元素e prev引用就是pred 也就是插入之前succ的前一个元素 next是succ
final Node < E > newNode = new Node < >(pred, e, succ);
//此时succ的上一个节点是插入的新节点 因此修改节点指向
succ.prev = newNode;
// 如果pred是null 表明这是第一个元素
if (pred == null)
//成员属性first指向新节点
first = newNode;
//反之
else
//节点前元素的next属性指向新节点
pred.next = newNode;
//长度+1
size++;
modCount++;
}
在上面的代码中我们应该注意到了,LinkedList 在插入元素的时候也要进行一定的验证,也就是下标越界验证,下面我们看一下具体的实现.
通过对两个添加方法的分析,我们可以很明显的感受到 LinkedList 添加元素的效率,不需要扩容,不需要复制数组.
private void checkPositionIndex(int index) {
if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//如果输入的index在范围之内返回ture
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
在这段代码中充分体现了双向链表的优越性,可以从前也可以从后开始遍历,通过对 index 范围的判断能够显著的提高效率.但是在遍历的时候也可以很明显的看到 LinkedList get 方法获取元素的低效率,时间复杂度 O(n).
get public E get(int index) {
//检查下标元素是否存在 实际上就是检查下标是否越界
checkElementIndex(index);
//如果没有越界就返回对应下标节点的item 也就是对应的元素
return node(index).item;
}
//下标越界检查 如果越界就抛异常
private void checkElementIndex(int index) {
if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//该方法是用来返回指定下标的非空节点
Node < E > node(int index) {
//假设下标未越界 实际上也没有越界 毕竟在此之前执行了下标越界检查
// assert isElementIndex(index);
//如果index小于size的二分之一 从前开始查找(向后查找) 反之向前查找
if (index < (size >> 1)) { //左移 效率高 值得学习
Node < E > x = first;
//遍历
for (int i = 0; i < index; i++)
//每一个节点的next都是他的后一个节点引用 遍历的同时x会不断的被赋值为节点的下一个元素 遍历到index是拿到的就是index对应节点的元素
x = x.next;
return x;
} else {
Node < E > x = last;
for (int i = size - 1; i > index; i--) x = x.prev;
return x;
}
}
remove(int index)
所谓删除节点 就是把节点的前后引用置为 null,并且保证没有任何其他节点指向被删除节点.
说明
public E remove(int index) {
//下标越界检查
checkElementIndex(index);
//此处的返回值实际上是执行了两个方法
//node获取制定下标非空节点
//unlink 断开指定节点的联系
return unlink(node(index));
}
E unlink(Node < E > x) {
//假设x不是null
// assert x != null;
//定义一个变量element接受x节点中的元素 最后会最后返回值返回
final E element = x.item;
//定义连个节点分别获得x节点的前后节点引用
final Node < E > next = x.next;
final Node < E > prev = x.prev;
//如果节点前引用为null 说明这是第一个节点
if (prev == null) {
//x是第一个节点 即将被删除 那么first需要被重新赋值
first = next;
} else {
//如果不是x不是第一个节点 将prev(x的前一个节点)的next指向x的后一个节点(绕过x)
prev.next = next;
//x的前引用赋值null
x.prev = null;
}
//如果节点后引用为null 说明这是最后一个节点 一系列类似前引用的处理方式 不再赘述
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//将x节点中的元素赋值null
x.item = null;
size--;
modCount++;
return element;
}
prev,item,next 均置为 null 是为了让虚拟机回收
我们可以看到 LinkedList 删除元素的效率也不错
LinkedList 总结
查询速度不行,每次查找都需要遍历,这就是在 ArrayList 分析时提到过的顺序下标遍历
添加元素,删除都很有速度优势
实现对列接口
ArrayList 和 LinkedList 的区别
顺序插入,两者速度都很快,但是 ArrayList 稍快于 LinkedList,数组实现,数组是提前创建好的;LinkedList 每次都需要重新 new 新节点
LinedList 需要维护前后节点,会更耗费内存
遍历,LinedList 适合用迭代遍历;ArrayList 适合用循环遍历
不要使用普通 for 循环遍历 LinedList
也不要使用迭代遍历遍历 ArrayList(具体看上篇文章《ArrayList 分析》)
删除和插入就不说了,毕竟 ArrayList 需要复制数组和扩容.
我不能保证每一个地方都是对的,但是可以保证每一句话,每一行代码都是经过推敲和斟酌的.希望每一篇文章背后都是自己追求纯粹技术人生的态度.
永远相信美好的事情即将发生.
来源: https://www.cnblogs.com/bingyang-py/p/8305757.html