1.前言

前面我們已經學習了陣列，陣列容量一經定義難以改變，同時刪除和插入元素需要移動大量的資料元素，效率較低。為此，引入了線性表中的鏈式儲存結構。鏈式儲存的資料元素不再具有連續的地址，同時可以根據需要隨時申請和釋放空間，更加靈活高效，但是喪失了隨機存取的能⼒。

2.定義

連結串列是一種物理儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是通過連結串列中的指標連結次序實現的。連結串列由一系列結點（連結串列中每一個元素稱為結點）組成，是一種遞迴的資料結構，結點可以在執行時動態生成。每個結點包括兩個部分：一個是儲存資料元素的資料域，另一個是儲存下一個結點地址的指標域。

在這裡插入圖片描述

3.模板設計

在這裡插入圖片描述
設計一個List介面，裡面寫一些通用的操作，供其他類實現，建立抽象類AbstractList，繼承List介面，實現一些通用的操作，比如判斷索引是否越界之類的常用操作。

List介面

public interface List<E> {
	static final int ELEMENT_NOT_FOUND = -1;
	/**
	 * 清除所有元素
	 */
	void clear();

	/**
	 * 元素的數量
	 * @return
	 */
	int size();

	/**
	 * 是否為空
	 * @return
	 */
	boolean isEmpty();

	/**
	 * 是否包含某個元素
	 * @param element
	 * @return
	 */
	boolean contains(E element);

	/**
	 * 新增元素到尾部
	 * @param element
	 */
	void add(E element);

	/**
	 * 獲取index位置的元素
	 * @param index
	 * @return
	 */
	E get(int index);

	/**
	 * 設定index位置的元素
	 * @param index
	 * @param element
	 * @return 原來的元素ֵ
	 */
	E set(int index, E element);

	/**
	 * 在index位置插入一個元素
	 * @param index
	 * @param element
	 */
	void add(int index, E element);

	/**
	 * 刪除index位置的元素
	 * @param index
	 * @return
	 */
	E remove(int index);

	/**
	 * 檢視元素的索引
	 * @param element
	 * @return
	 */
	int indexOf(E element);
}

抽象類AbstractList

public abstract class AbstractList<E> implements List<E>  {
	/**
	 * 元素的數量
	 */
	protected int size;
	/**
	 * 元素的數量
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 是否為空
	 * @return
	 */
	public boolean isEmpty() {
		 return size == 0;
	}

	/**
	 * 是否包含某個元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	/**
	 * 新增元素到尾部
	 * @param element
	 */
	public void add(E element) {
		add(size, element);
	}
	
	protected void outOfBounds(int index) {
		throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
	}
	
	protected void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfBounds(index);
		}
	}
	
	protected void rangeCheckForAdd(int index) {
		if (index < 0 || index > size) {
			outOfBounds(index);
		}
	}
}

4.單連結串列

4.1概念

顧名思義，單連結串列就是表示資料結點只有一個指標域。同時在單連結串列具體功能的實現中，為了讓程式碼更加精簡，統一所有節點的處理邏輯，可以在最前面增加一個虛擬的頭結點的輔助結點（不儲存資料）。同時，由於單連結串列的表頭元素中沒有前驅，所以建立一個指向表頭結點的指標，來儲存表頭結點的地址，稱為單連結串列的頭指標變數，即下圖中的first。

在這裡插入圖片描述

4.2基本操作

為了更好的實現下面的增刪改查操作，我們首先首先用一個靜態內部類來定義結點的抽象資料型別

	private static class Node<E> {
		E element;
		Node<E> next;
		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}

一個 Node 物件含有兩個範例變數，型別分別為 E（引數型別） 和 Node。其中next用來指向下一個連結串列，element用來儲存一個結點的資料。我們會在需要使用 Node 類的類中定義它並將它標記為 private，因為它不是為用例準備的。
然後建立一個first指標，指向頭結點。

private Node<E> first;

我們再寫一個node方法，用來獲取index位置對應的節點物件。首先檢查index值是否合理，如果合理，建立結點node指向頭結點。進行index次迴圈，每次讓結點node指向下一個結點。迴圈結束返回node。

