addAll©;

}

LinkedList有两个构造器，一个无参构造器，一个带参Collection c构造器。

当我们使用无参构造器创建LinkedList对象时，该对象只是初始化了first=null,last=null

当我们使用LinkedList(Collection c)创建对象时，内部调用了addAll(Collection c)方法，具体到addAll(Collection c)方法中讨论。

插入元素

====

常用方法

---

boolean add(E e)

/**

• Appends the specified element to the end of this list.

• 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) {

final Node l = last;

final Node newNode = new Node<>(l, e, null);

last = newNode;

if (l == null) // 我们知道当l为null时，即老的last为null,则说明对应的prev也是null,即链表是一个空链表。

first = newNode;// 若为空链表，则插入的节点就是链表的唯一节点，既是last，也是first

else

l.next = newNode;// 若为非空链表，则需要将老的last节点的next指向新的last节点

size++; // size是LinkedList的成员属性，初始值为0，加入一个元素后，size++为1

modCount++;// modCount变更可知该操作是集合结构化修改操做

}

从上面代码可以看出 add（E e）方法是在链表尾部插入一个节点。

下面画图演示在一个空链表中add（E e）

结合代码和图示：

第一步：先创建新节点e，e节点的prev指向了last，next指向了null

第二步：由于新节点e是插入到链表尾部，所以e节点是新的last节点

第三步：判断老的last节点是否为null，即插入e节点前，链表是否为空链表

若为空链表，则将first也指向e节点。

即当前链表只有一个节点，既是first 也是last

下面画图演示在一个非空链表中add（E e）

第一步：创建新节点e2,其中prev2指向last，next2指向null

第二步：由于e2节点是插入到链表尾部，所以e节点是新的last

第三步：判断老的last，即e节点是否为null，

若不为null,则链表不是空链表，则将e节点的next指向新的last，即e2

上述两种情况就是 linkLast（E e）的实现。

void add(int index, E element)

/**

• Inserts the specified element at the specified position in this list.

• Shifts the element currently at that position (if any) and any

• subsequent elements to the right (adds one to their indices).

• @param index index at which the specified element is to be inserted

• @param element element to be inserted

• @throws IndexOutOfBoundsException {@inheritDoc}

*/

public void add(int index, E element) {

checkPositionIndex(index);

if (index == size)

linkLast(element);

else

linkBefore(element, node(index));

}

private void checkPositionIndex(int index) {

if (!isPositionIndex(index))

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**

• Tells if the argument is the index of a valid position for an

• iterator or an add operation.

*/

private boolean isPositionIndex(int index) {

return index >= 0 && index <= size;

}

/**

• Returns the (non-null) Node at the specified element index.

*/

Node node(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;

}

}

/**

• Inserts element e before non-null Node succ.

*/

void linkBefore(E e, Node succ) {

// assert succ != null;

final Node pred = succ.prev;

final Node newNode = new Node<>(pred, e, succ);

succ.prev = newNode;

if (pred == null)

first = newNode;

else

pred.next = newNode;

size++;

modCount++;

}

add(int index, E element)方法是将element加到链表的index位置

首先链表结构不像数组（每个元素都有索引）一样，链表节点是没有索引的。所以这里的index并不是指元素的索引。

但是链表节点是有顺序性的，我们可以按照从first节点到last节点排序号，first节点就是序号0，last节点就是序号size-1 (size>=1时)。所以可以将index理解为序号。

那么链表元素是如何实现排序的呢？通过之前的图示我们知道  上一个节点的next指向下一个节点，下一个节点的prev指向上一个节点。

所以 first 的 index =0

则   first.next 的 index= 1

则   first.next.next 的 index = 2

…

则   last为 index = size -1

同样的，LinkedList是双向链表，具有双向性

所以  last 的 index = size -1

则     last.prev 的 index = size - 2

则     last.prev.prev 的 index = size - 3

…

则  first 的 index = 0

可以看出LinkedList底层双向链表查找对应index的元素，不像数组那样具有随机访问性，而是必须从first->last 或 last->first一个一个查询，所以LinkedList查询效率低。

而为了提升一点查询效率，Java大佬们使用了二分法查询。即：

若 index < size*0.5,则说明该索引在链表的前半部分，则可以从first->last方向查询

若index >= size*0.5,则说明该索引在链表的后半部分，则可以从last->first方向查询

具体代码实现如下

