目錄

前言

ArrayList的缺陷

鏈表?

鏈表的概念及結構

鏈表的種類

1.單向或雙向

2.帶頭或不帶頭

3.循環或不循環

LinkedList的使用?

什么是LinkedList

LinkedList的使用

LinkedList的構造

LinkedList的其他常用方法介紹

LinkedList的遍歷

ArrayList和LinkedList的區別

鏈表的缺陷?

---

?

前言

圖文詳解java鏈表，順序表和鏈表的比較，多種鏈表的形式，鏈表的使用，鏈表的方法

ArrayList的缺陷

ArrayList順序表

由于其底層是一段連續空間，當在ArrayList任意位置插入或者刪除元素時，就需要將后序元素整體往前或者往后 搬移，時間復雜度為O(n)，效率比較低，因此ArrayList不適合做任意位置插入和刪除比較多的場景。因此：java 集合中又引入了LinkedList，即鏈表結構。

鏈表?

鏈表的概念及結構

鏈表是一種物理存儲結構上非連續存儲結構，數據元素的邏輯順序是通過鏈表中的引用鏈接次序實現的 。

由上圖可見鏈表不同于數組，刪除和添加元素只需要把next的值改變即可

這樣時間復雜度只為O(1)

例如：?

?

注意:

? ? ? ? 1.從上圖可看出,鏈式結構在邏輯上是連續的,但是在物理上不一定連續

? ? ? ? 2.現實中的結點一般都是從堆上申請出來的

? ? ? ? 3.從堆上申請的空間,是按照一定的策略來分配的,兩次申請的空間可能連續,也可能不連續

鏈表的種類

1.單向或雙向

?

2.帶頭或不帶頭

3.循環或不循環

?

雖然有這么多的鏈表的結構，但是我們重點掌握兩種:

無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構，如 哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。

無頭雙向鏈表：在Java的集合框架庫中LinkedList底層實現就是無頭雙向循環鏈表。

LinkedList的使用?

什么是LinkedList

LinkedList的底層是雙向鏈表結構(鏈表后面介紹)，由于鏈表沒有將元素存儲在連續的空間中，元素存儲在單獨的節 點中，然后通過引用將節點連接起來了，因此在在任意位置插入或者刪除元素時，不需要搬移元素，效率比較高。

LinkedList的使用

LinkedList的構造

?

public static void main(String[] args) {// 構造一個空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");// 使用ArrayList構造LinkedListList<String> list3 = new LinkedList<>(list2);
}

LinkedList的其他常用方法介紹

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 刪除第一個元素，內部調用的是removeFirst()list.removeFirst(); // removeFirst(): 刪除第一個元素list.removeLast(); // removeLast(): 刪除最后元素list.remove(1); // remove(index): 刪除index位置的元素System.out.println(list);// contains(elem): 檢測elem元素是否存在，如果存在返回true，否則返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 從前往后找到第一個elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 從后往前找第一個1的位置int elem = list.get(0); // get(index): 獲取指定位置元素list.set(0, 100); // set(index, elem): 將index位置的元素設置為elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之間的元素構造一個新的LinkedList返回List<Integer> copy = list.subList(0, 3); System.out.println(list);System.out.println(copy);list.clear(); // 將list中元素清空System.out.println(list.size());
}

LinkedList的遍歷

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// foreach遍歷for (int e:list) {System.out.print(e + " ");}System.out.println();// 使用迭代器遍歷---正向遍歷ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();// 使用反向迭代器---反向遍歷ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();
}

ArrayList和LinkedList的區別

鏈表的缺陷?

我們知道鏈表的刪除和添加效率比順序表高得多，但是沒有取代順序表，這是因為鏈表也有缺陷

如上圖，鏈表對于訪問來說非常的乏力，順序表底層是數組，可以直接用下標來訪問，時間復雜度為O(1)，而鏈表則需要從頭開始訪問，一個個計數然后訪問到需要的元素，時間復雜度為O(n)?

所以順序表和鏈表都有其存在的意義，我們要視情況而選擇合適的來使用?