/**
	 * 獲取index位置對應的節點物件
	 * @param index
	 * @return
	 */
	private Node<E> node(int index) {
		rangeCheck(index);
		
		Node<E> node = first.next;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}

同時重寫indexOf方法，用來獲取元素的位置，具體操作與上面類似

	@Override
	public int indexOf(E element) {
		if (element == null) {
			Node<E> node = first;
			for (int i = 0; i < size; i++) {
				if (node.element == null) return i;
				
				node = node.next;
			}
		} else {
			Node<E> node = first;
			for (int i = 0; i < size; i++) {
				if (element.equals(node.element)) return i;
				
				node = node.next;
			}
		}
		return ELEMENT_NOT_FOUND;
	}

4.2.1新增

在這裡插入圖片描述
如果要在index=0位置處插入元素，只需要讓虛擬頭結點的next指向新插入的結點，新插入結點的next指向原先0位置的結點。

如果在其他合理位置插入，只需要找到前一個結點，讓他的next指向新插入的結點，新插入結點的next指向原先位置的結點。

	@Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		
		Node<E> prev = index == 0 ? first : node(index - 1);
		prev.next = new Node<>(element, prev.next);

		size++;
	}

4.2.2刪除

在這裡插入圖片描述
如果刪除index=0位置處的結點，只需要讓虛擬頭結點的next指向index=1處的結點。在Java中，0位置指向1位置的next不用設定為null，曾經的結點物件沒有其他結點指向它，變成了"孤兒"，Java 的記憶體管理系統最終將回收它所佔用的記憶體。
在這裡插入圖片描述
如果刪除其他位置的結點，只需要找到待刪除元素的前一個結點，讓它指向待刪除元素的下一個結點。

	@Override
	public E remove(int index) {
		rangeCheck(index);
		
		Node<E> prev = index == 0 ? first : node(index - 1);
		Node<E> node = prev.next;
		prev.next = node.next;
			
		size--;
		return node.element;
	}

4.2.3修改

	@Override
	public E set(int index, E element) {
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

4.2.4查詢

@Override
	public E get(int index) {
		return node(index).element;
	}

5.雙向連結串列

5.1概念

在這裡插入圖片描述
看圖就知道，雙向連結串列與單連結串列的不同之處在於每個結點都增加了一個指向其前驅的指標域，其餘不變。同時呢，為了更好的操作，我們再新增一個first指標指向第一個結點，一個last指標指向最後一個結點。

當只有一個元素時
在這裡插入圖片描述

5.2基本操作

與單連結串列的操作類似，建立一個內部類Node

private static class Node<E> {
		E element;
		//前一結點地址
		Node<E> prev;
		//後一結點地址
		Node<E> next;
		public Node(Node<E> prev, E element, Node<E> next) {
			this.prev = prev;
			this.element = element;
			this.next = next;
		}
	}

然後建立first和last指標分別指向第一個結點和最後一個結點。

private Node<E> first;
private Node<E> last;

5.2.1新增

在這裡插入圖片描述
如果原先連結串列不為空，我們在連結串列最後新增元素。

我們先拿到原先的last，就命名為oldLast
讓新新增的node前驅結點指向oldLast，後驅結點指向null，然後讓last指向新新增的結點，
讓oldLast的next指向新新增的結點。

當連結串列為空時，新增第一個元素，即oldLast為null，只需要first=last
在這裡插入圖片描述
同樣連結串列有其他結點，我們在非首尾位置新增結點。

通過node(index)獲取到原先位置的結點，命名為next，
通過next.prev獲取原先node位置的前驅元素prev，讓新新增的node元素的前驅結點指向prev,後驅結點指向next，
通過next.prev = node指向新新增的元素，最後通過prev.next = node讓前驅元素指向新新增的元素node。

當新增在0位置的元素時，前面獲取的prev元素為null，只需要讓first指向新新增的node

@Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		
		if (index == size) { // 往最後面新增元素,可能沒有元素
			Node<E> oldLast = last;
			last = new Node<>(oldLast, element, null);
			if (oldLast == null) { // 這是連結串列新增的第一個元素
				first = last;
			} else {
				oldLast.next = last;
			}
		} else {
			Node<E> next = node(index); 
			Node<E> prev = next.prev; 
			Node<E> node = new Node<>(prev, element, next);
			next.prev = node;
			
			if (prev == null) { // index == 0
				first = node;
			} else {
				prev.next = node;
			}
		}
		
		size++;
	}