/**

• Returns the (non-null) Node at the specified element index.

*/

Node node(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;

}

}

以上解释了LinkedList的元素索引的实现。下面继续讨论add(int index, E element)方法

add(int index, E element)方法可以分为三种情况讨论

当index=0时，说明element将要被插入到链表头部，此时只关注element和first

当index=size时，说明element将要被插入到链表尾部，此时只关注element和last

当 0<index<size 时，说明element将要被插入到链表中间，此时需要关注element和前后两个节点

Java这里将 index = size 归为了 linkLast(element)，关于linkLast实现和add(E e)方法中实现一致，不再赘述。

将 index<size 归为了 linkBefore(element,node(index))

下面图示linkBefore(E e, Node succ)实现,其中e是将要被插入到index位置新节点的元素，succ是插入前，链表中index位置的节点

从add(e,0)图示可以看出：

第一步：创建newNode节点，newNode.prev指向了Node0.prev，newNode.next指向了Node0

第二步：解开Node0与前一个节点的连接，即Node0.prev改为指向newNode,将Node0作为newNode的下一个节点

第三步：由于Node0已经不是头节点了，所以first改为指向newNode

从add(e,1)图示可以看出：

第一步：创建newNode节点，newNode.prev指向了Node1.prev，newNode.next指向了Node1

第二步：解开Node1和前一个节点的连接，即Node1.prev改为指向newNode,将Node1作为newNode的下一个节点

第三步：由于Node1本来就不是头节点，所以还需要解开Node1上一个节点Node0的next连接约束，即将Node0.next指向newNode

boolean addAll(Collection<? extends E> c)

/**

• Appends all of the elements in the specified collection to the end of

• this list, in the order that they are returned by the specified

• collection’s iterator. The behavior of this operation is undefined if

• the specified collection is modified while the operation is in

• progress. (Note that this will occur if the specified collection is

• this list, and it’s nonempty.)

• @param c collection containing elements to be added to this list

• @return {@code true} if this list changed as a result of the call

• @throws NullPointerException if the specified collection is null

*/

public boolean addAll(Collection<? extends E> c) {

return addAll(size, c);

}

通过源码可以看到addAll(Collection c)内部是调用另一个重载方法addAll(size,c)

可以简单看出addAll(Collection c)是将Collection c中的元素存储到LinkedList的size位置，即当前链表的尾部。

具体Collection c中的元素按何种顺序存入，请看下面allAll(int index,Collection c)的实现。

boolean addAll(int index, Collection<? extends E> c)

/**

• Inserts all of the elements in the specified collection into this

• list, starting at the specified position. Shifts the element

• currently at that position (if any) and any subsequent elements to

• the right (increases their indices). The new elements will appear

• in the list in the order that they are returned by the

• specified collection’s iterator.

• @param index index at which to insert the first element

•          from the specified collection
  

• @param c collection containing elements to be added to this list

• @return {@code true} if this list changed as a result of the call

• @throws IndexOutOfBoundsException {@inheritDoc}

• @throws NullPointerException if the specified collection is null

*/

public boolean addAll(int index, Collection<? extends E> c) {

checkPositionIndex(index);

Object[] a = c.toArray();// 将c集合转为数组a

int numNew = a.length;

if (numNew == 0)// 如果a.length==0，表示集合c是个空集合

return false;// 返回false表示添加失败

Node pred, succ;// 定义两个节点 插入节点前面的节点pred，插入节点后面的节点succ

if (index == size) {// 如果index==size，说明将c集合元素插入到当前链表尾部

succ = null;// 由于插入节点是插入到尾部，所以succ不存在

pred = last;// 由于插入节点是插入到尾部，所以pred是last节点

} else {// 如果插入节点插入到当前链表中间或头部

succ = node(index);// 则需要获取插入位置index的节点作为 插入节点后面的节点

pred = succ.prev;// 将succ前面的节点作为 插入节点的前一个节点

}

for (Object o : a) {

@SuppressWarnings(“unchecked”) E e = (E) o;

Node newNode = new Node<>(pred, e, null);// 定义插入节点

if (pred == null) // 如果插入节点前面的节点是null，则说明插入到了链表头部

first = newNode;// 则插入节点是第一个节点，即为头节点first

else //如果插入节点前面的节点不是null，则说明插入位置不是头部

pred.next = newNode; 则插入节点的前一个节点的next改为指向插入的节点

pred = newNode; // 将插入节点作为最小的pred,而后循环此流程

}

if (succ == null) { // 如果插入节点是插入到尾部

last = pred;//所以最后一个插入节点就是尾节点last

} else {// 否则说明插入位置不是尾部，则最后一个插入节点的next要指向succ，且succ要指向最后一个插入节点

pred.next = succ;

succ.prev = pred;

}

size += numNew;// LinKedList的元素数量增加c集合元素个数

modCount++;// 集合已被结构化修改

return true;// 返回插入成功

}

