CSDN系列專欄：數(shù)據(jù)結(jié)構(gòu)與算法專欄
針對以前寫的數(shù)據(jù)結(jié)構(gòu)與算法系列重寫(針對文字描述、圖片、錯誤修復(fù))，改動會比較大，一直到更新完為止
前言
通過前面數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識我們知道了數(shù)據(jù)結(jié)構(gòu)的一些概念和重要性，那么本章總結(jié)下線性表相關(guān)的內(nèi)容。當然，我用自己的理解分享給大家。
其實說實話，可能很多人依然分不清線性表，順序表，和鏈表之間的區(qū)別和聯(lián)系！
- 線性表：邏輯結(jié)構(gòu)， 就是對外暴露數(shù)據(jù)之間的關(guān)系，不關(guān)心底層如何實現(xiàn)，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)大分類就是線性結(jié)構(gòu)和非線性結(jié)構(gòu)而順序表、鏈表都是一種線性表。
- 順序表、鏈表：物理結(jié)構(gòu)，他是實現(xiàn)一個結(jié)構(gòu)實際物理內(nèi)存上的結(jié)構(gòu)。比如順序表就是用數(shù)組實現(xiàn)。而鏈表主要用指針完成工作。不同的結(jié)構(gòu)在不同的場景有不同的區(qū)別。
在Java中，大家都知道List接口，這就是邏輯結(jié)構(gòu)，它封裝了一個線性關(guān)系的一系列方法，用于表示和維護線性關(guān)系。而具體的實現(xiàn)其實就是跟物理結(jié)構(gòu)相關(guān)的內(nèi)容。比如順序表的內(nèi)容存儲使用數(shù)組的，然后一個get，set，add方法都要基于數(shù)組來完成,而鏈表是基于指針的，基于不同的物理結(jié)構(gòu)要根據(jù)結(jié)構(gòu)的特性維護數(shù)據(jù)的存儲和線性關(guān)系。
下面用一個圖來淺析物理結(jié)構(gòu)中順利表和鏈表之間的區(qū)別。
線性表基本架構(gòu)
對于一個線性表來說，不管它的具體實現(xiàn)如何，它們的方法函數(shù)名和實現(xiàn)效果應(yīng)該一致（即使用方法相同、達成邏輯上的效果相同，差別的是實現(xiàn)方式可能針對不同的場景效率不同）。線性表的概念與Java的接口/抽象類有一些相似之處。最著名的例子就是List接口的ArrayList和LinkedList，List是一種邏輯上的結(jié)構(gòu)，表示這種結(jié)構(gòu)為線性表，而ArrayList和LinkedList更多的是一種物理結(jié)構(gòu)（數(shù)組和鏈表）。
所以基于面向?qū)ο蟮木幊趟季S，我們可以將線性表寫成一個接口，而具體實現(xiàn)的順序表和鏈表的類可以實現(xiàn)這個線性表的方法，以提高程序的可讀性。還有一點非常重要，初學(xué)數(shù)據(jù)結(jié)構(gòu)與算法時實現(xiàn)的線性表都是固定類型（例如int），隨著知識的進步，我們應(yīng)當采用泛型來實現(xiàn)更合理的方式。至于接口的具體設(shè)計如下：
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(); // 轉(zhuǎn)成String輸出
}
順序表
順序表是基于數(shù)組實現(xiàn)的，所有實現(xiàn)需要基于數(shù)組特性。對于順序表的結(jié)構(gòu)應(yīng)該有一個存儲數(shù)據(jù)的數(shù)組data和有效使用長度size.
這里為了簡單就不實現(xiàn)擴容、異常處理相關(guān)的操作。
下面著重講解一些初學(xué)者容易混淆的概念和方法實現(xiàn)。這里把順序表比作一隊坐在板凳上的人。
插入操作
add(int index,T value)
其中index為插入的編號位置，value為插入的數(shù)據(jù)，插入的流程為：
(1)從后(最后一個有數(shù)據(jù)位)向前到index依次后移一位，騰出index位置的空間
(2)將待插入數(shù)據(jù)賦值到index位置上，完成插入操作
順序表很長，在靠前的地方如果插入效率比較低(插入時間復(fù)雜度為O(n))，如果頻繁的插入那么復(fù)雜度挺高的。
刪除操作
同理，刪除原理和插入類似，刪除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() {
// 默認構(gòu)造函數(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;
}
}
鏈表
在學(xué)習(xí)C/C++時，鏈表往往讓許多人感到復(fù)雜，其中一個主要原因可能是因為涉及到指針。盡管在Java中不直接使用指針，但我們?nèi)匀恍枰斫庵羔樀脑砗蛻?yīng)用。鏈表與順序表（數(shù)組）不同，它的結(jié)構(gòu)就像一條鏈一樣，將節(jié)點鏈接成一個線性結(jié)構(gòu)。在鏈表中，每個節(jié)點都存在于不同的內(nèi)存地址中，指針指向（鏈表存儲）了相鄰節(jié)點的地址，節(jié)點能夠通過這些指針找到下一個的節(jié)點形成一條鏈。
就物理存儲結(jié)構(gòu)而言，地址之間的聯(lián)系是無法更改的，相鄰地址就是相鄰。但在鏈式存儲中，下一個地址是由上一個節(jié)點"主動記錄的"，因此可以進行更改。這就好比親兄弟從出生就是同姓兄弟，而在我們的成長過程中，最好的朋友可能會因為階段性的變化而有所不同！
舉個例子，就像西天取經(jīng)的唐僧、悟空、八戒、沙和尚。他們本來沒有直接的聯(lián)系，但通過結(jié)拜為師徒兄弟，他們建立了聯(lián)系。如果你問悟空他的師父是誰，他會立刻想到唐僧，因為他們之間有五指山下的約定。
基本結(jié)構(gòu)
對于線性表，我們只需要一個data數(shù)組和size就能表示基本信息。而對于鏈表，我們需要一個Node類節(jié)點(head頭節(jié)點)，和size分別表示存儲的節(jié)點數(shù)據(jù)和鏈表長度，這個節(jié)點有數(shù)據(jù)域和指針域。數(shù)據(jù)域就是存放真實的數(shù)據(jù)，而指針域就是存放下一個Node類節(jié)點的指針，其具體結(jié)構(gòu)為：
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
this.next = null;
}
}
帶頭結(jié)點鏈表VS不帶頭結(jié)點鏈表
有許多人可能會對帶頭結(jié)點和不帶頭結(jié)點鏈表的區(qū)別感到困惑，甚至不清楚什么是帶頭結(jié)點和不帶頭結(jié)點。我來為大家闡述一下：
帶頭結(jié)點：在帶頭結(jié)點的鏈表中，head指針始終指向一個節(jié)點，這個節(jié)點不存儲有效值，僅僅起到一個標識作用（有點像班主任帶著學(xué)生）。
不帶頭結(jié)點：在不帶頭結(jié)點的鏈表中，head指針始終指向第一個有效節(jié)點，這個節(jié)點存儲有效數(shù)值。
那么帶頭結(jié)點和不帶頭結(jié)點的鏈表有什么區(qū)別呢？
查找方面：在查找操作上，它們沒有太大區(qū)別，帶頭結(jié)點需要多進行一次查找。
插入方面：對于非第0個位置的插入操作，區(qū)別不大，但不帶頭結(jié)點的鏈表在插入第0號位置之后需要重新改變head頭指針的指向。
刪除方面：對于非第0個位置的刪除操作，區(qū)別不大，不帶頭結(jié)點的鏈表在刪除第0號位置之后需要重新改變head頭指針的指向。
- 頭部刪除（帶頭結(jié)點）：在帶頭結(jié)點的鏈表中，頭部刪除操作和普通刪除操作一樣。只需執(zhí)行
head.next = head.next.next，這樣head的next直接指向第二個元素，從而刪除了第一個元素。 - 頭部刪除（不帶頭結(jié)點）：不帶頭結(jié)點的鏈表的第一個節(jié)點（head）存儲有效數(shù)據(jù)。在不帶頭結(jié)點的鏈表中，刪除也很簡單，只需將head指向鏈表中的第二個節(jié)點即可，即：
head = head.next。
總而言之：帶頭結(jié)點通過一個固定的頭可以使鏈表中任意一個節(jié)點都同等的插入、刪除。而不帶頭結(jié)點的鏈表在插入、刪除第0號位置時候需要特殊處理，最后還要改變head指向。兩者區(qū)別就是插入刪除首位(尤其插入)，個人建議以后在使用鏈表時候盡量用帶頭結(jié)點的鏈表避免不必要的麻煩。
帶頭指針VS帶尾指針
基本上是個鏈表都是要有頭指針的，那么頭尾指針是個啥呢？
頭指針： 其實頭指針就是鏈表中head節(jié)點，表示鏈表的頭，稱為為頭指針。
**尾指針： **尾指針就是多一個tail節(jié)點的鏈表，尾指針的好處就是進行尾插入的時候可以直接插在尾指針的后面。
但是帶尾指針的單鏈表如果刪除尾的話效率不高，需要枚舉整個鏈表找到tail前面的那個節(jié)點進行刪除。
插入操作
add(int index,T value)
其中index為插入的編號位置，value為插入的數(shù)據(jù)，在帶頭結(jié)點的鏈表中插入那么操作流程為
- 找到對應(yīng)index-1號節(jié)點成為pre。
-
node.next=pre.next，將插入節(jié)點后面先與鏈表對應(yīng)部分聯(lián)系起來。此時node.next和pre.next一致。 -
pre.next=node將node節(jié)點插入到鏈表中。
當然，很多時候鏈表需要插入在尾部，如果頻繁的插入在尾部每次枚舉到尾部的話效率可能比較低，可能會借助一個尾指針去實現(xiàn)尾部插入。
刪除操作
按照index移除(主要掌握)：delete(int index)
帶頭結(jié)點鏈表的通用方法(刪除尾也一樣)，找到該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); // 頭結(jié)點不存儲數(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()); // 打印表的內(nèi)容
}
}
總結(jié)
這里的只是簡單實現(xiàn)，實現(xiàn)基本方法。鏈表也只是單鏈表。完善程度還可以優(yōu)化。
單鏈表查詢速度較慢，因為他需要從頭遍歷，如果在尾部插入，可以考慮設(shè)計帶尾指針的鏈表。而順序表查詢速度雖然快但是插入很費時，實際應(yīng)用根據(jù)需求選擇！
Java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優(yōu)化，并且JDK也做了大量優(yōu)化。所以大家不用造輪子，可以直接用，但是手寫順序表、單鏈表還是很有學(xué)習(xí)價值的。文章來源：http://www.zghlxwxcb.cn/news/detail-743756.html
CSDN專欄：數(shù)據(jù)結(jié)構(gòu)與算法專欄
開源倉庫：bigsai-algorithm倉庫 ，歡迎支持
如果覺得不錯 還請三連支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-743756.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法【02】—線性表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
