情不知所起,一往而深。恨不知所踪,一笑而泯。

原创Java学习篇之---LinkedList

2016-05-19 16:12:06

LinkedList

Java.util.LinkedList是双向链表。

LinkedList的两个remove方法,remove(Object)和remove(int)的时间复杂度都是O(n),在链表元素很多 并且没有索引可用的情况下,LinkedList也并不适合做随机增删元素。在对性能特别敏感的场景下,还是需要自己实现专用的双向链表结构,真正实现 O(1)级别的随机增删。更进一步,jdk5引入的ConcurrentLinkedQueue是一个非阻塞的线程安全的双向队列实现。

理论上说,双向链表的删除的时间复杂度是O(1),你只需要将要删除的节点的前节点和后节点相连,然后将要删除的节点的前节点和后节点置为null即可:


    //伪代码  
      node.prev.next=node.next;  
      node.next.prev=node.prev;  
      node.prev=node.next=null;  

注意:

ArrayList和LinkedList的区 别之在什么场景下用:

大家都会说LinkedList随机增删多的场景比较合适,而ArrayList的随机访问多的场景比较合适。

联系我们 联系人:Neal Zhang 联系邮箱:master@pplns.com
© 2017 pplns.com 版权所有.