一乔询、LinkedList基本原理
- 優(yōu)點(diǎn)：插入數(shù)據(jù)特別的快，不像ArrayList數(shù)組那樣子韵洋，挪動(dòng)大量的元素的竿刁，他是直接在鏈表里加一個(gè)節(jié)點(diǎn)就可以了
- 缺點(diǎn)黄锤，不太適合在隨機(jī)的位置，獲取某個(gè)隨機(jī)的位置的元素食拜，比如LinkedList.get(10)鸵熟，這種操作，性能就很低负甸，因?yàn)樗枰闅v這個(gè)鏈表流强，從頭開始遍歷這個(gè)鏈表，直到找到index = 10的這個(gè)元素為止
- LinkedList底層是基雙向鏈表呻待，而ArrayList底層基于數(shù)組打月。也就是底層結(jié)構(gòu)不同，才影響著他們的優(yōu)缺點(diǎn)
二带污、使用場景
- ArrayList：代表一個(gè)集合僵控，只要?jiǎng)e頻繁的往里面插入和灌入大量的元素就可以了，遍歷鱼冀，或者隨機(jī)查报破，都可以
- LinkedList：適合，頻繁的在list中插入和刪除某個(gè)元素,典型的就是用作隊(duì)列
三千绪、插入元素源碼
我們還是從基本的方法作為入口充易，還有一點(diǎn)就是我們一定要清楚，LinkedList主要用作隊(duì)列使用荸型，最后只關(guān)注一下他的核心源碼
代碼片段一盹靴、
- 首先要看下，最主要的是Node節(jié)點(diǎn)瑞妇，包含了當(dāng)前元素稿静，上一個(gè)節(jié)點(diǎn)、下一個(gè)節(jié)點(diǎn)
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方法
- addFirst方法其實(shí)和add方法一樣的
/**
* 這里默認(rèn)向鏈表的尾部插入
* 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) {
// 將當(dāng)前元素放入隊(duì)尾
linkLast(e);
return true;
}
代碼片段二改备、
/**
* Links e as last element.
*/
void linkLast(E e) {
// 定義一個(gè)l元素，指向last尾元素
final Node<E> l = last;
// 新增一個(gè)Node蔓倍，他的pre指針指向l悬钳，就是隊(duì)尾的那個(gè)元素，next指向null
final Node<E> newNode = new Node<>(l, e, null);
// 讓last指向新增的節(jié)點(diǎn)
last = newNode;
if (l == null)
// 如果l為空偶翅，說明這是一個(gè)新的鏈表默勾，新怎的節(jié)點(diǎn)也是頭結(jié)點(diǎn)
first = newNode;
else
// l.next的意思是原來的隊(duì)尾節(jié)點(diǎn)的next指向當(dāng)前新怎的節(jié)點(diǎn)
l.next = newNode;
// 鏈表長度+1
size++;
modCount++;
}
代碼片段三、 addFirst方法
/**
* 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) {
// 定義一個(gè)f變量聚谁，指向隊(duì)首
final Node<E> f = first;
// 新增一個(gè)新的節(jié)點(diǎn)母剥，pre指針指向Null ,next指向隊(duì)首元素
final Node<E> newNode = new Node<>(null, e, f);
// 將first指針指向新增節(jié)點(diǎn)
first = newNode;
if (f == null)
// 如果f為空，說明這是一個(gè)新的鏈表，新怎的節(jié)點(diǎn)也是頭結(jié)點(diǎn)
last = newNode;
else
// y原來首節(jié)點(diǎn)的prev指向當(dāng)前新增節(jié)點(diǎn)
f.prev = newNode;
size++;
modCount++;
}
代碼片段四媳搪、
在指定位置插入元素
/**
* 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) {
// 參數(shù)校驗(yàn)
checkPositionIndex(index);
// 如果是index==size铭段，則直接插入尾部
if (index == size)
linkLast(element);
else
// node方法如下
linkBefore(element, node(index));
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果index < size/2,說明index在隊(duì)列的前半部分
if (index < (size >> 1)) {
// 拿到第一個(gè)元素，然后從頭開始遍歷秦爆，
Node<E> x = first;
//不停的遍歷序愚，直到找到index的位置，然后返回x
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 這里其實(shí)就是從尾部開始遍歷
Node<E> 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<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
//創(chuàng)建一個(gè)新的節(jié)點(diǎn)等限，前一個(gè)節(jié)點(diǎn)是index節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)爸吮，next節(jié)點(diǎn)為succ節(jié)點(diǎn)
// 其實(shí)就是node方法遍歷的時(shí)候找到的那個(gè)index對(duì)應(yīng)的節(jié)點(diǎn)
final Node<E> newNode = new Node<>(pred, e, succ);
// 讓原來的節(jié)點(diǎn)的prev指向新創(chuàng)建的節(jié)點(diǎn)
succ.prev = newNode;
if (pred == null)
// pred如果為空的話，說明index對(duì)應(yīng)是頭結(jié)點(diǎn)
first = newNode;
else
// index節(jié)點(diǎn)原來對(duì)應(yīng)的next指向創(chuàng)建的新節(jié)點(diǎn)
pred.next = newNode;
size++;
modCount++;
}
四望门、獲取元素源碼
代碼片段一形娇、getFirst peek
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
//返回第一個(gè)元素，這里的first其實(shí)就是指向了鏈表的第一個(gè)元素
// 如果鏈表為空的話筹误，則拋出異常
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
// 和getFirst區(qū)別就是如果鏈表為空的話桐早，返回null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Returns the element at the specified position in this list.
* 對(duì)于LinkedList而言，讀取某個(gè)元素的時(shí)候厨剪，是通過node方法哄酝，遍歷鏈表，判斷index的位置祷膳，所以隨機(jī)讀取
* 是LinkedList的弱點(diǎn)
* @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;
}
五陶衅、刪除元素
代碼片段一、
/**
* 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();
}
/**
* 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() {
// 首先直晨。拿到鏈表的第一個(gè)元素
final Node<E> f = first;
// 如果隊(duì)頭的元素為null的話搀军，這個(gè)隊(duì)列也是空的
if (f == null)
throw new NoSuchElementException();
// 最后還是走到unlinkFirst，刪除的核心邏輯
return unlinkFirst(f);
}
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Unlinks non-null last node l.
* 這里和unlinkfirst幾乎一個(gè)套路
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 1.先拿到隊(duì)頭的元素
// 2. 然后拿到隊(duì)頭的next元素
// 3. 隊(duì)頭的元素=null勇皇，
// 4. 隊(duì)頭的next指針指向null
// 5.將first指針指向next
// 6. 通過2罩句、3、4敛摘、5步驟的止，其實(shí)就是將隊(duì)頭的元素釋放掉了
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
