近日，中央某采购中心就电脑产品采购例行向各PC供应商征求。在支持国产操作系统发展的事项上，各PC供应商产生了巨大分歧。通过投票，由在场的七家厂商表达对于预装国产操作系统的意见。联想、惠普、宏碁和华硕四家持反对意见拒收。另外三家厂商同方、海尔和戴尔虽然支持国产操作系统预装，但因为反对票已经过半，无法扭转局面。
本篇来自潇风寒月的，分享了从源码的角度来分析了LinkedList，一起来看看！希望大家喜欢。
本文将带大家深入LinkedList源码，分析其背后的实现原理，以便以后在合适的情况下进行使用。之前我所知道的LinkedList的知识：
因为LinkedList源码中很多地方是进行链表操作,所以先带大家复习一下链表的基础知识.以前用C语言实现的链表,大家可以去看一下,地址如下：
一个节点中包含数据和下一个节点的指针(注意,是下一个节点的指针,而不是下一个节点数据的指针),尾节点没有下一个节点,所以指向null.访问某个节点只能从头节点开始查找,然后依次往后遍历.
双向链表的每个节点包含以下数据:上一个节点的指针,自己的数据,下一个节点的指针.尾节点没有下一个节点,所以指向null.这样的结构,比如我拿到链表中间的一个节点,即可以往前遍历,也可以往后遍历.
AbstractSequentialList这个类提供了List的一个骨架实现接口，以尽量减少实现此接口所需的工作量由“顺序访问”数据存储（如链接列表）支持。对于随机访问数据（如数组），应使用AbstractList优先于此类。
实现了List接口,意味着LinkedList元素是有序的,可以重复的,可以有null元素的集合.
Deque是Queue的子接口,Queue是一种队列形式,而Deque是双向队列,它支持从两个端点方向检索和插入元素.
实现了Cloneable接口,标识着可以它可以被复制.注意,ArrayList里面的clone()复制其实是浅复制(不知道此概念的赶快去查资料,这知识点非常重要).
为什么是静态内部类?我觉得可能原因如下:普通内部类会有外部类的强引用,而静态内部类就没有.有外部类的强引用的话,很容易造成内存泄漏,写成静态内部类可以避免这种情况的发生.
这里为什么要存在一个变量尾节点?我感觉是为了方便,比如查找相应索引处元素+插入元素到最后.查找相应索引处元素时,先判断索引是在前半段还是在后半段,如果是在后半段,那么直接从尾节点出发,从后往前进行查找,这样速度更快.在插入元素到最后时,可以直接通过尾节点方便的进行插入.
因为ArrayList有这种构造方法public ArrayList(int initialCapacity),ArrayList提供这种构造方法的好处在于在知道需要多大的空间的情况下,可以按需构造列表,无需浪费多余的空间和不必要的生成新数组的操作.而LinkedList可以很轻松动态的增加元素(O(1)),所以没必要一开始就构造一个有很多元素的列表,到时需要的时候再按需加上去就行了.
将该新节点作为新的尾节点.如果是空链表插入第一个元素,那么头结点=尾节点=新节点;如果不是,那么将之前的尾节点指向新节点.
boolean add(E e)添加成功返回true,添加失败返回lse.我们在代码中没有看到有返回lse的情况啊,直接在代码中写了个返回true,什么判断条件都没有,啊??
仔细想想,分配内存空间不是必须是连续的,所以只要是还能给它分配空间,就不会添加失败.当空间不够分配时(内存溢出),会抛出OutOfMemory.
将该新节点作为新的头节点.如果是空链表插入第一个元素,那么头结点=尾节点=新节点;如果不是,那么将之前的头节点的prev指针指向新节点.
方法作用:添加元素到链表头部 这里的意思比拟压栈.和pop(出栈:移除链表第一个元素)相反.
哇,这里描述起来有点困难,,,,不知道我描述清楚没有.如果没看懂我的描述,看一下代码+再结合代码注释+画一下草图应该更清晰一些.
判断需要插入的index是否等于链表长度size,如果相等则插入到链表最后;如果不相等,则插入到链表中间,还需要找到index处节点succ,方便拿到该节点的前后节点信息.
将集合最后一个元素的next指针指向succ,将succ的prev指针指向集合的最后一个元素
大体思:其实就是将第一个节点移除并置空,然后将第二个节点作为头节点.思还常清晰的,主要是对细节的处理.
将x的前一个节点prev节点的next指针指向next,将x节点的后一个节点的prev指针指向prev节点.
如果为null,那么循环遍历链表,从头节点开始往后查找,找到第一个节点的数据值为null的,直接删除该节点.
如果非null,那么循环遍历链表,从头节点开始往后查找,找到第一个节点的数据值为o的,直接删除该节点.
这里的循环遍历链表的代码,我觉得还是比较通用的,从头节点开始,通过不断的将x赋值为下一个元素,直到遍历到为null的地方结束,这样就完美的遍历完了链表所有节点.
方法作用:获取第一个元素的同时删除第一个元素,当链表无节点时,不会报错. 这里的unlinkFirst()已分析过.
方法作用:获取指定索引处元素. 方法比较简单,就是通过node(index)找到index索引处节点,然后返回其数据值
添加元素非常快,如果是添加到头部和尾部的话更快,因为已经记录了头节点和尾节点,只需要链接一下就行了. 如果是添加到链表的中间部分的话,那么多一步操作,需要先找到添加索引处的元素(因为需要链接到这里),才能进行添加.
遍历的时候,采用forEach()进行遍历,这样可以在每次获取下一个元素时都非常轻松(next = next.next;). 然后如果是通过fori和get(i)的方式进行遍历的话,效率是极低的,每次get(i)都需要从最前面(或者最后面)开始往后查找i索引处的元素,效率很低.
本文来源于ipfs
网友评论 ()条 查看