5.2.2刪除

在這裡插入圖片描述
當連結串列結構如上圖時，刪除最後一個元素

通過node(3)獲取要刪除的元素node,然後分別獲取到它的前驅結點prev和後繼結點next。
通過prev.next = next使前驅結點指向null
最後讓last指向prev

在這裡插入圖片描述
當刪除第一個元素時

通過node(0)獲取要刪除的元素node,然後分別獲取到它的前驅結點prev和後繼結點next。
發現prev=null,則直接first=next，指向待刪元素的下一個結點
最後next.prev = prev，其實這裡的prev==null

在這裡插入圖片描述
當刪除非首尾結點時

通過node(index)獲取要刪除的元素node,然後分別獲取到它的前驅結點prev和後繼結點next。
通過prev.next = next使前驅結點指向被刪元素的後一個結點
最後next.prev = prev，使被刪元素的後一個結點next指向被刪元素的前一個結點perv

@Override
	public E remove(int index) {
		rangeCheck(index);

		Node<E> node = node(index);
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		
		if (prev == null) { // index == 0
			first = next;
		} else {
			prev.next = next;
		}
		
		if (next == null) { // index == size - 1
			last = prev;
		} else {
			next.prev = prev;
		}
		
		size--;
		return node.element;
	}

5.2.3修改

@Override
	public E set(int index, E element) {
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

5.2.4查詢

	@Override
	public E get(int index) {
		return node(index).element;
	}

6.單向迴圈連結串列

6.1概念

為了某些操作實現方便，常將單連結串列中的最後一個結點的指標域指向頭結點，這樣就形成了首尾相連的結構，稱為迴圈單連結串列。

在這裡插入圖片描述
當只有一個結點時，結點的next指向自己，如下圖

6.2基本操作

先建立一個內部類Node

private static class Node<E> {
		E element;
		Node<E> next;
		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}

然後建立first指向第一個結點。

private Node<E> first;

6.2.1新增

在這裡插入圖片描述
當新增元素的位置為0時

我們先讓待插入結點newFirst的next指向原先0號位置的結點
如果此時的連結串列不為空，即size!=0,通過node(index-1)獲取最後一個結點。如果此時連結串列為空，最後一個結點就是它自己，讓它的next指向它自己。然後讓最後一個結點的next指向newFirst
此時的first還指向原先的第一個結點，最後將它的指標引向newFirst,即first = newFirst

在這裡插入圖片描述
當新增的元素位置不為0時

首先獲取待新增位置的前一個元素，比如新增新結點到三號位置，先通過node(index-1)獲取前一個元素prev
讓prev的next指向新插入的結點，讓新插入結點的next指向原先位置的元素

    @Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		
		if (index == 0) {
			Node<E> newFirst = new Node<>(element, first);
			// 拿到最後一個節點
			Node<E> last = (size == 0) ? newFirst : node(size - 1);
			last.next = newFirst;
			first = newFirst;
		} else {
			Node<E> prev = node(index - 1);
			prev.next = new Node<>(element, prev.next);
		}
		size++;
	}

6.2.2刪除

在這裡插入圖片描述
當刪除元素為第一個時

首先判斷這個連結串列是不是隻含這一個元素，如果只含這一個，只需要first=null,沒有指標引向它，它就會被回收，也就達到了刪除的目的。
如果還有其它的元素，首先將first指向原先一號位置的元素，即first = first.next，然後通過node(size - 1)獲取最後一個元素，使其指向原先的一號位置元素，即last.next = first

當刪除元素不是第一個時
1.通過node(index - 1)獲取待刪除元素的前一個結點prev，只需要讓前一個結點的next指向待刪除元素的的next，即prev.next = prev.next.next

