數據結構與演算法-基礎（二）單向鏈表

• 2021 年 9 月 12 日
• 筆記
• 數據結構與演算法

摘要

上期共同探究了下動態數組的添加、刪除等實現方法，想要再回顧一下的話，點擊我去再看看。接下來繼續探究數組。

其實，動態數組有個明顯的缺點，就是有可能造成記憶體空間的大量浪費。那麼有什麼辦法可以做到用多少就給多少呢？這時，咱接著探究一下鏈表，看看能不能解決這個疑問。

鏈表

話入正題，先說一下鏈表。鏈表是線性存儲的一種方式，每一個存放元素的記憶體空間不是相鄰的，需要用鎖鏈的方式去鏈接每一個存儲元素的記憶體空間。

正因為記憶體空間不用相鄰，所以在申請記憶體空間的時候，不需要多申請記憶體空間。

對比著具有連續的記憶體空間來存放元素，它在遍歷查詢上顯的沒有很高效方便，要根據不同的應用場景來選擇。

Array 的常用 API

按照慣例，先來一組常用的數組 API，看過上期動態數組，直接跳到下一節（數據結構）

/**
 * 清除所有元素
 */
public void clear()
/**
 * 元素的數量
 * @return
 */
public int size()
/**
 * 是否為空
 * @return
 */
public boolean isEmpty()
/**
 * 是否包含某個元素
 * @param element
 * @return
 */
public boolean contains(E element)
/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element)
/**
 * 獲取index位置的元素
 * @param index
 * @return
 */
public E get(int index)
/**
 * 設置index位置的元素
 * @param index
 * @param element
 * @return 原來的元素ֵ
 */
public E set(int index, E element)
/**
 * 在index位置插入一個元素
 * @param index
 * @param element
 */
public void add(int index, E element)
/**
 * 刪除index位置的元素
 * @param index
 * @return
 */
public E remove(int index)
/**
 * 刪除元素
 * @param element
 */
public void remove(E element)
/**
 * 查看元素的索引
 * @param element
 * @return
 */
public int indexOf(E element)

數據結構

根據鏈表的性質來看，存儲空間的位置不固定，需要類似鎖鏈的東西來鏈接。所以就用到指針來做鎖鏈，那麼每一個存儲空間就定義為節點。

除此之外，使用數組的時候，就需要確定一個頭節點，來遍歷尋找其他的元素，這裡就設置為first。

鎖鏈的本質，就是在節點中直接創建一個同類型的指針變數存放下一個節點的指針地址。

public class SingleLinkList<E> extends AbstractList<E>{

  // 頭部節點
  private Node<E> first;

  // 存放元素的節點，節點中存放下一個元素的位置
  private static class Node<E> {
    E element;
    Node<E> next;
    public Node(E element, Node<E> next) {
      this.element = element;
      this.next = next;
    }
}

實現方式

動態數組中一節中，咱先實現了可以直接處理的方法，比如元素的數量、是否為空。

然後根據在複雜方法中，先實現基礎再組合實現其他方法邏輯實現了一些組合方法，比如是否包含某個元素、添加元素到尾部、刪除元素。

/**
 * 元素數量
 */
protected int size = 0;

/**
 * 元素的數量
 * @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);
}

/**
 * 刪除元素
 * @param element
 */
public void remove(E element) {
  remove(indexOf(element));
}

protected void outOfBound(int index) {
  throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
}

/**
 * 判斷坐標是否越界
 * @param index
 */
protected void rangeCheck(int index) {
  if (index < 0 || index >= size) {
    outOfBound(index);
  }
}

protected void rangeCheckOfAdd(int index) {
  if (index < 0 || index > size) {
    outOfBound(index);
  }
}

鏈表實現方法

扯了這麼久，終於進入今天的正題，通過鏈表來實現基礎方法。

清除所有元素

在 JAVA 機制中，當一個記憶體空間沒有被其他對象（節點）指著，就會自動釋放。那麼清除所有元素就非常簡單, 直接讓頭節點為空即可，不要忘記把size設置為0.

	public void clear() {
		first = null;
		size = 0;
	}

獲取 index 位置的元素

鏈表的數據結構中看到，元素是存放到節點的element數據中，鏈表中的節點也不是相鄰的，所以就需要以first節點開始，通過遍歷方法來獲取。

這裡先實現便利獲取 index 位置的節點,在便利之前需要先判斷index是否越界。

