从面试角度怎么分析LinkedList源码
导读:本文共2932字符,通常情况下阅读需要10分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 注:本系列文章中用到的jdk版本均为java8LinkedList类图如下:LinkedList底层是由双向链表实现的。链表好比火车,每节车厢包含了车厢和连接下一节车厢的连接点。而双向链表的每个节点不仅有指向下一个节点的指针,还有指向上一个节点的指针。在LinkedList源码中有一个Node静态类,源码如下:privatestaticclassNode<... ...
目录
(为您整理了一些要点),点击可以直达。注:本系列文章中用到的jdk版本均为java8
LinkedList类图如下:
LinkedList底层是由双向链表实现的。链表好比火车,每节车厢包含了车厢和连接下一节车厢的连接点。而双向链表的每个节点不仅有指向下一个节点的指针,还有指向上一个节点的指针。
在LinkedList源码中有一个Node静态类,源码如下:
privatestaticclassNode<E>{Eitem;Node<E>next;Node<E>prev;Node(Node<E>prev,Eelement,Node<E>next){this.item=element;this.next=next;this.prev=prev;}}
一个Node节点包含三个部分,分别是
item:数据
next:下一个节点的指针
prev:上一个节点的指针
LinkedList的主要变量如下:
//集合中的元素数量transientintsize=0;/***首节点的指针.*Invariant:(first==null&&last==null)||*(first.prev==null&&first.item!=null)*/transientNode<E>first;/***尾结点的指针.*Invariant:(first==null&&last==null)||*(last.next==null&&last.item!=null)*/transientNode<E>last;
一、添加元素
LinkedList支持在任意节点位置添加元素,不仅提供了集合常用的add()方法,还提供了addFirst()和addLast(),add()方法默认调用addLast()方法,也就是默认是往链表尾部插入元素的。
add()方法源码:
publicbooleanadd(Ee){linkLast(e);returntrue;}
1.1 尾部插入元素
linkLast()源码如下:
voidlinkLast(Ee){finalNode<E>l=last;finalNode<E>newNode=newNode<>(l,e,null);last=newNode;if(l==null)first=newNode;elsel.next=newNode;size++;modCount++;}
我们来画张图演示一下如何给链表尾部插入元素:
假如链表中没有元素
对应源码中的if语句,如果没有元素则新增的这个节点为链表中唯一的一个元素,既是首节点,又是尾结点,前一个元素的指针和后一个元素的指针都是null。这里注意head节点不是第一个节点,head节点只是标识了这个链表的地址。
假如链表中有元素
对应源码中else语句。先将新增的元素当成Last节点,然后将原来的Last节点的next指向新节点。
elsel.next=newNode;
一图胜前言,画个图是不是什么都明白了。
1.2 头部插入元素
linkFirst()源码如下:
privatevoidlinkFirst(Ee){finalNode<E>f=first;finalNode<E>newNode=newNode<>(null,e,f);first=newNode;if(f==null)last=newNode;elsef.prev=newNode;size++;modCount++;}
还是根据上面的图来解读一下源码,先将第一个节点赋值给中间变量f,将新节点newNode赋值给first节点。如果链表没有元素,则Last节点和First节点都是新插入的节点newNode,否则,将原来的First节点的头指针指向新节点。
二、删除元素
LinkedList提供的删除方法有根据索引和元素删除,除此之外还提供删除第一个元素和最后一个元素的方法,这里我们只分析一下根据索引删除的方法。
publicEremove(intindex){checkElementIndex(index);returnunlink(node(index));}
checkElementIndex(index)方法就是用来判断传输的索引值是否合法,不合法则抛出数组越界异常。重点来看一下unlink(node(index))方法是如何删除元素的。
node(index)方法源码:
node(index)方法就是根据索引获取该索引位置的节点
Node<E>node(intindex){//assertisElementIndex(index);//如果指定下标<一半元素数量,则从首结点开始遍历//否则,从尾结点开始遍历if(index<(size>>1)){Node<E>x=first;for(inti=0;i<index;i++)x=x.next;returnx;}else{Node<E>x=last;for(inti=size-1;i>index;i--)x=x.prev;returnx;}}
unlink(Node
Eunlink(Node<E>x){//assertx!=null;finalEelement=x.item;finalNode<E>next=x.next;finalNode<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++;returnelement;}
画张图分析一下删除是如何进行的:
鸿蒙官方战略合作共建——HarmonyOS技术社区
假设删除的是第一个元素:则它的prev==NULL,我们需要将他的后一个元素(图中的second)作为第一个元素
假设删除的是最后一个元素,则它的next==null,我们需要将他的前一个元素(图中的second)作为最后一个元素
如果是中间的任意元素,则需要将它的前一个元素的next指针指向它的后一个元素,同时将它的后一个元素的prev指针指向它的前一个元素。
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
从面试角度怎么分析LinkedList源码的详细内容,希望对您有所帮助,信息来源于网络。