前言
前面一篇我们分析了ArrayList的源码,这一篇分享的是LinkedList。我们都知道它的底层是由链表实现的,所以我们要明白什么是链表?
一、LinkedList简介
1.1、LinkedList概述
- LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列,它是基于双向链表实现的。
- LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
- LinkedList 实现 List 接口,能对它进行队列操作。
- LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
- LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
- LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
- LinkedList 是非同步的。
1.2、LinkedList的数据结构
1)基础知识补充
1.1)单向链表:通过每个结点的指针指向下一个结点从而链接起来的结构,最后一个节点的next指向null。
element:用来存放元素
next:用来指向下一个节点元素
1.2)单向循环链表
element、next 跟前面一样
在单向链表的最后一个节点的next会指向头节点,而不是指向null,这样存成一个环
1.3)双向链表:包含两个指针的,pre指向前一个节点,next指向后一个节点,但是第一个节点head的pre指向null,最后一个节点的tail也指向null。
element:存放元素
pre:用来指向前一个元素
next:指向后一个元素
1.4)双向循环链表
element、pre、next 跟前面的一样
第一个节点的pre指向最后一个节点,最后一个节点的next指向第一个节点,也形成一个“环”。
2)LinkedList的数据结构
如上图所示:LinkedList底层使用的是双向链表结构,有一个头结点和一个尾结点,双向链表意味着我们可以从头开始正向遍历,或者是从尾开始逆向遍历,并且可以针对头部和尾部进行相应的操作。
1.3、LinkedList的特性
- 异步,也就是非线程安全
- 双向链表,由于实现了list和Deque接口,能够当作队列来使用。链表:查询效率不高,但是插入和删除这种操作性能好。
- 是顺序存储结构(注意和随机存取结构两个概念搞清楚)
二、LinkedList源码分析
2.1、LinkedList的继承结构以及层次关系
分析:我们可以看到,linkedList在最底层,说明他的功能最为强大,并且细心的还会发现,arrayList只有四层,这里多了一层AbstractSequentialList的抽象类,为什么呢?
通过API我们会发现:
- 减少实现顺序存取(例如LinkedList)这种类的工作,就是方便,抽象出类似LinkedList这种类的一些共同的方法
- 那么如果想自己实现顺序存取这种特性的类(就是链表形式),那么就继承这个AbstractSequentialList抽象类,如果想像数组那样的随机存取的类,那么就去实现AbstractList抽象类。
- 这样的分层,就很符合我们抽象的概念,越往高处的类,就越抽象,越往底层的类,就越有自己独特的个性。
- 实现了Deque接口,那么也就意味着LinkedList是双端队列的一种实现,所以,基于双端队列的操作在LinkedList中全部有效。
实现接口分析:
public class LinkedList
1)List接口:列表,add、set、等一些对列表进行操作的方法
2)Deque接口:有队列的各种特性,
3)Cloneable接口:能够复制,使用那个copy方法。
4)Serializable接口:能够序列化。
5)应该注意到没有RandomAccess:那么就推荐使用iterator,在其中就有一个foreach,增强的for循环,其中原理也就是iterator,我们在使用的时候,使用foreach或者iterator都可以。
2.2、类的属性
public class LinkedList
transient Node<E> first;**//头结点**
transient Node<E> last;**//尾结点**
LinkedList属性非常简单,一个头结点、一个尾结点、一个表示链表中实际元素的变量。注意,头尾结点都有transient关键字修饰,这也意味着在序列化时该域是不会序列化的。
2.3、LinkedList的构造方法
两个构造方法(两个构造方法都是规范规定需要写的)
1)空参构造函数
/** * Constructs an empty list. */ public LinkedList() { }
2)有参构造函数
//将集合中的元素构建成LinkedList链表 public LinkedList(Collection<? extends E> c) { //调用无参构造函数 this(); //添加集合中所有的元素 addAll(c); }
2.4、内部类(Node)
//根据前面介绍双向链表就知道这个代表什么了,linkedList的奥秘就在这里
private static class Node
//构造函数,初始化值
Node(Node
2.5、核心方法
2.5.1、add()方法
1)add(E)
public boolean add(E e) { //添加到末尾 linkLast(e); return true; }
说明:add函数用于向LinkedList中添加一个元素,并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的。
分析:LinkLast(XXXXX)
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node
说明:对于添加一个元素至链表中会调用add方法->LinkLast方法
举例一:
LinkedList
首先调用无参构造函数,之后添加元素5,之后再添加元素6。具体的示意图如下:
2.5.2、addAll方法
addAll有两个重载函数,addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型,我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型。
1)addAll(c);
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
//将集合c转换为Object数组a
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
//集合为空,则什么都不做,返回false
return false;
//定义两个结点(内部类),每个结点都有三个属性,item,next,prev.
Node
//将遍历数组a中的元素,封装为一个个结点
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//pred就是之前构建好的,可能为null,也可能不为null
Node
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
说明:参数中的index表示在索引下标为index的结点(实际上是第index + 1个结点)的前面插入。
在addAll函数中,addAll函数中还会调用到node函数,get函数也会调用到node函数,此函数是根据索引下标找到该结点并返回,具体代码如下:
Node
//判断插入的位置在链表的前半段或者后半段
if (index < (size >> 1)) {//插入位置在前半段
Node
说明:在根据索引查找结点时,会有一个小优化,结点在前半段则从头开始遍历,在后半段则从尾开始遍历,这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。
举例说明调用addAll函数后的链表状态:
List
上述代码内部的链表结构如下:
addAll()中的一个问题:
在addAll函数中,传入一个集合参数和插入位置,然后将集合转化为数组,然后再遍历数组,挨个添加数组的元素,但是问题来了,为什么要先转化为数组再进行遍历,而不是直接遍历集合呢?
从效果上两者是完全等价的,都可以达到遍历的效果。关于为什么要转化为数组的问题,我的思考如下:
1. 如果直接遍历集合的话,那么在遍历过程中需要插入元素,在堆上分配内存空间,修改指针域,这个过程中就会一直占用着这个集合,考虑正确同步的话,其他线程只能一直等待。
2. 如果转化为数组,只需要遍历数组,而遍历数组过程中不需要额外的操作,
所以占用的时间相对是较短的,这样就利于其他线程尽快的使用这个集合。说白了,就是有利于提高多线程访问该集合的效率,尽可能短时间的阻塞。
2.5.3、remove(Object o)
//如果我们要移除的值在链表中存在多个一样的值,那么我们会移除index最小的那个,也就是最先找到的那个值,如果不存在这个值,那么什么也不做
public boolean remove(Object o) {
//这里可以知道,linkedList也能存储null
if (o == null) {
//循环遍历链表。直到找到null值,然后使用unlink移除该值。
for (Node
unlink(xxxx)
E unlink(Node
//这里开始往下就进行移除该元素的操作,也就是把指向那个结点搞定 if (prev == null) { //说明移除的结点是头结点,则first头结点应该指向下一个结点 first = next; } else { //不是头结点,prev.next=next: prev.next = next; //然后解除x结点的指向 x.prev = null; }
if (next == null) {
//说明移除的结点是尾结点 last = prev; } else { //不是尾结点 next.prev = prev; x.next = null; } //x的前后都指向为null,也把item为null,让gc回收它 x.item = null; //移除一个结点,size自减 size--; modCount++; return element;//由于一开始保存了x的值到element,所以返回 }
2.5.4、get(index)
get(index)查询元素的方法
public E get(int index) { checkElementIndex(index); return node(index).item; }
Node
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;
}
}
2.5.5、indexOf(Object o)
//这个很简单,就是通过实体元素来查找到该元素在链表中的位置
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node
三、LinkedList的迭代器
在LinkedList中除了有一个Node的内部类外,应该还能看到另外两个内部类,那就是ListItr,还有一个是DescendingIterator。
3.1、ListItr内部类
public ListIterator
看一下他的继承结构,发现只继承了一个ListIterator,到ListIterator中一看:
看到方法名之后,就发现不止有向后迭代的方法,还有向前迭代的方法,所以我们就知道了这个ListItr这个内部类干嘛用的了,就是能让linkedList不光能像后迭代,也能向前迭代。
看一下ListItr中的方法,可以发现,在迭代的过程中,还能移除、修改、添加值得操作。
3.2、DescendingIterator内部类
private class DescendingIterator implements Iterator
看下这个类,还是调用ListItr,作用是封装一下Itr中几个方法,让使用者以正常的思维去写代码,例如,在从后往前遍历的时候,也是跟从前往后遍历一样,使用next等操作,而不使用previous。
微软面试题:
掌握LinkedList的特殊方法,用LinkedList实现字符串反转输出,实现字符串0到k 和k+1到2k反转,再合并输出
public class Linked001 {
public static void main(String[] args) {
String str="abcdefgh";
System.out.println("要反转的字符串:"+str);
LinkedList
LinkedList<Character> list2 = new LinkedList<>();
for (int i = str.length()>>1; i < str.length(); i++) {
char c=str.charAt(i);
list2.addFirst(c);
}
System.out.println("list2,k+1->2k之间:"+list2);
list.addAll(list2);
System.out.println("合并后,2k:"+list);
String newStr="";
while (list.size()>0){
newStr+=list.**removeFirst**();
}
System.out.println("newStr:"+newStr);
}
}
public void addFirst(E e) { linkFirst(e); }
private void linkFirst(E e) {
//先记录first结点,若第一次添加,first=null,则f=null
final Node
public E removeFirst() {
final Node
private E unlinkFirst(Node
输出结果:
四、总结
1)linkedList本质上是一个双向链表,通过一个Node内部类实现的这种链表结构。
2)能存储null值
3)跟arrayList相比较,就真正的知道了,LinkedList在删除和增加等操作上性能好,而ArrayList在查询的性能上好
4)从源码中看,它不存在容量不足的情况
5)linkedList不光能够向前迭代,还能像后迭代,并且在迭代的过程中,可以修改值、添加值、还能移除值。
6)linkedList不光能当链表,还能当队列使用,这个就是因为实现了Deque接口