oqo28資訊網——每日最新資訊28at.com

前言

通過前面數據結構與算法基礎知識我們知道了數據結構的一些概念和重要性，那么本章總結下線性表相關的內容。當然，我用自己的理解分享給大家。oqo28資訊網——每日最新資訊28at.com

其實說實話，可能很多人依然分不清線性表，順序表，和鏈表之間的區別和聯系！oqo28資訊網——每日最新資訊28at.com

• 線性表：邏輯結構， 就是對外暴露數據之間的關系，不關心底層如何實現，數據結構的邏輯結構大分類就是線性結構和非線性結構而順序表、鏈表都是一種線性表。
• 順序表、鏈表：物理結構，他是實現一個結構實際物理內存上的結構。比如順序表就是用數組實現。而鏈表主要用指針完成工作。不同的結構在不同的場景有不同的區別。

在Java中，大家都知道List接口，這就是邏輯結構，它封裝了一個線性關系的一系列方法，用于表示和維護線性關系。而具體的實現其實就是跟物理結構相關的內容。比如順序表的內容存儲使用數組的，然后一個get，set，add方法都要基于數組來完成,而鏈表是基于指針的，基于不同的物理結構要根據結構的特性維護數據的存儲和線性關系。oqo28資訊網——每日最新資訊28at.com

下面用一個圖來淺析物理結構中順利表和鏈表之間的區別。oqo28資訊網——每日最新資訊28at.com

oqo28資訊網——每日最新資訊28at.com

線性表基本架構

對于一個線性表來說，不管它的具體實現如何，它們的方法函數名和實現效果應該一致（即使用方法相同、達成邏輯上的效果相同，差別的是實現方式可能針對不同的場景效率不同）。線性表的概念與Java的接口/抽象類有一些相似之處。最著名的例子就是List接口的ArrayList和LinkedList，List是一種邏輯上的結構，表示這種結構為線性表，而ArrayList和LinkedList更多的是一種物理結構（數組和鏈表）。oqo28資訊網——每日最新資訊28at.com

所以基于面向對象的編程思維，我們可以將線性表寫成一個接口，而具體實現的順序表和鏈表的類可以實現這個線性表的方法，以提高程序的可讀性。還有一點非常重要，初學數據結構與算法時實現的線性表都是固定類型（例如int），隨著知識的進步，我們應當采用泛型來實現更合理的方式。至于接口的具體設計如下：oqo28資訊網——每日最新資訊28at.com

