0°

Java LinkedList源码剖析

内容预览:
  • 关于栈或队列,现在的首选是ArrayDeque,它有着比LinkedList(当作栈或...~
  • 注意这里没有所谓的哑元,当链表为空的时候first和last都指向null~
  •        final Node<E> pred = succ.prev; &n...~

始发于微信公众号: 程序员小乐

分享编程技能、互联网技术、生活感悟、打造干货分享平台,将总结的技术、心得、经验分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “程序员小乐” ,选择“置顶公众号”,第一时间送达!


每日英文
Things always have a way of working out when you least expect it. Never give it up.
事情总是在你最不抱期望的时候得到解决,所以,永远不要放弃。

乐乐有话说
这个世界,已经有很多人和事让你失望了,而最不应该的,就是自己还令自己失望。一定要记住:社会很残酷,你要活得有温度。

总体介绍

LinkedList同时实现了List接口和Deque接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类,更遗憾的是,Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列,现在的首选是ArrayDeque,它有着比LinkedList(当作栈或队列使用时)有着更好的性能。

Java LinkedList源码剖析

LinkedList底层通过双向链表实现,本节将着重讲解插入和删除元素时双向链表的维护过程,也即是之间解跟List接口相关的函数,而将Queue和Stack以及Deque相关的知识放在下一节讲。双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元,当链表为空的时候first和last都指向null。

//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的实现方式决定了所有跟下标相关的操作都是线性时间,而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized),如果需要多个线程并发访问,可以先采用Collections.synchronizedList()方法对其进行包装。

方法剖析

add()

add()方法有两个版本,一个是add(E e),该方法在LinkedList的末尾插入元素,因为有last指向链表末尾,在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可;另一个是add(int index, E element),该方法是在指定下表处插入元素,需要先通过线性查找找到具体位置,然后修改相关引用完成插入操作。

Java LinkedList源码剖析

结合上图,可以看出add(E e)的逻辑非常简单。

//add(E e)
public boolean add(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++;
   return true;
}

add(int index, E element)的逻辑稍显复杂,可以分成两部,1.先根据index找到要插入的位置;2.修改引用,完成插入操作。

//add(int index, E element)
public void add(int index, E element) {
   checkPositionIndex(index);//index >= 0 && index <= size;
   if (index == size)//插入位置是末尾,包括列表为空的情况
       add(element);
   else{
       Node<E> succ = node(index);//1.先根据index找到要插入的位置
       //2.修改引用,完成插入操作。
       final Node<E> pred = succ.prev;
       final Node<E> newNode = new Node<>(pred, e, succ);
       succ.prev = newNode;
       if (pred == null)//插入位置为0
           first = newNode;
       else
           pred.next = newNode;
       size++;
   }
}

上面代码中的node(int index)函数有一点小小的trick,因为链表双向的,可以从开始往后找,也可以从结尾往前找,具体朝那个方向找取决于条件index < (size >> 1),也即是index是靠近前端还是后端。

remove()

remove()方法也有两个版本,一个是删除跟指定元素相等的第一个元素remove(Object o),另一个是删除指定下标处的元素remove(int index)。

Java LinkedList源码剖析

两个删除操作都要1.先找到要删除元素的引用,2.修改相关引用,完成删除操作。在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法,而remove(int index)使用的是下标计数,两种方式都是线性时间复杂度。在步骤2中,两个revome()方法都是通过unlink(Nodex)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

//unlink(Node<E> x),删除一个Node
E unlink(Node<E> x) {
   final E element = x.item;
   final Node<E> next = x.next;
   final Node<E> 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;//let GC work
   size--;
   return element;
}

get()

get(int index)得到指定下标处元素的引用,通过调用上文中提到的node(int index)方法实现。

public E get(int index) {
   checkElementIndex(index);//index >= 0 && index < size;
   return node(index).item;
}

set()

set(int index, E element)方法将指定下标处的元素修改成指定值,也是先通过node(int index)找到对应下表元素的引用,然后修改Node中item的值。

public E set(int index, E element) {
   checkElementIndex(index);
   Node<E> x = node(index);
   E oldVal = x.item;
   x.item = element;//替换新值
   return oldVal;
}

如果您觉得不错,请别忘了转发、分享、点赞让更多的人去学习, 您的举手之劳,就是对小乐最好的支持,非常感谢!


如何您想进技术群交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:CarpenterLee

链接:http://www.cnblogs.com/CarpenterLee/

著作权归作者所有,本文已获得授权,欢迎投稿。

Java LinkedList源码剖析

推荐阅读


看完本文有收获?请转发分享给更多人
关注「程序员小乐」,提升技能

以上就是:Java LinkedList源码剖析 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论