數(shù)據(jù)結構與算法—線性表
前言
通過前面數(shù)據(jù)結構與算法基礎知識我們知道了數(shù)據(jù)結構的一些概念和重要性，那么本章總結下線性表相關的內容。當然，我用自己的理解分享給大家。
其實說實話，可能很多人依然分不清線性表，順序表，和鏈表之間的區(qū)別和聯(lián)系！
- 線性表：邏輯結構， 就是對外暴露數(shù)據(jù)之間的關系，不關心底層如何實現(xiàn)，數(shù)據(jù)結構的邏輯結構大分類就是線性結構和非線性結構而順序表、鏈表都是一種線性表。
- 順序表、鏈表：物理結構，他是實現(xiàn)一個結構實際物理內存上的結構。比如順序表就是用數(shù)組實現(xiàn)。而鏈表主要用指針完成工作。不同的結構在不同的場景有不同的區(qū)別。
在Java中，大家都知道List接口，這就是邏輯結構，它封裝了一個線性關系的一系列方法，用于表示和維護線性關系。而具體的實現(xiàn)其實就是跟物理結構相關的內容。比如順序表的內容存儲使用數(shù)組的，然后一個get，set，add方法都要基于數(shù)組來完成,而鏈表是基于指針的，基于不同的物理結構要根據(jù)結構的特性維護數(shù)據(jù)的存儲和線性關系。
下面用一個圖來淺析物理結構中順利表和鏈表之間的區(qū)別。
線性表基本架構
對于一個線性表來說，不管它的具體實現(xiàn)如何，它們的方法函數(shù)名和實現(xiàn)效果應該一致（即使用方法相同、達成邏輯上的效果相同，差別的是實現(xiàn)方式可能針對不同的場景效率不同）。線性表的概念與Java的接口/抽象類有一些相似之處。最著名的例子就是List接口的ArrayList和LinkedList，List是一種邏輯上的結構，表示這種結構為線性表，而ArrayList和LinkedList更多的是一種物理結構（數(shù)組和鏈表）。
所以基于面向對象的編程思維，我們可以將線性表寫成一個接口，而具體實現(xiàn)的順序表和鏈表的類可以實現(xiàn)這個線性表的方法，以提高程序的可讀性。還有一點非常重要，初學數(shù)據(jù)結構與算法時實現(xiàn)的線性表都是固定類型（例如int），隨著知識的進步，我們應當采用泛型來實現(xiàn)更合理的方式。至于接口的具體設計如下：
public interface ListInterface<T> {
void init(int initialSize); // 初始化表
int length();
boolean isEmpty(); // 是否為空
int elemIndex(T t); // 找到編號
T getElem(int index); // 根據(jù)index獲取數(shù)據(jù)
void add(int index, T t) ; // 根據(jù)index插入數(shù)據(jù)
void delete(int index) ;
void add(T t) ; // 尾部插入
void set(int index, T t) ;
String toString(); // 轉成String輸出
}順序表
順序表是基于數(shù)組實現(xiàn)的，所有實現(xiàn)需要基于數(shù)組特性。對于順序表的結構應該有一個存儲數(shù)據(jù)的數(shù)組data和有效使用長度size.
這里為了簡單就不實現(xiàn)擴容、異常處理相關的操作。
下面著重講解一些初學者容易混淆的概念和方法實現(xiàn)。這里把順序表比作一隊坐在板凳上的人。
插入操作
(1)從后(最后一個有數(shù)據(jù)位)向前到index依次后移一位，騰出index位置的空間
(2)將待插入數(shù)據(jù)賦值到index位置上，完成插入操作
順序表很長，在靠前的地方如果插入效率比較低(插入時間復雜度為O(n))，如果頻繁的插入那么復雜度挺高的。
刪除操作
同理，刪除原理和插入類似，刪除index位置的操作就是從index開始(index+1)數(shù)據(jù)賦值到index位置，一直到size-1位置，具體可以看這張圖：
代碼實現(xiàn)
這里實現(xiàn)一個簡單的順序表：
public class SeqList<T> implements ListInterface<T> {
private T[] array;
private int size;
public SeqList() {
// 默認構造函數(shù)
init(10);
}
@Override
public void init(int initialSize) {
array = (T[]) new Object[initialSize];
size = 0;
}
@Override
public int length() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int elemIndex(T value) {
for (int i = 0; i < size; i++) {
if (array[i].equals(value)) {
return i;
}
}
return -1;
}
@Override
public T getElem(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
return array[index];
}
@Override
public void add(int index, T value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
if (size == array.length) {
// 如果數(shù)組已滿，擴展數(shù)組
resizeArray();
}
// 將index之后的元素后移一位
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = value;
size++;
}
@Override
public void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
// 將index之后的元素前移一位
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
size--;
}
@Override
public void add(T value) {
if (size == array.length) {
// 如果數(shù)組已滿，擴展數(shù)組
resizeArray();
}
array[size] = value;
size++;
}
@Override
public void set(int index, T value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
array[index] = value;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(array[i]);
if (i < size - 1) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
private void resizeArray() {
int newCapacity = (int) (array.length * 1.5);
T[] newArray = (T[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
}鏈表
在學習C/C++時，鏈表往往讓許多人感到復雜，其中一個主要原因可能是因為涉及到指針。盡管在Java中不直接使用指針，但我們仍然需要理解指針的原理和應用。鏈表與順序表（數(shù)組）不同，它的結構就像一條鏈一樣，將節(jié)點鏈接成一個線性結構。在鏈表中，每個節(jié)點都存在于不同的內存地址中，指針指向（鏈表存儲）了相鄰節(jié)點的地址，節(jié)點能夠通過這些指針找到下一個的節(jié)點形成一條鏈。
就物理存儲結構而言，地址之間的聯(lián)系是無法更改的，相鄰地址就是相鄰。但在鏈式存儲中，下一個地址是由上一個節(jié)點"主動記錄的"，因此可以進行更改。這就好比親兄弟從出生就是同姓兄弟，而在我們的成長過程中，最好的朋友可能會因為階段性的變化而有所不同！
舉個例子，就像西天取經的唐僧、悟空、八戒、沙和尚。他們本來沒有直接的聯(lián)系，但通過結拜為師徒兄弟，他們建立了聯(lián)系。如果你問悟空他的師父是誰，他會立刻想到唐僧，因為他們之間有五指山下的約定。
基本結構
對于線性表，我們只需要一個data數(shù)組和size就能表示基本信息。而對于鏈表，我們需要一個Node類節(jié)點(head頭節(jié)點)，和size分別表示存儲的節(jié)點數(shù)據(jù)和鏈表長度，這個節(jié)點有數(shù)據(jù)域和指針域。數(shù)據(jù)域就是存放真實的數(shù)據(jù)，而指針域就是存放下一個Node類節(jié)點的指針，其具體結構為：
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
this.next = null;
}
}帶頭結點鏈表VS不帶頭結點鏈表
有許多人可能會對帶頭結點和不帶頭結點鏈表的區(qū)別感到困惑，甚至不清楚什么是帶頭結點和不帶頭結點。我來為大家闡述一下：
帶頭結點：在帶頭結點的鏈表中，head指針始終指向一個節(jié)點，這個節(jié)點不存儲有效值，僅僅起到一個標識作用（有點像班主任帶著學生）。
不帶頭結點：在不帶頭結點的鏈表中，head指針始終指向第一個有效節(jié)點，這個節(jié)點存儲有效數(shù)值。
那么帶頭結點和不帶頭結點的鏈表有什么區(qū)別呢？
查找方面：在查找操作上，它們沒有太大區(qū)別，帶頭結點需要多進行一次查找。
插入方面：對于非第0個位置的插入操作，區(qū)別不大，但不帶頭結點的鏈表在插入第0號位置之后需要重新改變head頭指針的指向。
刪除方面：對于非第0個位置的刪除操作，區(qū)別不大，不帶頭結點的鏈表在刪除第0號位置之后需要重新改變head頭指針的指向。
- 頭部刪除（帶頭結點）：在帶頭結點的鏈表中，頭部刪除操作和普通刪除操作一樣。只需執(zhí)行 head.next = head.next.next，這樣head的next直接指向第二個元素，從而刪除了第一個元素。
- 頭部刪除（不帶頭結點）：不帶頭結點的鏈表的第一個節(jié)點（head）存儲有效數(shù)據(jù)。在不帶頭結點的鏈表中，刪除也很簡單，只需將head指向鏈表中的第二個節(jié)點即可，即：head = head.next。
總而言之：帶頭結點通過一個固定的頭可以使鏈表中任意一個節(jié)點都同等的插入、刪除。而不帶頭結點的鏈表在插入、刪除第0號位置時候需要特殊處理，最后還要改變head指向。兩者區(qū)別就是插入刪除首位(尤其插入)，個人建議以后在使用鏈表時候盡量用帶頭結點的鏈表避免不必要的麻煩。
帶頭指針VS帶尾指針
基本上是個鏈表都是要有頭指針的，那么頭尾指針是個啥呢？
頭指針： 其實頭指針就是鏈表中head節(jié)點，表示鏈表的頭，稱為為頭指針。
尾指針： 尾指針就是多一個tail節(jié)點的鏈表，尾指針的好處就是進行尾插入的時候可以直接插在尾指針的后面。
但是帶尾指針的單鏈表如果刪除尾的話效率不高，需要枚舉整個鏈表找到tail前面的那個節(jié)點進行刪除。
插入操作
add(int index,T value) 其中index為插入的編號位置，value為插入的數(shù)據(jù)，在帶頭結點的鏈表中插入那么操作流程為
- 找到對應index-1號節(jié)點成為pre。
- node.next=pre.next，將插入節(jié)點后面先與鏈表對應部分聯(lián)系起來。此時node.next和pre.next一致。
- pre.next=node 將node節(jié)點插入到鏈表中。
當然，很多時候鏈表需要插入在尾部，如果頻繁的插入在尾部每次枚舉到尾部的話效率可能比較低，可能會借助一個尾指針去實現(xiàn)尾部插入。
刪除操作
按照index移除(主要掌握)：delete(int index)
帶頭結點鏈表的通用方法(刪除尾也一樣)，找到該index的前一個節(jié)點pre，pre.next=pre.next.next
代碼實現(xiàn)
在這里我也實現(xiàn)一個單鏈表給大家作為參考使用：
public class LinkedList<T> implements ListInterface<T> {
private Node<T> head;
private int size;
public LinkedList() {
head = new Node<>(null); // 頭結點不存儲數(shù)據(jù)
size = 0;
}
@Override
public void init(int initialSize) {
head.next = null;
size = 0;
}
@Override
public int length() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int elemIndex(T value) {
Node<T> current = head.next;
int index = 0;
while (current != null) {
if (current.data.equals(value)) {
return index;
}
current = current.next;
index++;
}
return -1;
}
@Override
public T getElem(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
Node<T> current = head.next;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
@Override
public void add(int index, T value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
Node<T> newNode = new Node<>(value);
Node<T> pre = head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
newNode.next = pre.next;
pre.next = newNode;
size++;
}
@Override
public void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
Node<T> pre = head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
size--;
}
@Override
public void add(T value) {
add(size, value); // 在末尾添加元素
}
@Override
public void set(int index, T value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index is out of bounds.");
}
Node<T> current = head.next;
for (int i = 0; i < index; i++) {
current = current.next;
}
current.data = value;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
Node<T> current = head.next;
while (current != null) {
sb.append(current.data);
if (current.next != null) {
sb.append(", ");
}
current = current.next;
}
sb.append("]");
return sb.toString();
}
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
this.next = null;
}
}
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.init(10); // 初始化表
list.add(1);
list.add(2);
list.add(3);
list.add(1, 4); // 在索引1處插入值4
list.delete(2); // 刪除索引2處的值
System.out.println(list.toString()); // 打印表的內容
}
}總結
這里的只是簡單實現(xiàn)，實現(xiàn)基本方法。鏈表也只是單鏈表。完善程度還可以優(yōu)化。
單鏈表查詢速度較慢，因為他需要從頭遍歷，如果在尾部插入，可以考慮設計帶尾指針的鏈表。而順序表查詢速度雖然快但是插入很費時，實際應用根據(jù)需求選擇！
Java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優(yōu)化，并且JDK也做了大量優(yōu)化。所以大家不用造輪子，可以直接用，但是手寫順序表、單鏈表還是很有學習價值的。
