技术控

    今日:136| 主题:49228
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] 计算机程序的思维逻辑(39):剖析 LinkedList

[复制链接]
╰等不到的愛 发表于 4 天前
88 1

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
查看历史文章,请点击上方链接关注公众号。
   上节我们介绍了ArrayList,ArrayList随机访问效率很高,但插入和删除性能比较低,我们提到了同样实现了List接口的LinkedList,它的特点与ArrayList几乎正好相反,本节我们就来详细介绍LinkedList。
  除了实现了List接口外,LinkedList还实现了Deque和Queue接口,可以按照队列、栈和双端队列的方式进行操作,本节会介绍这些用法,同时介绍其实现原理。
  我们先来看它的用法。
  用法
  构造方法

  LinkedList的构造方法与ArrayList类似,有两个,一个是默认构造方法,另外一个可以接受一个已有的Collection,如下所示:
   public LinkedList()

  public LinkedList(Collection c)
  比如,可以这么创建:
   List list = new LinkedList<>();
List list2 = new LinkedList<>(
Arrays.asList(new String[]{"a","b","c"}));
  List接口

   LinkedList与ArrayList一样,同样实现了List接口,而List接口扩展了Collection接口,Collection又扩展了Iterable接口,所有这些接口的方法都是可以使用的,使用方法与上节介绍的一样,本节就不再赘述了。
  队列 (Queue)

   LinkedList还实现了队列接口Queue,所谓队列就类似于日常生活中的各种排队, 特点就是先进先出 ,在尾部添加元素,从头部删除元素,它的接口定义为:
   public interface Queue extends Collection {
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
}
  Queue扩展了Collection,它的主要操作有三个:
  
       
  • 在尾部添加元素 (add, offer)
       
  • 查看头部元素 (element, peek),返回头部元素,但不改变队列
       
  • 删除头部元素 (remove, poll),返回头部元素,并且从队列中删除
      
  每种操作都有两种形式,有什么区别呢?区别在于,对于特殊情况的处理不同。特殊情况是指,队列为空或者队列为满,为空容易理解,为满是指队列有长度大小限制,而且已经占满了。LinkedList的实现中,队列长度没有限制,但别的Queue的实现可能有。
  在队列为空时,element和remove会抛出异常NoSuchElementException,而peek和poll返回特殊值null,在队列为满时,add会抛出异常IllegalStateException,而offer只是返回false。
  把LinkedList当做Queue使用也很简单,比如,可以这样:
   Queue queue = new LinkedList<>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
while(queue.peek()!=null){
System.out.println(queue.poll());     
}
  输出为:
   a
b
c
  

   我们在介绍函数调用原理的时候介绍过栈,栈也是一种常用的数据结构,与队列相反, 它的特点是先进后出、后进先出 ,类似于一个储物箱,放的时候是一件件往上放,拿的时候则只能从上面开始拿。
  Java中有一个类Stack,用于表示栈,但这个类已经过时了,我们不再介绍,Java中没有单独的栈接口,栈相关方法包括在了表示双端队列的接口Deque中,主要有三个方法:
  void push(E e);
  E pop();
  E peek();
  解释下:
  
       
  • push表示入栈,在头部添加元素,栈的空间可能是有限的,如果栈满了,push会抛出异常IllegalStateException。
       
  • pop表示出栈,返回头部元素,并且从栈中删除,如果栈为空,会抛出异常NoSuchElementException。
       
  • peek查看栈头部元素,不修改栈,如果栈为空,返回null。
      
  把LinkedList当做栈使用也很简单,比如,可以这样:
   Deque stack = new LinkedList<>();
stack.push("a");
stack.push("b");
stack.push("c");
while(stack.peek()!=null){
System.out.println(stack.pop());     
}
  输出为:
   c
