Java教程

JAVA LinkedList源码分析

本文主要是介绍JAVA LinkedList源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

LinkedList底层结构

一、LinkedList 的全面说明

  1. LinkedList底层实现了双向链表和双端队列的贴点
  2. 可以添加任意元素(元素可以重复),包括null
  3. 线程不安全,没有实现同步
    • 不涉及到多线程时使用

二、 LinkedList 的底层操作机制

package com.hspedu.list_;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * @author DL5O
 * @version 1.0
 */
@SuppressWarnings("all")
public class LinkedListCRUD {

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);

        System.out.println("linkedList = " + linkedList);//[1, 2, 3]
        linkedList.remove();//删除第一个节点
//        linkedList.remove(1);//删除第二个节点
//        linkedList.remove(new Integer(1));//指定删除
        System.out.println(linkedList);//[2, 3]

        //修改某个节点对象
        linkedList.set(1,999);
        System.out.println(linkedList);//[2, 999]

        //得到某个节点对象
        Object o = linkedList.get(1);
        System.out.println(o);

        //因为linkedList实现了 list接口,所以它的遍历方式可以是增强for或者是迭代器
        Iterator iterator = linkedList.iterator();
        while(iterator.hasNext()){
            Object next = iterator.next();
            System.out.print(next+" ");
        }
        //2 999
        System.out.println();
        //源码阅读
        /*
            1.new 一个LinkedList后,调用它的无参构造器
                public LinkedList() {}
            2.这时linkedlist 的属性 first = null, last = null;
            3.执行
                public boolean add(E e) {
                    linkLast(e);
                    return true;
                }
            4.这时把插入的元素,插入到链表的尾部
                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++;
                }
         */


        /*
            删除remove的源码
            1.
            public E remove() {
                return removeFirst();
            }
            2.执行
            public E removeFirst() {
                final Node<E> f = first;
                if (f == null)
                    throw new NoSuchElementException();
                return unlinkFirst(f);
            }

            3.执行 unlinkLast,将 f 指向的双向链表的第一个结点拿掉(删除)
            private E unlinkLast(Node<E> l) {
                // assert l == last && l != null;
                final E element = l.item;
                final Node<E> prev = l.prev;
                l.item = null;
                l.prev = null; // help GC
                last = prev;
                if (prev == null)
                    first = null;
                else
                    prev.next = null;
                size--;
                modCount++;
                return element;
            }
         */

    }
}

源码分析

1.添加

第一次添加

  • 首先让节点 l 指向尾节点 last

    • last 默认为null
  • 创建一个名为newNode的新节点,new Node<>(前驱,元素值,后继)

    • 因为这里是第一次添加元素到这个双向链表(linkLast集合)中,l指向的last为空,新创建的节点,前驱为null
  • last指针指向新节点,即新节点就变成了尾节点

  • 如果 l==null,代表该链表现在没有元素,就让头节点也指向这个新节点,这时该链表中的第一个元素就诞生了

  • size ++,表长加加

第二次添加

2.删除

  • 删除链表的头节点,即首个节点
    • 如果 f == null,即该链表没有结点,为空链表,就抛出异常
  • 调用unlinkFirst方法将头节点的地址作为参数传进去,进行删除操作

  • 用一个只读泛型 element 来接受 头结点的 数据

  • next 为 头结点的下一个节点

  • 让 f(头结点)的数据域和next域置空(让GC回收)

  • 让后让头指针 指向 next(被删除的节点的下一个节点)

  • 如果next == null,链表为空,让last也指向null

    • 如果不为空,就让新的头结点(next)的prev设为null

三、ArrayList和LinkedList比较

底层结构 增删效率 改查效率
ArrayList 可变数组 较低,数组扩容 较高
LinkedList 双向链表 较高,通过链表追加 较低
  1. 如果我们改查的操作多,就选择ArrayList
  2. 如果我们增删的操作多,就选择LinkedList
  3. 一般来说,在程序中,80%~90%都是查询因此大部分情况下都会选择ArrayList
  4. 在一个项目中,根据业务灵活选择,也可能这样,一个模块使用ArrayList一个模块使用LinkedList,也就是说根据业务来进行合理选择

注意:

  • 这两个集合都是线程不安全的,建议在不涉及到多线程时使用
这篇关于JAVA LinkedList源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!