	/**
	 * 獲取某個坐標的 node
	 * @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;
	}

獲取到節點，只需將節點中的元素取出即可

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

設置index位置的元素

上面已經實現了獲取index的節點，那麼只需要將這個節點的元素設置為新的元素就完成了。

/**
 * 設置index位置的元素
 * @param index
 * @param element
 * @return 原來的元素ֵ
 */
public E set(int index, E element) {
  Node<E> node = node(index);
  E old = node.element;
  node.element = element;
  return old;
}

在index位置插入一個位置

實現這個方法，需要考慮兩個不同的情況，1.數組中沒有一個元素和2.數組中已經有元素。

1中的情況就直接把元素放在first節點中，2中的情況就需要先獲取index-1位置的next節點，將這個next指向這個插入的節點，這個新插入的節點的next指向原來在index位置的節點，size不要忘記加1.

聽著有些繞，直接上程式碼

public void add(int index, E element) {
  // 需要先做判斷
  rangeCheckOfAdd(index);
  if (index == 0) {
    // 插入第一個，並不是說 first 就是 null。也是指向有值的
    first = new Node<>(element, first); 
  }
  else {
    Node<E> prev = node(index-1);
    Node<E> node = new Node<>(element, prev.next);
    prev.next = node;
  }
  size ++;
}

刪除index位置的元素

這個方法同樣需要考慮1.刪除index=0位置元素和2.刪除其他位置元素這兩種情況。

若是1中情況，只需要將first節點指向它的下一個節點即可。若是2中情況，就先獲取index-1位置節點，讓這個節點的next指向index位置的next。index位置沒有其他對象指引，就被直接刪除（釋放）。

public E remove(int index) {
  // 需要先判斷
  rangeCheck(index);
  Node<E> old = first;
  if (index == 0) {
    // 只是刪除對應的坐標，不是刪除所有
    first = first.next;
  }
  else {
    Node<E> prev = node(index -1);
    old = prev.next;
    prev.next = prev.next.next;
  }
  size --;
  return old.element;
}

查看元素的索引

元素要看一下是否為 null，如果為 null，則無法進行比較，就遍歷找第一個為 null 的元素。

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;
}

整體實現

鏈表實現就完成了，鏈表中沒有了索引的概念，取而代之的是類似指針的概念。在一些方法實現上和上一期動態數組一樣，這裡做了一些抽取，這裡有包括抽取的方法，程式碼有些長，想著還是保證程式碼的完整性，不能自己實現的時候，缺這塊缺那塊的。

實現鏈表中的方法（本期重點）

public class SingleLinkList<E> extends AbstractList<E>{

	// 私有變數
	private Node<E> first;
	
	private static class Node<E> {
		E element;
		Node<E> next;
		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}
	
	@Override
	public void clear() {
		first = null;
		size = 0;
	}

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

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

	@Override
	public void add(int index, E element) {
		// 需要先做判斷
		rangeCheckOfAdd(index);
		if (index == 0) {
			// 插入第一個，並不是說 first 就是 null。也是指向有值的
			first = new Node<>(element, first); 
		}
		else {
			Node<E> prev = node(index-1);
			Node<E> node = new Node<>(element, prev.next);
			prev.next = node;
		}
		size ++;
	}

	@Override
	public E remove(int index) {
		// 需要先判斷
		rangeCheck(index);
		Node<E> old = first;
		if (index == 0) {
			// 只是刪除對應的坐標，不是刪除所有
			first = first.next;
		}
		else {
			Node<E> prev = node(index -1);
			old = prev.next;
			prev.next = prev.next.next;
		}
		size --;
		return old.element;
	}

	@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;
	}
	
	/**
	 * 獲取某個坐標的 node
	 * @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 String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("size:").append(size).append(" ").append("[");
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				stringBuilder.append(",");
			}
			stringBuilder.append(node.element);
			node = node.next;
		}
		stringBuilder.append("]");
		return stringBuilder.toString();
	}
}

繼承公共實現方法

將通用的方法聲明為公共方法，自定義的方法就可以繼承這個公共類去實現。

public abstract class AbstractList<E> implements List<E> {

	/**
	 * 元素數量
	 */
	protected int size = 0;
	
	/**
	 * 元素的數量
	 * @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);
	}
	
	/**
	 * 刪除元素
	 * @param element
	 */
	public void remove(E element) {
		remove(indexOf(element));
	}
	
	protected void outOfBound(int index) {
		throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
	}
	
	/**
	 * 判斷坐標是否越界
	 * @param index
	 */
	protected void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfBound(index);
		}
	}
	
	protected void rangeCheckOfAdd(int index) {
		if (index < 0 || index > size) {
			outOfBound(index);
		}
	}
}

介面方法

這是 java 中的實現方式，將要實現的方法先做聲明

public interface List<E> {

	/**
	 * 默認標示
	 */
	static final int ELEMENT_NOT_FOUND = -1;
	
	/**
	 * 清除所有元素
	 */
	public void clear();

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

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

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

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	public void add(E element);

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

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

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

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

	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element);
}