一、LinkedList的概述
1. LinkedList是雙向鏈表實現(xiàn)的List
2. LinkedList是非線程安全的
3. LinkedList元素允許為null，允許重復元素
4. LinkedList是基于鏈表實現(xiàn)的，因此插入刪除效率高，查找效率低(雖然有一個加速動作)
5. LinkedList是基于鏈表實現(xiàn)的，因此不存在容量不足的問題，所以沒有擴容的方法
6. LinkedList還實現(xiàn)了棧和隊列的操作方法，因此也可以作為棧、隊列和雙端隊列來使用。推薦了解java培訓課程。
二、LinkedList的分析
2.1LinkedList的存儲結構
LinkedList是由雙鏈表的數(shù)據(jù)結構組成的
public class LinkedList{
// 元素個數(shù)
transient int size = 0;
/**
* 指向第一個節(jié)點的指針
* 不變性:
* 1. 如果first = null，則last=null
* 2. 如果first.prev == null，則first.item != null
*/ transient Node<E> first;
/**
* 指向最后一個節(jié)點的指針
* 不變性:
* 1. 如果first = null，則last = null
* 2. 如果last.next == null，則last.item != null
*/
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next; // 下一個Node的引用
Node<E> prev; // 上一個Node的引用
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
* 創(chuàng)建一個空list
* */
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
}
2.2添加元素
2.2.1從頭部添加
// 從頭插入
public void addFirst(E e) { linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null) // 當前List中沒有元素，size=0
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
2.2.2從尾部添加
public boolean add(E e) {
linkLast(e);
eturn true;
}
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)// 當前List中沒有元素，size=0
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
2.3.刪除節(jié)點
2.3.1從頭部刪除
// 移除首節(jié)點，并返回該節(jié)點的元素值
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 刪除首節(jié)點f
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null) // size=1
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
2.3.2從尾部移除
2.3.3根據(jù)索引移除
public E remove(int index) {
checkElementIndex(index);// 檢查索引index范圍
return unlink(node(index));
}
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) {// x為首節(jié)點
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {// x為尾節(jié)點
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
2.4獲取節(jié)點數(shù)據(jù)
2.4.1獲取頭部數(shù)據(jù)
// 獲取首節(jié)點的數(shù)據(jù)
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
2.4.2獲取尾部數(shù)據(jù)
// 獲取尾節(jié)點的數(shù)據(jù)
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
2.4.3根據(jù)索引獲取節(jié)點數(shù)據(jù)
// 獲取索引對應節(jié)點的數(shù)據(jù)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 類似折半查找
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;
}
}
三、總結:LinkedList和ArrayList的比較
1. 順序插入速度ArrayList會比較快，因為ArrayList是基于數(shù)組實現(xiàn)的，數(shù)組是事先new好的，只要往指定位置塞一個數(shù)據(jù)就好了
2. LinkedList則不同，每次順序插入的時候LinkedList將new一個對象出來，如果對象比較大，那么new的時間勢必會長一點，再加上一些引用賦值的操作，所以順序插入LinkedList必然慢于ArrayList
3. ArrayList的遍歷效率會比LinkedList的遍歷效率高一些
4. LinkedList做插入、刪除的時候，慢在尋址，快在只需要改變前后Node的引用地址
5. ArrayList做插入、刪除的時候，慢在數(shù)組元素的批量copy，快在尋址
(1) 如果確定插入、刪除的元素是在前半段，那么就使用LinkedList
(2) 如果確定插入、刪除的元素在比較靠后的位置，那么可以考慮使用ArrayList
(3) 如果不能確定插入、刪除是在哪兒呢?建議使用LinkedList，
·一來LinkedList整體插入、刪除的執(zhí)行效率比較穩(wěn)定，沒有ArrayList這種越往后越快的情況
·二來插入元素的時候，弄得不好ArrayList就要進行一次擴容，而ArrayList底層數(shù)組擴容是一個既消耗時間又消耗空間的操作
猜你喜歡
北京比較好的Java培訓機構
JavaEE
鴻蒙應用開發(fā)
集成電路應用開發(fā)
人工智能開發(fā)
AI+Linux云計算運維
Python+大數(shù)據(jù)開發(fā)
AI+設計
軟件測試
新媒體+短視頻
HTML&JS+前端
據(jù)學科列表頁右側.png)
.jpg)