Java集合之LinkedList源码分析

概述

LinkedLIst和ArrayLIst一样, 都实现了List接口, 但其内部的数据结构不同, LinkedList是基于链表实现的(从名字也能看出来), 随机访问效率要比ArrayList差. 它的插入和删除操作比ArrayList更加高效, 但还是要遍历部分链表的指针才能移动到下标所指的位置, 只有在链表两头的操作能省掉移动, 如add(), addFirest(), removeLast()等.

LinkedList源码分析

1.数据结构

LinkedList是基于链表结构实现的, 在类中定义了头尾指针. 其内部维护了一个双向链表

1535878389129f157ebfbc1 (345×108)

1535878418431f2dac6c169 (602×249)

2.构造方法

默认构造函数很简单, 啥也没有

1535878540677dfacaea908 (309×57)

将集合的元素添加的LinkedList中:

1535878563217d5f0f60fe6 (648×99)

153587860667110d0696b5e (640×97)

153587874655530446a266f (640×774)

3.存储

(1)add(E)在链表的末尾添加元素

15358788244691bbad061f6 (372×98)

153587893795670ccc4ab7b (615×341)

(2)add(int, E)在指定的位置插入元素

15358791311764d3a8a6204 (565×245)

1535879215090916b5a70eb (607×335)

153587936572872a732a46a (640×358)

(3)addAll(Collection)将集合添加到链表末尾, 该方法在构造方法中介绍了, 在此不再赘述

1535879498363ee8100ef41 (648×102)

(4)addAll(int, Collection)将集合添加到链表的指定位置, 该方法也在构造方法中介绍了

15358795591014c703890aa (773×77)

(5)addFirst(E)将元素添加到链表表头位置

1535879626519e0b278aafc (370×73)

15358796924873f0634e512 (614×314)

(6)addLast(E)将元素添加到表尾

1535879739068f81041c1b2 (333×73)

15358797492679ee53ac66f (640×330)

4.获取

1535879830511a02a75a317 (407×126)

15358798490516c7f56446a (522×167)

1535879863183ad5edd376e (577×162)

5.删除

删除方法不在给出源码, 基本大同小异. 有如下方法:

  1. remove(): 删除第一个元素并返回, 调用 removeFirst 方法
  2. remove(int): 删除链表指定位置的元素
  3. remove(Object): 从链表中删除首次出现的元素
  4. removeFirst(): 删除并返回第一个元素
  5. removeLast(): 删除并返回最后一个元素
  6. removeFirstOccurrence(Object): 从链表中删除第一次出现的指定元素
  7. removeLastOccurrence(Object): 从链表中删除最后一个出现的指定元素

LinkedList是一个功能强大的类, 可以当作List集合、队列和栈来使用.

------------

原文地址 https://hujingnb.com/archives/166

转载请保留原文连接: Java集合之LinkedList源码分析 | 烟草的香味

guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x