JAVA LinkedList源码分析
2022/3/10 1:14:49
本文主要是介绍JAVA LinkedList源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LinkedList底层结构
一、LinkedList 的全面说明
- LinkedList底层实现了双向链表和双端队列的贴点
- 可以添加任意元素(元素可以重复),包括null
- 线程不安全,没有实现同步
- 不涉及到多线程时使用
二、 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
- 因为这里是第一次添加元素到这个双向链表(linkLast集合)中,l指向的
-
让
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 | 双向链表 | 较高,通过链表追加 | 较低 |
- 如果我们改查的操作多,就选择ArrayList
- 如果我们增删的操作多,就选择LinkedList
- 一般来说,在程序中,80%~90%都是查询,因此大部分情况下都会选择ArrayList
- 在一个项目中,根据业务灵活选择,也可能这样,一个模块使用ArrayList一个模块使用LinkedList,也就是说根据业务来进行合理选择
注意:
- 这两个集合都是线程不安全的,建议在不涉及到多线程时使用
这篇关于JAVA LinkedList源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署