@Override
	public E remove(int index) {
		rangeCheck(index);
		
		Node<E> node = first;
		if (index == 0) {
			if (size == 1) {
				first = null;
			} else {
				Node<E> last = node(size - 1);
				first = first.next;
				last.next = first;
			}
		} else {
			Node<E> prev = node(index - 1);
			node = prev.next;
			prev.next = node.next;
		}
		size--;
		return node.element;
	}

6.2.3修改

@Override
	public E set(int index, E element) {
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

6.2.4查詢

	/**
	 * 獲取index位置對應的節點物件
	 * @param index
	 * @return
	 */
	private Node<E> node(int index) {
		rangeCheck(index);
		
		Node<E> node = first;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		
		return node;
	}

@Override
	public E get(int index) {
		return node(index).element;
	}

7.雙向迴圈連結串列

7.1概念

在這裡插入圖片描述

雙向迴圈連結串列的節點不僅包含指向下一個節點的指標(next)，還包含指向前一個節點的指標(prev)，並且有迴圈連結串列的特點，最後一個結點的next指向第一個結點。

當連結串列只有一個元素時：
在這裡插入圖片描述

7.2基本操作

與單連結串列的操作類似，建立一個內部類Node

	private static class Node<E> {
		E element;
		Node<E> prev;
		Node<E> next;
		public Node(Node<E> prev, E element, Node<E> next) {
			this.prev = prev;
			this.element = element;
			this.next = next;
		}
	}

然後建立first和last指標分別指向第一個結點和最後一個結點。

private Node<E> first;
private Node<E> last;

7.2.1新增

在這裡插入圖片描述

@Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);

		// size == 0
		// index == 0
		if (index == size) { // 往最後面新增元素
			Node<E> oldLast = last;
			last = new Node<>(oldLast, element, first);
			if (oldLast == null) { // 這是連結串列新增的第一個元素
				first = last;
				first.next = first;
				first.prev = first;
			} else {
				oldLast.next = last;
				first.prev = last;
			}
		} else {
			Node<E> next = node(index); 
			Node<E> prev = next.prev; 
			Node<E> node = new Node<>(prev, element, next);
			next.prev = node;
			prev.next = node;
			
			if (next == first) { // index == 0
				first = node;
			}
		}
		
		size++;
	}

7.2.2刪除

在這裡插入圖片描述

public E remove(int index) {
		rangeCheck(index);

		Node<E> node = node(index);
		if (size == 1) {
			first = null;
			last = null;
		} else {
			Node<E> prev = node.prev;
			Node<E> next = node.next;
			prev.next = next;
			next.prev = prev;
			
			if (node == first) { // index == 0
				first = next;
			}
			
			if (node == last) { // index == size - 1
				last = prev;
			}
		}
		
		size--;
		return node.element;
	}

7.2.3修改

@Override
	public E set(int index, E element) {
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

7.2.4查詢

/**
	 * 獲取index位置對應的節點物件
	 * @param index
	 * @return
	 */
	private Node<E> node(int index) {
		rangeCheck(index);
		
		if (index < (size >> 1)) {
			Node<E> node = first;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
			return node;
		} else {
			Node<E> node = last;
			for (int i = size - 1; i > index; i--) {
				node = node.prev;
			}
			return node;
		}
	}

@Override
	public E get(int index) {
		return node(index).element;
	}

連結串列看這篇就夠了

連結串列

1.前言

2.定義

3.模板設計

4.單連結串列

4.1概念

4.2基本操作

4.2.1新增

4.2.2刪除

4.2.3修改

4.2.4查詢

5.雙向連結串列

5.1概念

5.2基本操作

5.2.1新增

5.2.2刪除

5.2.3修改

5.2.4查詢

6.單向迴圈連結串列

6.1概念

6.2基本操作

6.2.1新增

6.2.2刪除

6.2.3修改

6.2.4查詢

7.雙向迴圈連結串列

7.1概念

7.2基本操作

7.2.1新增

7.2.2刪除

7.2.3修改

7.2.4查詢