Java數(shù)據(jù)結(jié)構(gòu)之LinkedList從鏈表到實(shí)現(xiàn)的方法是什么

今天小編給大家分享一下Java數(shù)據(jù)結(jié)構(gòu)之LinkedList從鏈表到實(shí)現(xiàn)的方法是什么的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來(lái)了解一下吧。

1.ArrayList的缺陷

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// ...
	// 默認(rèn)容量是10
	private static final int DEFAULT_CAPACITY = 10;
	//...
	// 數(shù)組：用來(lái)存儲(chǔ)元素
	transient Object[] elementData; // non-private to simplify nested class access
	// 有效元素個(gè)數(shù)
	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);
				}
		} 
		// ...
}

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

2.LinkedList

LinkedList概念

LinkedList的底層是雙向鏈表結(jié)構(gòu)，由于鏈表沒(méi)有將元素存儲(chǔ)在連續(xù)的空間中，元素存儲(chǔ)在單獨(dú)的節(jié)點(diǎn)中，然后通過(guò)引用將節(jié)點(diǎn)連接起來(lái)了，因此在在任意位置插入或者刪除元素時(shí)，不需要搬移元素，效率比較高。

在集合框架中，LinkedList也實(shí)現(xiàn)了List接口，具體如下：

說(shuō)明:

• LinkedList實(shí)現(xiàn)了List接口

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

• LinkedList沒(méi)有實(shí)現(xiàn)RandomAccess接口，因此LinkedList不支持隨機(jī)訪問(wèn)

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

LinkedList的使用

LinkedList的構(gòu)造

public static void main(String[] args) {
	// 構(gòu)造一個(gè)空的LinkedList
	List<Integer> list1 = new LinkedList<>();
	List<String> list2 = new java.util.ArrayList<>();
	list2.add("JavaSE");
	list2.add("JavaWeb");
	list2.add("JavaEE");
	// 使用ArrayList構(gòu)造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(): 刪除第一個(gè)元素，內(nèi)部調(diào)用的是removeFirst()
	list.removeFirst(); // removeFirst(): 刪除第一個(gè)元素
	list.removeLast(); // removeLast(): 刪除最后元素
	list.remove(1); // remove(index): 刪除index位置的元素
	System.out.println(list);
	// contains(elem): 檢測(cè)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): 從前往后找到第一個(gè)elem的位置
	System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 從后往前找第一個(gè)1的位置
	int elem = list.get(0); // get(index): 獲取指定位置元素
	list.set(0, 100); // set(index, elem): 將index位置的元素設(shè)置為elem
	System.out.println(list);
	// subList(from, to): 用list中[from, to)之間的元素構(gòu)造一個(gè)新的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.鏈表的概念及結(jié)構(gòu)

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：

• 單向或者雙向

• 帶頭或者不帶頭

• 循環(huán)或者非循環(huán)

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們重點(diǎn)掌握兩種:

• 無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

• 無(wú)頭雙向鏈表：在Java的集合框架庫(kù)中LinkedList底層實(shí)現(xiàn)就是無(wú)頭雙向循環(huán)鏈表。

4.ArrayList和LinkedList的區(qū)別

以上就是“Java數(shù)據(jù)結(jié)構(gòu)之LinkedList從鏈表到實(shí)現(xiàn)的方法是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。