摘要：类定义是接口的简化版，支持按次序访问，支持随机访问。否则将原尾节点的尾指针指向。在某结点之前插入元素。根据索引随机访问，为方法的真正实现。总结其实只要你对双向链表结构比较熟悉，那源码读起来就会很轻松。
linkedlist简单介绍（jdk1.8）
linkedlist的底层结构是线性表的双向链表，每个节点包括两个指针域（一个指向前驱结点，一个指向后继结点）和一个数据域，因为双指针域的独特结构，所以其拥有增删快和存取慢的特点。链表结构不需要预分配存储空间，增加新的结点再去内存中申请即可，不会造成内存浪费和碎片化。
类定义AbstractSequentialList是List接口的简化版，支持按次序访问，abstractList支持随机访问。
list接口许多常用的基础方法,如set,get,indexof,remove等
Deque是一个双端队列接口，提供了类似栈、队列,push,pop,peek的方法
Cloneable代表可以被复制
Serializable代表可以被序列化
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable
和Arraylist一样，linkedlist也是一个非线程安全的集合，只能在单线程环境下使用。若想获得一个线程安全的linkedlist可以使用：
List类属性
transient int size = 0;
transient Nodefirst;
transient Nodelast;
size:双向链表中节点的个数
first:指向链表的首结点
last:指向链表的尾结点
public LinkedList() {}
public LinkedList(Collection c) {
this();
addAll(c);
}
构造函数只有两个，第一个非常简单，构造一个空的linkedList。第二个有参构造就是所有Collection下的子类都通过toArray变为数组，然后通过遍历生成节点插入双向链表中。
核心方法在阅读核心方法之前，我们首先需要了解它的核心内部类Node和ListItr.
Node
链表中的单个结点，具有两个指针域和一个数据域，其结构为:
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
ListItr
AbstractSequentialList定义了抽象方法listIterator,linkedlist实现此方法，并返回迭代器ListItr;其结构为：
private class ListItr implements ListIterator{ private Node lastReturned; private Node next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; }
其实迭代器的核心就是游标，如果不清楚迭代器可以自行查询相关原理，lastReturned是游标前的元素，迭代器中修改数据结构的方法操作的都是lastReturned，next就是游标后元素，nextIndex为next的索引，expectedModCount
为父类AbstractList的modCount，因为是线程不安全的类，用来触发fast-fail机制。用来遍历iterator的有hasNext(),next(),hasPrevious(),previous()。通过iterator修改linkedlist的有remove(),set(),add(),操作的都是游标前元素lastReturned，并且会根据modcount来触发fast-fail机制的检验，这些方法的实现依赖于linkedlist的核心方法。 终于说完ListItr，强烈建议你们自己看下源码，接下来让我们一起看下linkedlist的实现：
//将头结点赋值给final f，新建一个新的结点newNode,将newNode定义为头节点。如果f=null，说明此前是个空链表，所以last也定义newNode，否则将原头节点f（现第二个节点）的前指针指向newNode
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++;
}
//将尾结点指向final l，声明一个新的结点newNode（头指针指向尾结点，尾指针指向null），将newNode定义 为新的尾结点。如果l=null，代表原链表没有尾节点（空链表），则将newNode也设为头节点。否则将原尾节点l的尾指针指向newNode。
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//在某结点之前插入元素。在AC结点中插入b元素，将b元素生成B结点，将B节点的前指针指向A，后指针指向C,将C的前指针指向B，将A的后指针指向B
void linkBefore(E e, Node succ) {
// assert succ != null;
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++;
}
//将结点从链表中分离。
E unlink(Node x) {
// assert x != null;
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.item = null;
size--;
modCount++;
return element;
}
//根据索引随机访问linkedlist，为get方法的真正实现。 //size右移1位，大致相当于size/2.若index>size/2，则从尾结点向前遍历，否则从头结点向后遍历 Node总结node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; 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 set(int index, E element) { checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = element; return oldVal; } public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } //查询o最后一次出现的索引，将o分为两种情况，一种为==null，另一种用equals比较，后序遍历得索引值。 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
其实只要你对双向链表结构比较熟悉，那linkedlist源码读起来就会很轻松。linkedlist不需要分配存储空间，只要有就可以分配，元素个数也不受限制，在找到指定索引的结点后，进行增删改都是O（1）的操作，效率非常高。在遍历linkedlist的时候，最好使用foreach或者iterator，严禁直接使用get（）遍历。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/68053.html
摘要：我的是忙碌的一年，从年初备战实习春招，年三十都在死磕源码，三月份经历了阿里五次面试，四月顺利收到实习。因为我心理很清楚，我的目标是阿里。所以在收到阿里之后的那晚，我重新规划了接下来的学习计划，将我的短期目标更新成拿下阿里转正。 我的2017是忙碌的一年，从年初备战实习春招，年三十都在死磕JDK源码，三月份经历了阿里五次面试，四月顺利收到实习offer。然后五月怀着忐忑的心情开始了蚂蚁金...
摘要：删除元素作为双端队列，删除元素也有两种方式，一种是队列首删除元素，一种是队列尾删除元素。作为，又要支持中间删除元素，所以删除元素一个有三个方法，分别如下。在中间删除元素比较低效，首先要找到删除位置的节点，再修改前后指针，时间复杂度为。 介绍 LinkedList是一个以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用，它是怎么实现的呢？让我们一起来学习吧。 继...
摘要：常用集合使用场景分析过年前的最后一篇，本章通过介绍，，，底层实现原理和四个集合的区别。和都是线程安全的，不同的是前者使用类，后者使用关键字。面试官会认为你是一个基础扎实，内功深厚的人才到这里常用集合使用场景分析就结束了。 Java 常用List集合使用场景分析 过年前的最后一篇，本章通过介绍ArrayList，LinkedList，Vector，CopyOnWriteArrayList...
摘要：前言在上篇文章中我们对对了详细的分析，今天我们来说一说。他们之间有什么区别呢最大的区别就是底层数据结构的实现不一样，是数组实现的具体看上一篇文章，是链表实现的。至于其他的一些区别，可以说大部分都是由于本质不同衍生出来的不同应用。 前言 在上篇文章中我们对ArrayList对了详细的分析，今天我们来说一说LinkedList。他们之间有什么区别呢？最大的区别就是底层数据结构的实现不一样，...
阅读 702·2023-04-25 17:54
阅读 2944·2021-11-18 10:02
阅读 1115·2021-09-28 09:35
阅读 625·2021-09-22 15:18
阅读 2820·2021-09-03 10:49
阅读 2995·2021-08-10 09:42
阅读 2546·2019-08-29 16:24
阅读 1235·2019-08-29 15:08