addAll(int index, Collection c)的实现思路和add(int index,E e)差不多，都分为两种情况：

1.是在链表尾部插入c集合元素，即插入位置index=size

2.是在链表头部或中间插入c集合元素，即插入位置0=<index<size

只考虑主体逻辑，该方法的实现关键是定义了两个特殊节点pred,succ。

pred指代  新节点的插入位置的前面一个节点

succ指代  新节点的插入位置的后面一个节点

当情况1时，即插入在当前链表尾部时，即pred是当前链表的last节点，succ不存在

当情况2，插入到当前链表头部时，即pred是null，succ是first节点

当情况2，插入到当前链表中间时，即pred是node(index-1),succ是node(index)

而这里的新节点可以理解成一个双向链表段，它会按照c.toArray()的数组元素顺序组成一个双向链表段。

void addFirst(E e)

/**

• Inserts the specified element at the beginning of this list.

• @param e the element to add

*/

public void addFirst(E e) {

linkFirst(e);

}

/**

• Links e as first element.

*/

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++;

}

插入元素到链表头部，方法名友好。体现了LinkedList的底层是个双向不循环链表。

void addLast(E e)

/**

• Appends the specified element to the end of this list.

• This method is equivalent to {@link #add}.

• @param e the element to add

*/

public void addLast(E e) {

linkLast(e);

}

和add(E e)实现相同，只是方法名更加友好。体现了LinkedList的底层是个双向不循环链表。

特性证明

---

集合元素元素类型可以不一致，但是必须是引用类型。

该特性可以从节点Node(Node pre,E e,Node next)定义可知，其中e是集合元素，E是指e的类型，E是泛型，如果不指定泛型的话，那E就是默认的Object类型。而所有引用类型都可以向上转型为Object类型。

集合的容量是动态的

LinkedList的底层是双向链表。

它和ArrayList存储机制不一样，ArrayList底层是数组，数组的特点是使用前必须初始化，即数组使用前必须要确定长度。

ArrayList的动态容量实现是创建新数组来实现扩容。

而链表使用前不需要确定长度，或容量，链表的容量是真正的动态的。所以LinkedList的容量是动态的。

LinkedList集合元素是有序的

LinkedList的集合元素的有序性体现在

上一个节点的next指向下一个节点

下一个节点的prev指向上一个节点

LinkedList集合元素可以重复

LinkedList的add操作没有做添加元素的重复性检查操作，所以LinkedList的集合元素是可重复的。

获取元素

====

常用方法

---

E get(int index)

/**

• 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;

}

private void checkElementIndex(int index) {

if (!isElementIndex(index))

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**

• Tells if the argument is the index of an existing element.

*/

private boolean isElementIndex(int index) {

return index >= 0 && index < size;

}

/**

• Returns the (non-null) Node at the specified element index.

*/

Node node(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;

}

}

E get(int index)用于获取链表中index位置的节点的元素。

关于链表节点的索引，在前面已经讨论过了。链表节点不具备索引能力，体现在LinkedList上的索引能力是通过Node node(int index)方法实现的。

Node node(int index)方法，将first节点当成索引0，first.next节点当成索引1，first.next.next节点当成索引2，…，last节点当成索引size-1，

也可以将last节点当成索引size-1,last.prev节点当成size-2,last.prev.prev节点当成索引size-3,…,first节点当成索引0

Node node(int index)方法采用二分法查询，提升了查询效率。

E getFirst()

/**

• Returns the first element in this list.

• @return the first element in this list

• @throws NoSuchElementException if this list is empty

*/

public E getFirst() {

final Node f = first;

if (f == null)

throw new NoSuchElementException();

return f.item;

}

getFirst()方法用于获取链表first节点的元素。如果没有first节点，则抛出无此元素异常。

E getLast()

/**

• Returns the last element in this list.

• @return the last element in this list

• @throws NoSuchElementException if this list is empty

*/

