点击上方 Java后端，选择 设为星标
优质文章，及时送达
又通知我有空去聊聊技术。去的路上，我一直在想，今天会问些什么问题，集合？多线程？还是底层原理......真是越想越激动。心想昨天晚上复习了一晚，还怕这？想着想着就到了，尽管还是那个熟悉的面试官，但那张英俊的面孔折射出要把我面趴下的自信。他先开口了：咋眼圈都是黑的？这么重视？
我：对啊，昨天复习了一下基础知识，看了一下集合相关的内容。
面试官：好，不错，那今天就聊聊集合吧，你先讲讲 ArrayList 的原理和用法吧。这个接口用的比较多。
我心想，昨天把这个知识点整理了出来，现在终于派上用场了：ArrayList的使用及原理，面试必问的知识点，我把这篇博文的内容大侃一通。
还可以，看来没少下功夫，那咱们聊聊LinkedList吧
还是这个套路，
无论是在面试还是在平时应用中，都经常将LinkedList与ArrayList进行比较，因为他们虽然都是List主力军，但因其结构的不同，其应用场景也不太相同。
好，来吧
你说说LinkedList的继承关系吧
我：这个接口用的老熟了，LinkedList的继承关系是这样的：
面试官：行吧，有没有读过 LinkedList 的源码？
这基础中的基础，肯定看过啊
行，我不单独问了，你就从头把 LinkedList 的用法和原理给我捋一遍吧
好吧。。。调整一下心态，我开始了讲解：
LinkedList有两个构造函数：① 无参；②参数为集合。
举个栗子：
//默认创建一个LinkedList
LinkedList<String> l1 = new LinkedList<>();
//创建一个将其他类型集合中的数据化为己用的LinkedList
LinkedList<String> l2 = new LinkedList<>(new HashSet<>());transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
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;
}
}
LinkedList无参构造函数
public LinkedList() {}
LinkedList有参构造函数——入参类型为集合类
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* ......
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
怎么使用LinkedList？
get(int index)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}checkElementIndex()
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
node()
Node<E> node(int 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;
}
}
add(E e)
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}-
假如我们要向空LinkedList菜单集合中添加"小笼包"，则这个节点既是首节点，也是尾节点：
-
假如我们要向非空LinkedList菜单集合中添加“奶黄包”，则这个节点就是尾节点last，且下一个节点next为null。
-
加入通过add(1, “叉烧包”)这种方式将元素添加到LinkedList中，则需要找到这个下标代表的元素，并将这个元素以及该元素后的节点作为"叉烧包"节点的前后节点。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}从源码中我们可以看到，在进行添加操作之前，会将传入的索引进行范围检查后，再比较索引与当前LinkedList对象的size的大小，选择节点插入的位置。
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}如果索引index等于size，则说明该节点需要放在LinkedList对象的末尾。如果索引index不等于size，则需要调用node()方法找到索引对应的节点，与元素一起作为调用linkBefore()的参数：
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}可以看到，这个过程与add(int index)的没有本区区别，都是通过建立一个新的Node节点，并且指定其prev和next来实现，不同点在于需要调用node()来指定插入的位置，这里需要遍历链表才能获得，也是比较耗时的一个过程。
可以看到，在ArrayList中插入数据可能有的数组扩容和数据元素移动造成的开销，在LinkedList都不需要，所以相比ArrayList，LinkedList的插入效率比较高。除了add()之外，比较常用的添加方法还有addFirst()和addLast()。
remove(Object o)和remove(int index)
在上文我们介绍了LinkedList增加节点的方法，是通过链表上节点的prev和next变量来进行节点之间的连接。所以LinkedList移除节点也是在prev和next变量中来调节点与点之间的关系。
remove(Object o)
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}从源码中我们可以看出，LinkedList也可以添加值为null的节点，但其实除了要判断值为null之外，两个代码块的操作是一样的，需要将所有节点遍历一遍直到确认值为入参o是否在LinkedList链表中。如果找到了，则通过unlink()方法将值为o的节点移除链表。
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<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++;
return element;
}在unlink()方法中可以看到，在将该节点x的前节点的后指针指向x的后节点，将x的后节点的前指针指向x的前节点，并且将x的值设为null，便于GC回收（有兴趣的读者可以了解下JVM的垃圾回收机制）。
上面这段可能有点拗口，举个栗子，假如需要将LinkedList的菜单对象中的"叉烧包"移除：
那么需要将"小笼包"的next指针指向"奶黄包"，“奶黄包"的prev指针指向"小笼包”，并且将"叉烧包"的prev、item、next属性都设置为null。这样就可以完全移除"叉烧包"节点了。
remove(int index)
让我们再来看看依据索引来找到节点位置并移除节点的方法：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}在remove(int index)方法中可以看到我们方法体中出现的方法都是上文我们提到过的，所以在此也不做赘述，简单说明下此方法的原理：先对形参索引index进行检查范围的判断之后，先通过node()方法获取在LinkedList中此索引位置的节点，然后再通过unlink()方法对此节点进行移除处理。
其实相比ArrayList，LinkedList在对节点增加、移除方面的性能要好一点，但是因为可能在寻找节点的过程中需要遍历链表才能找到所需节点，所以在获取元素方面，ArrayList还是略胜一筹。关于移除的方法，常用的还有removeFirst()、removeLast()等方法。
LinkedList遍历
在此主要对LinkedList的三种常用的遍历方式进行介绍：
-
普通for循环
-
增强for循环
-
Iterator迭代器
普通for循环
public static void listForNormal(LinkedList<Integer> list){
// 记录开始时间
long start = System.currentTimeMillis();
int size = list.size();
for(int i=0;i<size;i++){
list.get(i);
}
//记录用时
long interval = System.currentTimeMillis() - start;
System.out.println("listForNormal："+interval+" ms");
}
增强for循环遍历LinkedList
public static void listByStrengThenFor(LinkedList<Integer> list){
// 记录开始时间
long start = System.currentTimeMillis();
for (Integer i : list) { }
// 记录用时
long interval = System.currentTimeMillis() - start;
System.out.println("listByStrengThenFor：" + interval + " ms");
}
迭代器遍历LinkedList
public static void listByIterator(LinkedList<Integer> list){
// 记录开始时间
long start = System.currentTimeMillis();
int size = list.size();
for(Iterator iter = list.iterator(); iter.hasNext();){
iter.next();
}
//记录用时
long interval = System.currentTimeMillis() - start;
System.out.println("listForNormal："+interval+" ms");
}listByNormalFor：1046 ms
listByStrengThenFor：6 ms
listByIterator：3 msprivate static void listByIterator(LinkedList<Integer> var0) {
long var1 = System.currentTimeMillis();
Iterator var3 = var0.iterator();
while(var3.hasNext()) {
var3.next();
}
long var5 = System.currentTimeMillis() - var1;
System.out.println("listByIterator:" + var5 + " ms");
}不错，看你讲的口干舌燥。今天的面试先到这里了，回家等消息吧。
我：好的。。说实话，捋的我头皮发麻。。
参考资料：
Java集合 LinkedList的原理及使用
可能会有看官觉得，了解ArrayList和LinkedList好像用处不大，不妨做下Leetcode 的这道题，它会让你感受ArrayList和LinkedList的底层结构不同，带来的效果也会不一样：面试题62. 圆圈中最后剩下的数字。https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
如果看到这里，说明你喜欢这篇文章，请转发、点赞
。同时标星（置顶）本公众号可以第一时间接受到博文推送。
本文分享自微信公众号 - Java后端（web_resource）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
相关文章
暂无评论...
致力于称为最好的程序员导航网站