public interface ListInterface<T> {    void init(int initialSize); // 初始化表    int length();    boolean isEmpty(); // 是否為空    int elemIndex(T t); // 找到編號    T getElem(int index); // 根據index獲取數據    void add(int index, T t) ; // 根據index插入數據    void delete(int index) ;    void add(T t) ; // 尾部插入    void set(int index, T t) ;    String toString(); // 轉成String輸出}

順序表

順序表是基于數組實現的，所有實現需要基于數組特性。對于順序表的結構應該有一個存儲數據的數組data和有效使用長度size.oqo28資訊網——每日最新資訊28at.com

這里為了簡單就不實現擴容、異常處理相關的操作。oqo28資訊網——每日最新資訊28at.com

下面著重講解一些初學者容易混淆的概念和方法實現。這里把順序表比作一隊坐在板凳上的人。oqo28資訊網——每日最新資訊28at.com

插入操作

(1)從后(最后一個有數據位)向前到index依次后移一位，騰出index位置的空間oqo28資訊網——每日最新資訊28at.com

(2)將待插入數據賦值到index位置上，完成插入操作oqo28資訊網——每日最新資訊28at.com

oqo28資訊網——每日最新資訊28at.com

順序表很長，在靠前的地方如果插入效率比較低(插入時間復雜度為O(n))，如果頻繁的插入那么復雜度挺高的。oqo28資訊網——每日最新資訊28at.com

刪除操作

同理，刪除原理和插入類似，刪除index位置的操作就是從index開始(index+1)數據賦值到index位置，一直到size-1位置，具體可以看這張圖：oqo28資訊網——每日最新資訊28at.com

oqo28資訊網——每日最新資訊28at.com

代碼實現

這里實現一個簡單的順序表：oqo28資訊網——每日最新資訊28at.com

public class SeqList<T> implements ListInterface<T> {    private T[] array;    private int size;    public SeqList() {        // 默認構造函數         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) {            // 如果數組已滿，擴展數組            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) {            // 如果數組已滿，擴展數組            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中不直接使用指針，但我們仍然需要理解指針的原理和應用。鏈表與順序表（數組）不同，它的結構就像一條鏈一樣，將節點鏈接成一個線性結構。在鏈表中，每個節點都存在于不同的內存地址中，指針指向（鏈表存儲）了相鄰節點的地址，節點能夠通過這些指針找到下一個的節點形成一條鏈。oqo28資訊網——每日最新資訊28at.com

就物理存儲結構而言，地址之間的聯系是無法更改的，相鄰地址就是相鄰。但在鏈式存儲中，下一個地址是由上一個節點"主動記錄的"，因此可以進行更改。這就好比親兄弟從出生就是同姓兄弟，而在我們的成長過程中，最好的朋友可能會因為階段性的變化而有所不同！oqo28資訊網——每日最新資訊28at.com

舉個例子，就像西天取經的唐僧、悟空、八戒、沙和尚。他們本來沒有直接的聯系，但通過結拜為師徒兄弟，他們建立了聯系。如果你問悟空他的師父是誰，他會立刻想到唐僧，因為他們之間有五指山下的約定。oqo28資訊網——每日最新資訊28at.com

oqo28資訊網——每日最新資訊28at.com

基本結構

對于線性表，我們只需要一個data數組和size就能表示基本信息。而對于鏈表，我們需要一個Node類節點(head頭節點)，和size分別表示存儲的節點數據和鏈表長度，這個節點有數據域和指針域。數據域就是存放真實的數據，而指針域就是存放下一個Node類節點的指針，其具體結構為：oqo28資訊網——每日最新資訊28at.com

private static class Node<T> {   T data;   Node<T> next;   Node(T data) {     this.data = data;     this.next = null;   } }

帶頭結點鏈表VS不帶頭結點鏈表

有許多人可能會對帶頭結點和不帶頭結點鏈表的區別感到困惑，甚至不清楚什么是帶頭結點和不帶頭結點。我來為大家闡述一下：oqo28資訊網——每日最新資訊28at.com

帶頭結點：在帶頭結點的鏈表中，head指針始終指向一個節點，這個節點不存儲有效值，僅僅起到一個標識作用（有點像班主任帶著學生）。oqo28資訊網——每日最新資訊28at.com

不帶頭結點：在不帶頭結點的鏈表中，head指針始終指向第一個有效節點，這個節點存儲有效數值。oqo28資訊網——每日最新資訊28at.com

那么帶頭結點和不帶頭結點的鏈表有什么區別呢？oqo28資訊網——每日最新資訊28at.com

查找方面：在查找操作上，它們沒有太大區別，帶頭結點需要多進行一次查找。oqo28資訊網——每日最新資訊28at.com

插入方面：對于非第0個位置的插入操作，區別不大，但不帶頭結點的鏈表在插入第0號位置之后需要重新改變head頭指針的指向。oqo28資訊網——每日最新資訊28at.com

oqo28資訊網——每日最新資訊28at.com

刪除方面：對于非第0個位置的刪除操作，區別不大，不帶頭結點的鏈表在刪除第0號位置之后需要重新改變head頭指針的指向。oqo28資訊網——每日最新資訊28at.com

• 頭部刪除（帶頭結點）：在帶頭結點的鏈表中，頭部刪除操作和普通刪除操作一樣。只需執行 head.next = head.next.next，這樣head的next直接指向第二個元素，從而刪除了第一個元素。
• 頭部刪除（不帶頭結點）：不帶頭結點的鏈表的第一個節點（head）存儲有效數據。在不帶頭結點的鏈表中，刪除也很簡單，只需將head指向鏈表中的第二個節點即可，即：head = head.next。

oqo28資訊網——每日最新資訊28at.com

總而言之：帶頭結點通過一個固定的頭可以使鏈表中任意一個節點都同等的插入、刪除。而不帶頭結點的鏈表在插入、刪除第0號位置時候需要特殊處理，最后還要改變head指向。兩者區別就是插入刪除首位(尤其插入)，個人建議以后在使用鏈表時候盡量用帶頭結點的鏈表避免不必要的麻煩。oqo28資訊網——每日最新資訊28at.com

帶頭指針VS帶尾指針

基本上是個鏈表都是要有頭指針的，那么頭尾指針是個啥呢？oqo28資訊網——每日最新資訊28at.com

頭指針： 其實頭指針就是鏈表中head節點，表示鏈表的頭，稱為為頭指針。oqo28資訊網——每日最新資訊28at.com

尾指針： 尾指針就是多一個tail節點的鏈表，尾指針的好處就是進行尾插入的時候可以直接插在尾指針的后面。oqo28資訊網——每日最新資訊28at.com

oqo28資訊網——每日最新資訊28at.com

但是帶尾指針的單鏈表如果刪除尾的話效率不高，需要枚舉整個鏈表找到tail前面的那個節點進行刪除。oqo28資訊網——每日最新資訊28at.com

插入操作

add(int index,T value) 其中index為插入的編號位置，value為插入的數據，在帶頭結點的鏈表中插入那么操作流程為oqo28資訊網——每日最新資訊28at.com

1. 找到對應index-1號節點成為pre。
2. node.next=pre.next，將插入節點后面先與鏈表對應部分聯系起來。此時node.next和pre.next一致。
3. pre.next=node 將node節點插入到鏈表中。

oqo28資訊網——每日最新資訊28at.com

當然，很多時候鏈表需要插入在尾部，如果頻繁的插入在尾部每次枚舉到尾部的話效率可能比較低，可能會借助一個尾指針去實現尾部插入。oqo28資訊網——每日最新資訊28at.com

刪除操作

按照index移除(主要掌握)：delete(int index)oqo28資訊網——每日最新資訊28at.com

帶頭結點鏈表的通用方法(刪除尾也一樣)，找到該index的前一個節點pre，pre.next=pre.next.nextoqo28資訊網——每日最新資訊28at.com

oqo28資訊網——每日最新資訊28at.com

代碼實現

在這里我也實現一個單鏈表給大家作為參考使用：oqo28資訊網——每日最新資訊28at.com

public class LinkedList<T> implements ListInterface<T> {    private Node<T> head;    private int size;    public LinkedList() {        head = new Node<>(null); // 頭結點不存儲數據        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()); // 打印表的內容    }}

總結

這里的只是簡單實現，實現基本方法。鏈表也只是單鏈表。完善程度還可以優化。oqo28資訊網——每日最新資訊28at.com

單鏈表查詢速度較慢，因為他需要從頭遍歷，如果在尾部插入，可以考慮設計帶尾指針的鏈表。而順序表查詢速度雖然快但是插入很費時，實際應用根據需求選擇！oqo28資訊網——每日最新資訊28at.com

Java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優化，并且JDK也做了大量優化。所以大家不用造輪子，可以直接用，但是手寫順序表、單鏈表還是很有學習價值的。oqo28資訊網——每日最新資訊28at.com

本文鏈接：http://www.tebozhan.com/showinfo-26-17177-0.html數據結構與算法—線性表

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 如何成為前1%的程序員

下一篇： Ydata_Profiling：自動生成數據探索報告的Python庫