您的位置 首页 java

java源码之LinkedList源码

LinkedList优点:

  1. 基于双向 链表 实现,增删改的效率很高
  2. 可以当队列来用

LinkedList缺点:

  1. 链表查找的时间复杂度是O(n),所以随机读是非常慢的

LinkedList使用场景:

LinkedList在生产中使用较ArrayList少很多,因为一般程序都是读多写少,LinkedList却更适合写多读少的情况。

LinkedList主要方法解析:

add(E e):在双向链表尾部插入一个元素

  1. 生成指针l指向双向链表中的最后一个元素last
  2. 生成一个新的 node 节点,pre是last,next是null
  3. 把last指针指向新node
  4. 如果l是null说明新node是第一个元素,则把first指针指向新node,否则说明新node不是第一个元素,l的next指针指向新node
  5. size++和modCount++

这里说明下modCount的作用,主要是防止在遍历LinkedList时对Linked进行add或remove元素,有这种操作都会报oncurrentModification Exception

add(int index,E e):在双向链表指定位置插入一个元素

  1. 检查index是否小于0或大于size,是的话报错
  2. index是否等于size,等于则在双向链表的尾部插入 linkLast(e)
  3. 找到ndex位置上的元素:node(index)

如果index小于size的一半则从链表的head开始遍历前部分,否则从链表的tail开始遍历后部分

  1. 把元素插入到index元素之前:linkBefore(e,succ)
    1. 拿到node的prev元素succ
    2. 生成新的节点:new Node<>(pred, e, succ)
    3. succ的prev指向new node
    4. 如果prev是null说明新node是第一个元素,则把first指针指向新node,否则说明新node不是第一个元素,prev的next指针指向新node
    5. size++和modeCount++

get(i),getFist(),getLast()方法:获取指定index的元素,获取第一个元素,获取最后一个元素

这些比较简单不多说了

链表和数组的区别:

链表的元素操作都是指针的移动和头尾节点维护,在增删改方面的性能很高,但查的时间复杂度是O(n),数组则正好相反,在增删改方面的性能很差(涉及到数组的扩容以及元素的迁移),但查是寻址操作,性能非常高

单向链表和双向链表的区别

单向链表只有指向下一个元素的next指针,相对双向链表来说,指针维护简单,但遍历时只能从head开始,时间复杂度是O(n),双向链表有指向前后两个node的指针,指针维护较复杂,但遍历时可以通过head和tail两种方式查找,在get(i)和add(i,e)效率较单向链表高

欢迎关注”java面试工程师“公众号

文章来源:智云一二三科技

文章标题:java源码之LinkedList源码

文章地址:https://www.zhihuclub.com/188056.shtml

关于作者: 智云科技

热门文章

网站地图