对于要有扎实的 java 基础, 集合是必须掌握的, 而且精读这部分的源码很有用, 也很有必要. 而 LinkedList 是在 java.util 包下, 和 java.io,java.lang 都是比较常用, 而且比较简单. 看看它们的源码有助于锻炼我们看源码的感觉, 也了解一下大神们写代码的风格. 看这些源码的目的, 更多是为了增加阅读代码能力.
这里只写 LinkedList 的初始化和 add() 方法的源码分析, 先放一张 Collection 集合的分类简图:
LinkedList 采用双向链表存储方式
缺点: 遍历和随机访问元素效率低下.
优点: 插入, 删除元素效率比较高 (但是前提也是必须先低效率查询才可, 如果插入删除发生在头尾可以减少查询次数).
那开始吧!
- public class TestLinkedList {
- public static void main(String[] args) {
- LinkedList<Integer> list = new LinkedList<Integer>();
- list.add(1);
- list.add(2);
- list.add(3);
- }
- }
点进 LinkedList 发现只是一个构造函数, 有 3 个变量 (这里只放部分代码)
- public class LinkedList<E>
- extends AbstractSequentialList<E>
- implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- {
- transient int size = 0; // 默认长度 0
- transient Node<E> first; // 上一个元素
- transient Node<E> last; // 下一个元素
- public LinkedList() {
- }
- private static class Node<E> {
- E item;
- Node<E> next;
- Node<E> prev;
- Node(Node<E> prev, E element, Node<E> next) {
- this.item = element;
- this.next = next;
- this.prev = prev;
- }
- }
- }
Node 是 LinkedList 的一个内部类, Node 指的是双向链表的结点 (包括 3 部分, 中间数据 item, 左右两边的指针, 指向前 prev 后 next 的结点)
执行到 LinkedList<Integer> list = new LinkedList<Integer>(); 在内存中是这样的
我们再看看 add() 方法
- public boolean add(E e) {
- linkLast(e);
- return true;
- }
- /**
- * Links e as last element.// 将 e 链接为最后一个元素
- */
- void linkLast(E e) {
- final Node<E> l = last;
- final Node<E> newNode = new Node<>(l, e, null);
- last = newNode;
- if (l == null)
- first = newNode;
- else
- l.next = newNode;
- size++;
- modCount++;
- }
执行 add(1) 方法后, 将开始 last=null 赋给了一个变量 l, 这时候 new Node<>(l, e, null); 就是 new Node<>(null, 1, null), 在栈里创建了对象 (Node 结点).
到了 12 行 last = newNode;last 就不是 null 了, 是 0x2012, 也就指向了下一个结点
在往后面看 if 判断, 这是 l 是等于 null 的, 就把 first = newNode;first 就不是 null 了, 是 0x2012(newCode), 也就指向了上一个结点. 因为只有一个结点, 前后都是它自己.
继续 add,l=0x2012, 所以 new Node<>(l, e, null); 就是 new Node<>(0x2012, 2, null), 所以新增的结点就指向了上一个 0x2012.
然后再 last=newNode, 就是 0x3012. 它就不执行 0x2012 了.
这个时候 if 判断, l 已经不等空了, 执行 l.next=newNode.newNode 是 0x3012,l 是 0x2012,l.next 就是 0x2012 这个结点的 next 属性, 也是个 Node.
内存图是这样的:
最后再 add
来源: https://www.cnblogs.com/YancyL/p/12919561.html