public E getLast() {

final Node l = last;

if (l == null)

throw new NoSuchElementException();

return l.item;

}

getLast()方法用于获取链表last节点的元素。如果没有last节点，则抛出无此元素异常。

特性证明

---

LinkedList集合元素有索引

LinkedList底层是双向链表，双向链表节点本身没有索引概念，但是有顺序概念。

所以LinkedList将底层双向链表的first节点当成索引0节点，后面节点（前面节点.next）索引依次加1，直到last节点的索引为size-1。

需要注意地是：LinkedList根据索引访问集合元素，并不像ArrayList那样访问具有随机性。LinkedList访问集合元素只能从first->last方向一个个找，或者从last->first方向一个个找。

这更加证明了LinkedList的元素索引是伪索引。

修改元素

====

常用方法

---

E set(int index, E element)

/**

• Replaces the element at the specified position in this list with the

• specified element.

• @param index index of the element to replace

• @param element element to be stored at the specified position

• @return the element previously at the specified position

• @throws IndexOutOfBoundsException {@inheritDoc}

*/

public E set(int index, E element) {

checkElementIndex(index);

Node x = node(index);

E oldVal = x.item;

x.item = element;

return oldVal;

}

set(int index, E element)方法就是简单地将index索引处节点的元素改为element。

删除元素

====

常用方法

---

E remove()

/**

• Retrieves and removes the head (first element) of this list.

• @return the head of this list

• @throws NoSuchElementException if this list is empty

• @since 1.5

*/

public E remove() {

return removeFirst();

}

remove()方法用于删除LinkedList底层双向链表的first节点

内部实现是调用removeFirst()方法，具体实现请看removeFirst()

E remove(int index)

/**

• Removes the element at the specified position in this list. Shifts any

• subsequent elements to the left (subtracts one from their indices).

• Returns the element that was removed from the list.

• @param index the index of the element to be removed

• @return the element previously at the specified position

• @throws IndexOutOfBoundsException {@inheritDoc}

*/

public E remove(int index) {

checkElementIndex(index);

return unlink(node(index));

}

/**

• Unlinks non-null node x.

*/

E unlink(Node x) {// x指要被删除的节点

// assert x != null;

final E element = x.item; // 取出x节点的item元素，后面删除成功后，会作为remove方法的返回值

final Node next = x.next;// 获取x节点的后一个节点next

final Node prev = x.prev;// 获取x节点的前一个节点prev

if (prev == null) {//如果x的前一个节点是null，则说明x节点是first

first = next;// 那么删除x节点后，x的后一个节点next就是新的first

} else { //如果x的前一个节点不是null，则说明x节点不是first

prev.next = next;// 那么删除x后，x的前一个节点的next指向改为x的后一个节点

x.prev = null; // 将x节点的prev指向改为null，达到从链中彻底删除x节点的目的

}

if (next == null) {// 如果x的后一个节点是null，则说明x节点是last

last = prev;// 则删除x之后，x的前一个节点就是新的last

} else {// 如果x的后一个节点不是null，则说明x节点不是last

next.prev = prev; // 则删除x节点后，x的后一个节点的prev指向改为x的前一个节点

x.next = null; // 将x节点的next指向改为null，达到从链中彻底删除x节点的目的

}

x.item = null;// 此时x的prev,next都已经被设置为了null,需要将x.item也设置为null，那么x节点对象就会变成垃圾，等待被垃圾回收器回收

size–;// 链表元素个数减一

modCount++;// 集合对象发生结构化修改

return element;//返回之前保存的被删除节点的元素

}

remove(int index)方法的主体逻辑是unlink(node(index))。下面我们解析下unlink（Node x）方法实现：

unlink方法入参的节点x是需要被删除的节点。通过走读unlink代码发现，其思路是：由于要删除x节点，那么删除x节点后，x的前后两个节点就要建立联系。unlink的主要目的就是建立x前后两个节点之间的联系。

Java大佬们将x的前一个节点 定义为 x_prev, 将x的后一个节点 定义为 x_next。在建立x_prev和x_next节点联系前，我们需要搞清楚x_prev和x_next的具体场景

1. 当x节点是链表的唯一节点时，删除了x节点，那么链表就变成了空链表，即first=x_prev=null,last=x_next=null

2. 当x节点不是链表的唯一节点时，且x节点是头节点时，x_prev是null，删除x节点对x_prev无影响。而删除x节点后，x_next就是头节点。则需要删除x节点和x_next之间的联系,以及建立x_next和x_prev的联系，即x.next=null, x_next.prev=x_prev

