Java 集合 - LinkedList

Java 集合 - LinkedList

技术杂谈小彩虹2021-08-23 1:05:44150A+A-

Java 集合- LinkedList 源码浅析

基本使用

新建一个Java类,以最基本的用法来走一遍 ArrayList 是如何运行的

package demo;

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("demo");
        String s = list.get(0);
        list.remove(0);
    }
}

总共分为4步

  1. 声明一个 LinkedList
  2. 添加一个元素
  3. 获取一个元素
  4. 删除一个元素
开始逐步分析源码
  • 声明一个 LinkedList

    进入 LinkedList 的构造函数

    public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
        
        transient int size = 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;
            }
        }
    }
    

    可以看到,对于 LinkedList 的构造函数,其实什么也没有做。

    不过需要关注 Node<E> 这个内部类,可以看到,LinkedList 的实际上是一个双向链表,对于其中的节点 node 分别存储了指向前向节点和后向节点的指针,其大致结构如下

    双向链表.png

  • 添加一个元素

    跟踪代码进入 add 函数,发现 add 函数如下所示

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    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++;
    }
    

    可以看到,添加一个元素为直接在链表末尾加上一个节点,并返回 true

    进入 linkLast(E e) 函数,可以看到主要分为3个步骤:

    • 记录当前最后一个节点
    • 声明一个新的节点并将当前最后一个节点赋值给新节点的 prev
    • 将当前的 last 指向新节点

    与 ArrayList 的 add 相同,这里也通过 modCount 记录了当前的操作次数

  • 获取一个元素

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    

    首先检查传入的 index 是否合法

    然后进入 node(index) 函数查找元素

    Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    

    可以看到,这里查找元素使用了折半查找的方法,如果小于一半从 fisrt 开始从前往后查找,如果大于则从 last 从后往前

  • 删除一个元素

    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
    
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }
    

    可以看到,remove 实际上是走到了 unlink 函数中,这个操作具体可以分为4个步骤:

    • 记录当前节点的 prev 和 next 节点
    • 如果 prev 为空则当前节点为首节点,将 fisrt 指向当前节点的下一个节点即可;否则将前节点的 next 指向当前节点的后一个节点
    • 如果 next 为空则当前节点为尾结点,将 last 指向当前节点的上一个节点即可;否则将当前节点的 prev 指向当前节点的前一个节点
    • 当前节点置空,size 长度减一

    最后返回删除的元素和增加操作数

    整个流程可以用下图总结

双向链表revome.png

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1
本网站由 提供CDN/云存储服务

联系我们