LinkedList优点:
- 基于双向 链表 实现,增删改的效率很高
- 可以当队列来用
LinkedList缺点:
- 链表查找的时间复杂度是O(n),所以随机读是非常慢的
LinkedList使用场景:
LinkedList在生产中使用较ArrayList少很多,因为一般程序都是读多写少,LinkedList却更适合写多读少的情况。
LinkedList主要方法解析:
add(E e):在双向链表尾部插入一个元素
- 生成指针l指向双向链表中的最后一个元素last
- 生成一个新的 node 节点,pre是last,next是null
- 把last指针指向新node
- 如果l是null说明新node是第一个元素,则把first指针指向新node,否则说明新node不是第一个元素,l的next指针指向新node
- size++和modCount++
这里说明下modCount的作用,主要是防止在遍历LinkedList时对Linked进行add或remove元素,有这种操作都会报oncurrentModification Exception
add(int index,E e):在双向链表指定位置插入一个元素
- 检查index是否小于0或大于size,是的话报错
- index是否等于size,等于则在双向链表的尾部插入 linkLast(e)
- 找到ndex位置上的元素:node(index)
如果index小于size的一半则从链表的head开始遍历前部分,否则从链表的tail开始遍历后部分
- 把元素插入到index元素之前:linkBefore(e,succ)
- 拿到node的prev元素succ
- 生成新的节点:new Node<>(pred, e, succ)
- succ的prev指向new node
- 如果prev是null说明新node是第一个元素,则把first指针指向新node,否则说明新node不是第一个元素,prev的next指针指向新node
- size++和modeCount++
get(i),getFist(),getLast()方法:获取指定index的元素,获取第一个元素,获取最后一个元素
这些比较简单不多说了
链表和数组的区别:
链表的元素操作都是指针的移动和头尾节点维护,在增删改方面的性能很高,但查的时间复杂度是O(n),数组则正好相反,在增删改方面的性能很差(涉及到数组的扩容以及元素的迁移),但查是寻址操作,性能非常高
单向链表和双向链表的区别
单向链表只有指向下一个元素的next指针,相对双向链表来说,指针维护简单,但遍历时只能从head开始,时间复杂度是O(n),双向链表有指向前后两个node的指针,指针维护较复杂,但遍历时可以通过head和tail两种方式查找,在get(i)和add(i,e)效率较单向链表高
欢迎关注”java面试工程师“公众号