b
a
  双端队列 (Deque)

  栈和队列都是在两端进行操作,栈只操作头部,队列两端都操作,但尾部只添加、头部只查看和删除,有一个更为通用的操作两端的接口Deque,Deque扩展了Queue,包括了栈的操作方法,此外,它还有如下更为明确的操作两端的方法:
  void addFirst(E e);
  void addLast(E e);
  E getFirst();
  E getLast();
  boolean offerFirst(E e);
  boolean offerLast(E e);
  E peekFirst();
  E peekLast();
  E pollFirst();
  E pollLast();
  E removeFirst();
  E removeLast();
  xxxFirst操作头部,xxxLast操作尾部。与队列类似,每种操作有两种形式,区别也是在队列为空或满时,处理不同。为空时,getXXX/removeXXX会抛出异常,而peekXXX/pollXXX会返回null。队列满时,addXXX会抛出异常,offerXXX只是返回false。
  栈和队列只是双端队列的特殊情况,它们的方法都可以使用双端队列的方法替代,不过,使用不同的名称和方法,概念上更为清晰。
  Deque接口还有一个迭代器方法,可以从后往前遍历
  Iterator descendingIterator();
  比如,看如下代码:
   Deque deque = new LinkedList<>(
Arrays.asList(new String[]{"a","b","c"}));
Iterator it = deque.descendingIterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
  输出为
  c b a
  用法小结

  LinkedList的用法是比较简单的,与ArrayList用法类似,支持List接口,只是,LinkedList增加了一个接口Deque,可以把它看做队列、栈、双端队列,方便的在两端进行操作。
  如果只是用作List,那应该用ArrayList还是LinkedList呢?我们需要了解下LinkedList的实现原理。
  实现原理
  内部组成

   我们知道,ArrayList内部是数组,元素在内存是连续存放的,但LinkedList不是。LinkedList直译就是链表,确切的说,它的内部实现是 双向链表 ,每个元素在内存都是单独存放的,元素之间通过链接连在一起,类似于小朋友之间手拉手一样。
   为了表示链接关系,需要一个 节点 的概念,节点包括实际的元素,但同时有两个链接,分别指向前一个节点(前驱)和后一个节点(后继),节点是一个内部类,具体定义为:
   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;
}
}
  Node类表示节点,item指向实际的元素,next指向下一个节点,prev指向前一个节点。
  LinkedList内部组成就是如下三个实例变量:
  transient int size = 0;
  transient Node first;
  transient Node last;
  我们暂时忽略transient关键字,size表示链表长度,默认为0,first指向头节点,last指向尾节点,初始值都为null。
  LinkedList的所有public方法内部操作的都是这三个实例变量,具体是怎么操作的?链接关系是如何维护的?我们看一些主要的方法,先来看add方法。
  Add方法

  add方法的代码为:
   public boolean add(E e) {
linkLast(e);
return true;
}
  主要就是调用了linkLast,它的代码为:
   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++;
}
  代码的基本步骤是:
  1. 创建一个新的节点newNode。prev指向原来的尾节点,如果原来链表为空,则为null。代码为:
  Node newNode = new Node<>(l, e, null);
  2. 修改尾节点last,指向新的最后节点newNode。代码为:
  last = newNode;
  3. 修改前节点的后向链接,如果原来链表为空,则让头节点指向新节点,否则让前一个节点的next指向新节点。代码为:
   if (l == null)
first = newNode;
else
l.next = newNode;
  4. 增加链表大小。代码为:
  size++
  modCount++的目的与ArrayList是一样的,记录修改次数,避免迭代中间并发修改错误。
  我们通过一些图示来更清楚的看一下,比如说,代码为:
   List list = new ArrayList();
list.add("a");
list.add("b");

  执行完第一行后,内部结构如下所示:
   
计算机程序的思维逻辑(39):剖析 LinkedList-1 (计算机程序,public,文章,接口,历史)

添加完"a"后,内部结构如下所示:

计算机程序的思维逻辑(39):剖析 LinkedList-2 (计算机程序,public,文章,接口,历史)

添加完"b"后,内部结构如下所示:
123下一页
友荐云推荐




上一篇:TANK: A very high performance distributed log service
下一篇:对于企业网站建设来说 哪些内容是必不可少的“干货”
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

meptn 发表于 4 天前
谁说colabug的人气不行了?
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表