面试问你链表和LinkedList怎么答？

63 阅读 0 评论 42 点赞

我是靠谱客的博主留胡子煎饼，最近开发中收集的这篇文章主要介绍面试问你链表和LinkedList怎么答？，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

上篇文章说了下，数据和ArrayList，这篇文章我们说下在面试中有很大概率两者作为兄弟同时出现的LinkedList，希望大家看完这篇文章后能够有恍然大悟的感觉。

LinkedList底层是链表实现的，那么我们首先说下什么是链表。

和上篇文章的数组相比，链表要相对于更复杂一点，两者也是非常基础、常用，而且在面试中同时出现的概率也是很大的。

上篇文章我们说到，数据是需要连续的内存空间来存储的，而链表刚好与它相反，链表是不需要连续的内存空间的，它是通过将好多的零散的内存使用“指针”串联起来使用，如果数组和链表都想在计算机中申请大小为10M的内存，而计算机中只有10M的零散内存，那么数组就会申请内存失败，链表就会成功。

想对数组和ArrayList有多些了解的小伙伴可以看我的上篇文章：

[juejin.im/post/5c99c7…]

既然链表在内存中都是零散的块，那么我们是怎么称呼这些小块块呢？

我们把这些块叫做“结点”，为了把每个结点都串联起来，结点中不仅会存储数据，还有存储下一个结点的地址。

那我们怎么称呼记录下个结点地址的指针呢？

我们把他们叫做“后继指针next”。

链表中最特殊的是头结点和尾结点，顾名思义，也就是链表的第一个结点和最后一个结点，第一个结点保存着链表的基地址，通过这个结点，我们就能定位到它，最后一个结点的指针指向的是NULL，说明这个是链表的最后一个结点。

LinkedList中元素的所有操作都是在这样的数据结构上进行的，大家可以脑补下。

链表也可以进行插入、删除和查询操作。数组在进行插入和删除操作的时候，会进行数据的搬移操作，因为数据要保证他的内存空间是连续的，而链表则不需要，因为他的内存空间本就不是连续的，它只需要改变相邻结点的指针改变就够了，所以速度是非常快的。

但是查询就不会那么快了，链表查询数据要一个一个的遍历结点，直到找到相应的结点。

链表还有双向链表和循环链表，我们要说的LinkedList就是一个双向链表，上面说到的单向链表是只存了后一个结点的地址，而双向链表呢，是同时保存了前一个和后一个共两个元素的地址，所以就可以很方便的获取到一个结点的前后两个元素，而且我们也可以从前后两个方向来遍历。

接下来我们看下LinkedList的源码：

首先是继承关系：

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
复制代码

也是同时继承了Cloneable 和 Serializable ，Deque是一个双端队列，说明在LinkedList中同时也支持对队列的操作。

LinkedList的属性只有三个：

transient int size = 0;
transient Node<E> first;
transient Node<E> last;
复制代码

头结点，尾结点，链表中的元素数量，三者都是被 transient关键字修饰的，有小伙伴不理解这个关键字的，欢迎看我上上篇文章：面试问你java中的序列化怎么答？

Node是它的一个内部类，用来保存数据：


private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
复制代码

接下来，我们看下核心的 add方法，这次我还是在每行代码的上面添加上我的注释，帮助大家能够更好的理解。因为我的读者水平不一，所以必须要照顾到所有人：


/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
//保存 last 尾结点
final Node<E> l = last;
//将要保存的元素放到 新建一个结点中，
final Node<E> newNode = new Node<>(l, e, null);
// 这样这个新的节点就变成 了尾结点
last = newNode;
// 判断下如果这个尾结点为空，就说明这个链表是空的
//那么这个新的结点就是 首结点。
if (l == null)
first = newNode;
//如果不是空的，那么之前旧的尾结点的 next 保存的就是这个新结点
else
l.next = newNode;
size++;
modCount++;
}
复制代码

接下来，addAll 方法有两个重载函数，前一个是调用的后一个，所以我们只说一个：

public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//首先进行下标合理性检查，下面有这个方法
checkPositionIndex(index);
//将集合转换为 Object 数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//定义下标位置的前置结点和后继结点
Node<E> pred, succ;
if (index == size) {
//从尾部添加，前置结点是 之前的尾结点，后继结点为null
succ = null;
pred = last;
} else {
//从指定位置添加，后继结点是下标是index的结点；
//前置结点是下标位置的前一个结点
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//如果插入位置在头部
first = newNode;
else
//非空链表插入
pred.next = newNode;
pred = newNode;
//更新前置结点为最新的结点
}
if (succ == null) {
//如果是从尾部插入的，插入完成后重置尾结点
last = pred;
} else {
//如果不是尾部，那么把之前的数据和尾部连接起来
pred.next = succ;
succ.prev = pred;
}
//集合的原来数量+新集合的数量
size += numNew;
modCount++;
return true;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
复制代码

我们再说下根据下标来获取元素的方法 get

/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//元素的下标检查
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//如果下标位置靠近链表前半部分，从头开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
//如果下标位置靠近链表后半部分，从尾部开始遍历
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
复制代码