建站
咨詢
售后
建站咨詢
新聞中心
本篇文章為大家展示了如何在Java中使用LinkedList，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。
網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了江北免費(fèi)建站歡迎大家使用！
一. 定義一個(gè)LinkedList
public static void main(String[] args) {
List stringList = new LinkedList<>();
List tempList = new ArrayList<>();
tempList.add("牛魔王");
tempList.add("蛟魔王");
tempList.add("鵬魔王");
tempList.add("獅駝王");
tempList.add("獼猴王");
tempList.add("禺賊王");
tempList.add("美猴王");
List stringList2 = new LinkedList<>(tempList);
} 上面代碼中采用了兩種方式來定義LinkedList，可以定義一個(gè)空集合，也可以傳遞已有的集合，將其轉(zhuǎn)化為L(zhǎng)inkedList。我們看一下源碼
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node last; /** * Constructs an empty list. */ public LinkedList() { } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection c) { this(); addAll(c); } }
LinkedList繼承了AbstractSequentialList類，實(shí)現(xiàn)了List接口，AbstractSequentialList中已經(jīng)實(shí)現(xiàn)了很多方法，如get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)，這些方法是我們集合操作時(shí)使用最多的，不過這些方法在LinkedList中都已經(jīng)被重寫了，而抽象方法在LinkedList中有了具體實(shí)現(xiàn)。因此我們回到LinkedList類
LinkedList類中定義了三個(gè)變量
size：集合的長(zhǎng)度
first：雙向鏈表頭部節(jié)點(diǎn)
last：雙向鏈表尾部節(jié)點(diǎn)
針對(duì)first變量和last變量，我們看到是Node類的實(shí)體，這是一個(gè)靜態(tài)內(nèi)部類，關(guān)于靜態(tài)內(nèi)部類的講解，我們?cè)趕tatic五大應(yīng)用場(chǎng)景一章已經(jīng)有說明
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
我們知道LinkedList是通過雙向鏈表實(shí)現(xiàn)的，而雙向鏈表就是通過Node類來體現(xiàn)的，類中通過item變量保存了當(dāng)前節(jié)點(diǎn)的值，通過next變量指向下一個(gè)節(jié)點(diǎn)，通過prev變量指向上一個(gè)節(jié)點(diǎn)。
二. LinkedList常用方法
1. get(int index)
我們知道隨機(jī)讀取元素不是LinkedList所擅長(zhǎng)的，讀取效率比起ArrayList也低得多，那么我來看一下為什么
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 返回一個(gè)指定索引的非空節(jié)點(diǎn).
*/
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;
}
} 從上述代碼中我們可以看到get(int index)方法是通過node(int index)來實(shí)現(xiàn)的，它的實(shí)現(xiàn)機(jī)制是：
比較傳入的索引參數(shù)index與集合長(zhǎng)度size/2，如果是index小，那么從第一個(gè)順序循環(huán)，直到找到為止；如果index大，那么從最后一個(gè)倒序循環(huán)，直到找到為止。也就是說越靠近中間的元素，調(diào)用get(int index方法遍歷的次數(shù)越多，效率也就越低，而且隨著集合的越來越大，get(int index)執(zhí)行性能也會(huì)指數(shù)級(jí)降低。因此在使用LinkedList的時(shí)候，我們不建議使用這種方式讀取數(shù)據(jù)，可以使用getFirst()，getLast()方法，將直接用到類中的first和last變量。
2. add(E e) 和 add(int index, E element)
大家都在說LinkedList插入、刪除操作效率比較高，以stringList.add(“豬八戒”)為例來看到底發(fā)生了什么？
在LinkedList中我們找到add(E e)方法的源碼
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 設(shè)置元素e為最后一個(gè)元素
*/
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
} 很好理解：
情況1：假如stringList為空，那么添加進(jìn)來的node就是first，也是last，這個(gè)node的prev和next都為null;
情況2：假如stringList不為空，那么添加進(jìn)來的node就是last，node的prev指向以前的最后一個(gè)元素，node的next為null；同時(shí)以前的最后一個(gè)元素的next.
而如果通過stringList.add(1, “豬八戒”)這種方式將元素添加到集合中呢？
//在指定位置添加一個(gè)元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 在一個(gè)非空節(jié)點(diǎn)前插入一個(gè)元素
*/
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++;
} 其實(shí)從代碼中看到和add(E e)的代碼實(shí)現(xiàn)沒有本質(zhì)區(qū)別，都是通過新建一個(gè)Node實(shí)體，同時(shí)指定其prev和next來實(shí)現(xiàn)，不同點(diǎn)在于需要調(diào)用node(int index)通過傳入的index來定位到要插入的位置，這個(gè)也是比較耗時(shí)的，參考上面的get(int index)方法。
其實(shí)看到這里，大家也都明白了。
LinkedList插入效率高是相對(duì)的，因?yàn)樗∪チ薃rrayList插入數(shù)據(jù)可能的數(shù)組擴(kuò)容和數(shù)據(jù)元素移動(dòng)時(shí)所造成的開銷，但數(shù)據(jù)擴(kuò)容和數(shù)據(jù)元素移動(dòng)卻并不是時(shí)時(shí)刻刻都在發(fā)生的。
3. remove(Object o) 和 remove(int index)
這里removeFirst()和removeLast()就不多說了，會(huì)用到類中定義的first和last變量，非常簡(jiǎn)單，我們看一下remove(Object o) 和 remove(int index)源碼
//刪除某個(gè)對(duì)象
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;
}
//刪除某個(gè)位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//刪除某節(jié)點(diǎn)，并將該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)（如果有）和下一個(gè)節(jié)點(diǎn)（如果有）關(guān)聯(lián)起來
E unlink(Node x) {
final E element = x.item;
final Node next = x.next;
final Node 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;
} 其實(shí)實(shí)現(xiàn)都非常簡(jiǎn)單，先找到要?jiǎng)h除的節(jié)點(diǎn)，remove(Object o)方法遍歷整個(gè)集合，通過 == 或 equals方法進(jìn)行判斷；remove(int index)通過node(index)方法。
4. LinkedList遍歷
我們主要列舉一下三種常用的遍歷方式，
普通for循環(huán)，增強(qiáng)for循環(huán)，Iterator迭代器
public static void main(String[] args) {
LinkedList list = getLinkedList();
//通過快速隨機(jī)訪問遍歷LinkedList
listByNormalFor(list);
//通過增強(qiáng)for循環(huán)遍歷LinkedList
listByStrengThenFor(list);
//通過快迭代器遍歷LinkedList
listByIterator(list);
}
/**
* 構(gòu)建一個(gè)LinkedList集合,包含元素50000個(gè)
* @return
*/
private static LinkedList getLinkedList() {
LinkedList list = new LinkedList();
for (int i = 0; i < 50000; i++){
list.add(i);
}
return list;
}
/**
* 通過快速隨機(jī)訪問遍歷LinkedList
*/
private static void listByNormalFor(LinkedList list) {
// 記錄開始時(shí)間
long start = System.currentTimeMillis();
int size = list.size();
for (int i = 0; i < size; i++) {
list.get(i);
}
// 記錄用時(shí)
long interval = System.currentTimeMillis() - start;
System.out.println("listByNormalFor：" + interval + " ms");
}
/**
* 通過增強(qiáng)for循環(huán)遍歷LinkedList
* @param list
*/
public static void listByStrengThenFor(LinkedList list){
// 記錄開始時(shí)間
long start = System.currentTimeMillis();
for (Integer i : list) { }
// 記錄用時(shí)
long interval = System.currentTimeMillis() - start;
System.out.println("listByStrengThenFor：" + interval + " ms");
}
/**
* 通過快迭代器遍歷LinkedList
*/
private static void listByIterator(LinkedList list) {
// 記錄開始時(shí)間
long start = System.currentTimeMillis();
for(Iterator iter = list.iterator(); iter.hasNext();) {
iter.next();
}
// 記錄用時(shí)
long interval = System.currentTimeMillis() - start;
System.out.println("listByIterator：" + interval + " ms");
} 執(zhí)行結(jié)果如下：
listByNormalFor：1067 ms
listByStrengThenFor：3 ms
listByIterator：2 ms
通過普通for循環(huán)隨機(jī)訪問的方式執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)大于迭代器訪問方式，這個(gè)我們可以理解，在前面的get(int index)方法中已經(jīng)有過說明，那么為什么增強(qiáng)for循環(huán)能做到迭代器遍歷差不多的效率？
通過反編譯工具后得到如下代碼
public static void listByStrengThenFor(LinkedListlist) { long start = System.currentTimeMillis(); Integer localInteger; for (Iterator localIterator = list.iterator(); localIterator.hasNext(); localInteger = (Integer)localIterator.next()) {} long interval = System.currentTimeMillis() - start; System.out.println("listByStrengThenFor：" + interval + " ms"); }
很明顯了，增強(qiáng)for循環(huán)遍歷時(shí)也調(diào)用了迭代器Iterator，不過多了一個(gè)賦值的過程。
還有類似于pollFirst()，pollLast()取值后刪除的方法也能達(dá)到部分的遍歷效果。
上述內(nèi)容就是如何在Java中使用LinkedList，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
分享文章：如何在Java中使用LinkedList
URL鏈接：http://fisionsoft.com.cn/article/jgsjcs.html
