Java數據結構之LinkedList從鏈表到實現的方法是什么

今天小編給大家分享一下Java數據結構之LinkedList從鏈表到實現的方法是什么的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

1.ArrayList的缺陷

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// ...
	// 默認容量是10
	private static final int DEFAULT_CAPACITY = 10;
	//...
	// 數組：用來存儲元素
	transient Object[] elementData; // non-private to simplify nested class access
	// 有效元素個數
	private int size;
	public ArrayList(int initialCapacity) {
		if (initialCapacity > 0) {
			this.elementData = new Object[initialCapacity];
		} else if (initialCapacity == 0) {
			this.elementData = EMPTY_ELEMENTDATA;
				} else {
						throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
				}
		} 
		// ...
}

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

2.LinkedList

LinkedList概念

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

在集合框架中，LinkedList也實現了List接口，具體如下：

說明:

• LinkedList實現了List接口

• LinkedList的底層使用了雙向鏈表

• LinkedList沒有實現RandomAccess接口，因此LinkedList不支持隨機訪問

• LinkedList的任意位置插入和刪除元素時效率比較高，時間復雜度為O(1)

LinkedList的使用

LinkedList的構造

public static void main(String[] args) {
	// 構造一個空的LinkedList
	List<Integer> list1 = new LinkedList<>();
	List<String> list2 = new java.util.ArrayList<>();
	list2.add("JavaSE");
	list2.add("JavaWeb");
	list2.add("JavaEE");
	// 使用ArrayList構造LinkedList
	List<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);
	// 在起始位置插入0
	list.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，否則返回false
	if(!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位置的元素設置為elem
	System.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();
}

3.鏈表的概念及結構

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

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

• 單向或者雙向

• 帶頭或者不帶頭

• 循環或者非循環

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

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

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

4.ArrayList和LinkedList的區別

以上就是“Java數據結構之LinkedList從鏈表到實現的方法是什么”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。