LinkedList底层结构_network

2021年9月27日 2点热度 0条评论 来源: Az-Xm

LinkedList底层结构

说明

  • LinkedList底层实现了双向链表和双端队列特点
  • 可以添加任意元素(元素可以重复),包括null
  • 线程不安全,没有实现同步

操作机制:

  1. LInkedList底层维护了一个双向链表
  2. LinkedList中维护了两个属性first和last分别指向首节点和尾节点
  3. 每个节点(Node对象),里面又维护了prev、next、item(真正存放数据的地方)三个属性,其中通过prev指向前一个,next指向后一个,最终实现双向链表
  4. 所以LinkedList的元素的添加和删除,不是通过数组完成的,相对来说效率较高

first:指向第一个链表的第一个元素

last:指向最后一个链表的元素

初始化

这时候LinkedList属性 first last 都为null

执行了add方法

将新的节点加入到双向链表的最后

删除流程:

remove()方法:默认删除的是第一个节点

判空

真正执行删除的方法

将f指向的节点拿掉

修改方法

linkedList.set(1,999);

遍历方式

因为LinkedList实现了List接口,遍历方式

ArrayList和LinkedList比较

底层结构 增删的效率 改查效率
ArrayList 可变数据 较低,数组扩容 较高
LinkedList 双向链表 较高,通过链表追加 较低

如何选择ArrayList和LinkedList:

  1. 如果我们改查比较多用arraylist
  2. 如果我们增删操作多用LinkedList
  3. 一般来说在程序中,80%~90%都是查询,因此大部分情况下会选择ArrayList
  4. 在一个项目中,根据业务灵活选择,也可能这样,一个模块使用的是ArrayList,另一个模块是LinkedList
    原文作者:Az-Xm
    原文地址: https://www.cnblogs.com/IsMhhla/p/16200189.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。