从面试角度怎么分析LinkedList源码
本篇内容介绍了“从面试角度怎么分析LinkedList源码”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
在曲麻莱等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供做网站、成都网站制作 网站设计制作定制网站制作,公司网站建设,企业网站建设,高端网站设计,营销型网站,外贸营销网站建设,曲麻莱网站建设费用合理。
注：本系列文章中用到的jdk版本均为java8
LinkedList类图如下：
LinkedList底层是由双向链表实现的。链表好比火车，每节车厢包含了车厢和连接下一节车厢的连接点。而双向链表的每个节点不仅有指向下一个节点的指针，还有指向上一个节点的指针。
在LinkedList源码中有一个Node静态类，源码如下：
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
一个Node节点包含三个部分，分别是
item：数据
next：下一个节点的指针
prev：上一个节点的指针
LinkedList的主要变量如下：
// 集合中的元素数量 transient int size = 0; /** * 首节点的指针. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Nodefirst; /** * 尾结点的指针. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node last;
一、添加元素
LinkedList支持在任意节点位置添加元素，不仅提供了集合常用的add()方法，还提供了addFirst()和addLast()，add()方法默认调用addLast()方法，也就是默认是往链表尾部插入元素的。
add()方法源码：
public boolean add(E e) { linkLast(e); return true; }1.1 尾部插入元素
linkLast()源码如下：
void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } 我们来画张图演示一下如何给链表尾部插入元素：
假如链表中没有元素
对应源码中的if语句，如果没有元素则新增的这个节点为链表中唯一的一个元素，既是首节点，又是尾结点，前一个元素的指针和后一个元素的指针都是null。这里注意head节点不是第一个节点，head节点只是标识了这个链表的地址。
假如链表中有元素
对应源码中else语句。先将新增的元素当成Last节点，然后将原来的Last节点的next指向新节点。
else l.next = newNode;
一图胜前言，画个图是不是什么都明白了。
1.2 头部插入元素
linkFirst()源码如下：
private void linkFirst(E e) { final Node f = first; final Node newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } 还是根据上面的图来解读一下源码，先将第一个节点赋值给中间变量f，将新节点newNode赋值给first节点。如果链表没有元素，则Last节点和First节点都是新插入的节点newNode，否则，将原来的First节点的头指针指向新节点。
二、删除元素
LinkedList提供的删除方法有根据索引和元素删除，除此之外还提供删除第一个元素和最后一个元素的方法，这里我们只分析一下根据索引删除的方法。
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }checkElementIndex(index)方法就是用来判断传输的索引值是否合法，不合法则抛出数组越界异常。重点来看一下unlink(node(index))方法是如何删除元素的。
node(index)方法源码：
node(index)方法就是根据索引获取该索引位置的节点
Nodenode(int index) { // assert isElementIndex(index); // 如果指定下标 < 一半元素数量，则从首结点开始遍历 // 否则，从尾结点开始遍历 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
unlink(Node
E unlink(Nodex) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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++; return element; }
画张图分析一下删除是如何进行的：
鸿蒙官方战略合作共建——HarmonyOS技术社区
假设删除的是第一个元素：则它的prev==NULL，我们需要将他的后一个元素(图中的second)作为第一个元素
假设删除的是最后一个元素，则它的next==null，我们需要将他的前一个元素(图中的second)作为最后一个元素
如果是中间的任意元素，则需要将它的前一个元素的next指针指向它的后一个元素，同时将它的后一个元素的prev指针指向它的前一个元素。
“从面试角度怎么分析LinkedList源码”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
网站题目：从面试角度怎么分析LinkedList源码
文章转载：http://scjbc.cn/article/ggdoio.html