3. 当x节点时尾节点时，x_next是null，删除x节点对x_next无影响。而删除x节点后，x_prev就是尾节点。则需要删除x节点和x_prev之间的联系,以及建立x_prev和x_next的联系，即x.prev=null, x_prev.next=x_next

4. 当x节点时中间节点时，则需要删除x节点和x_next,x_prev之间的联系，即将x.prev=null,x.next=null。然后需要建立x_next和x_prev的联系，即x_prev.next = x_next, x_next.prev = x_prev。

经过Java大佬的凝结提炼得到如下代码：

if (prev == null) {

first = next;

} else {

prev.next = next;

x.prev = null;

}

if (next == null) {

last = prev;

} else {

next.prev = prev;

x.next = null;

}

该代码的妙处是将上面情况3的修改凝练到了情况1，2中。上面这段代码

两个if体组合是情况1

两个else体组合就是情况4

一个if和另一个if的else组合就是情况2，3

说实话，这种代码思维 比 逻辑思维更加缜密。如果从逻辑思维考虑的话，很可能就漏掉情况1。

boolean remove(Object o)

/**

• Removes the first occurrence of the specified element from this list,

• if it is present. If this list does not contain the element, it is

• unchanged. More formally, removes the element with the lowest index

• {@code i} such that

• (o==null ? get(i)==null : o.equals(get(i)))

• (if such an element exists). Returns {@code true} if this list

• contained the specified element (or equivalently, if this list

• changed as a result of the call).

• @param o element to be removed from this list, if present

• @return {@code true} if this list contained the specified element

*/

public boolean remove(Object o) {

if (o == null) {

for (Node x = first; x != null; x = x.next) {

if (x.item == null) {

unlink(x);

return true;

}

}

} else {

for (Node x = first; x != null; x = x.next) {

if (o.equals(x.item)) {

unlink(x);

return true;

}

}

}

return false;

}

remove(Object o)分两种情况：

1. o == null,此时删除LinkedList底层双向链表的第一个元素为null的节点。

2. o != null ，此时底层会调用o的equals方法去比较底层链表的每个节点的元素，匹配到的第一个元素节点删除

所以remove(Object o) 期望o的运行时类型重写了equals方法

E removeFirst()

/**

• Removes and returns the first element from this list.

• @return the first element from this list

• @throws NoSuchElementException if this list is empty

*/

public E removeFirst() {

final Node f = first;

if (f == null)

throw new NoSuchElementException();

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024c （备注前端）

总结

技术学到手后，就要开始准备面试了，找工作的时候一定要好好准备简历，毕竟简历是找工作的敲门砖，还有就是要多做面试题，复习巩固。

CodeChina开源项目：【大厂前端面试题解析+核心总结学习笔记+真实项目实战+最新讲解视频】

if (o.equals(x.item)) {

unlink(x);

return true;

}

}

}

return false;

}

remove(Object o)分两种情况：

1. o == null,此时删除LinkedList底层双向链表的第一个元素为null的节点。

2. o != null ，此时底层会调用o的equals方法去比较底层链表的每个节点的元素，匹配到的第一个元素节点删除

所以remove(Object o) 期望o的运行时类型重写了equals方法

E removeFirst()

/**

• Removes and returns the first element from this list.

• @return the first element from this list

• @throws NoSuchElementException if this list is empty

*/

public E removeFirst() {

final Node f = first;

if (f == null)

throw new NoSuchElementException();

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
[外链图片转存中…(img-1lnkGBZs-1711967012377)]
[外链图片转存中…(img-aXRYfJKr-1711967012378)]
[外链图片转存中…(img-Q7lRZHEc-1711967012378)]
[外链图片转存中…(img-V4LkAUZt-1711967012379)]
[外链图片转存中…(img-ktStnQGU-1711967012379)]
[外链图片转存中…(img-ryOzX617-1711967012379)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024c （备注前端）
[外链图片转存中…(img-AV0YIZkm-1711967012379)]

总结

技术学到手后，就要开始准备面试了，找工作的时候一定要好好准备简历，毕竟简历是找工作的敲门砖，还有就是要多做面试题，复习巩固。

CodeChina开源项目：【大厂前端面试题解析+核心总结学习笔记+真实项目实战+最新讲解视频】