Java集合之LinkedList源码分析

概述

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

LinkedList源码分析

1.数据结构

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

Java集合之LinkedList源码分析
Java集合之LinkedList源码分析

2.构造方法

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

Java集合之LinkedList源码分析

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

Java集合之LinkedList源码分析
Java集合之LinkedList源码分析
Java集合之LinkedList源码分析

3.存储

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

Java集合之LinkedList源码分析
Java集合之LinkedList源码分析

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

Java集合之LinkedList源码分析
Java集合之LinkedList源码分析
Java集合之LinkedList源码分析

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

Java集合之LinkedList源码分析

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

Java集合之LinkedList源码分析

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

Java集合之LinkedList源码分析
Java集合之LinkedList源码分析

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

Java集合之LinkedList源码分析
Java集合之LinkedList源码分析

4.获取

Java集合之LinkedList源码分析
Java集合之LinkedList源码分析
Java集合之LinkedList源码分析

5.删除

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

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

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

上一篇:fastdfs安装


下一篇:[Luogu P1120]小木棍·加强版