[[373937]]

本文轉(zhuǎn)載自微信公眾號(hào)「 bigsai」，作者 bigsai 。轉(zhuǎn)載本文請(qǐng)聯(lián)系 bigsai公眾號(hào)。

前言

通過前面數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)我么知道了數(shù)據(jù)結(jié)構(gòu)的一些概念和重要性，那么我們今天總結(jié)下線性表相關(guān)的內(nèi)容。當(dāng)然，我用自己的理解分享給大家。(ps你有混淆是節(jié)點(diǎn)還是結(jié)點(diǎn)嘛)

其實(shí)說實(shí)話，可能很多人依然分不清線性表，順序表，和鏈表之間的區(qū)別和聯(lián)系!

• 線性表：邏輯結(jié)構(gòu)， 就是對(duì)外暴露數(shù)據(jù)之間的關(guān)系，不關(guān)心底層如何實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)大分類就是線性結(jié)構(gòu)和非線性結(jié)構(gòu)而順序表、鏈表都是一種線性表。
• 順序表、鏈表：物理結(jié)構(gòu)，他是實(shí)現(xiàn)一個(gè)結(jié)構(gòu)實(shí)際物理地址上的結(jié)構(gòu)。比如順序表就是用數(shù)組實(shí)現(xiàn)。而鏈表用指針完成主要工作。不同的結(jié)構(gòu)在不同的場(chǎng)景有不同的區(qū)別。

在Java中，大家都知道List接口類型，這就是邏輯結(jié)構(gòu)，因?yàn)樗褪欠庋b了一個(gè)線性關(guān)系的一系列方法和數(shù)據(jù)。而具體的實(shí)現(xiàn)其實(shí)就是跟物理結(jié)構(gòu)相關(guān)的內(nèi)容。比如順序表的內(nèi)容存儲(chǔ)使用數(shù)組的，然后一個(gè)get，set，add方法都要基于數(shù)組來完成,而鏈表是基于指針的。當(dāng)我們考慮對(duì)象中的數(shù)據(jù)關(guān)系就要考慮指針的屬性。指針的指向和value。

下面用一個(gè)圖來淺析線性表的關(guān)系?？赡苡行┎惶_切，但是其中可以參考，并且后面也會(huì)根據(jù)這個(gè)圖舉例。

線性表基本架構(gòu)

對(duì)于一個(gè)線性表來說。不管它的具體實(shí)現(xiàn)如何，但是它們的方法函數(shù)名和實(shí)現(xiàn)效果應(yīng)該一致(即使用方法相同、達(dá)成邏輯上效果相同，差別的是運(yùn)行效率)。線性表的概念與Java的接口/抽象類有那么幾分相似。最著名的就是List的Arraylist和LinkedList，List是一種邏輯上的結(jié)構(gòu)，表示這種結(jié)構(gòu)為線性表，而ArrayList，LinkedList更多的是一種物理結(jié)構(gòu)(數(shù)組和鏈表)。

所以基于面向?qū)ο蟮木幊趟季S，我們可以將線性表寫成一個(gè)接口，而具體實(shí)現(xiàn)的順序表和鏈表的類可以實(shí)現(xiàn)這個(gè)線性表的方法，提高程序的可讀性，還有一點(diǎn)比較重要的，記得初學(xué)數(shù)據(jù)結(jié)構(gòu)與算法時(shí)候?qū)崿F(xiàn)的線性表都是固定類型(int),隨著知識(shí)的進(jìn)步，我們應(yīng)當(dāng)采用泛型來實(shí)現(xiàn)更合理。至于接口的具體設(shè)計(jì)如下：

package LinerList; 
public interface ListInterface<T> {     
    void Init(int initsize);//初始化表 
    int length(); 
    boolean isEmpty();//是否為空 
    int ElemIndex(T t);//找到編號(hào) 
    T getElem(int index) throws Exception;//根據(jù)index獲取數(shù)據(jù) 
    void add(int index,T t) throws Exception;//根據(jù)index插入數(shù)據(jù) 
    void delete(int index) throws Exception; 
    void add(T t) throws Exception;//尾部插入 
    void set(int index,T t) throws Exception; 
    String toString();//轉(zhuǎn)成String輸出   
} 

順序表

順序表是基于數(shù)組實(shí)現(xiàn)的，所以所有實(shí)現(xiàn)需要基于數(shù)組特性。對(duì)于順序表的結(jié)構(gòu)應(yīng)該有一個(gè)存儲(chǔ)數(shù)據(jù)的數(shù)組data和有效使用長(zhǎng)度length.

還有需要注意的是初始化數(shù)組的大小，你可以固定大小，但是筆者為了可用性如果內(nèi)存不夠?qū)U(kuò)大二倍。

下面著重講解一些初學(xué)者容易混淆的概念和方法實(shí)現(xiàn)。

插入操作

add(int index,T t)

其中index為插入的編號(hào)位置，t為插入的數(shù)據(jù)，插入的流程為：

(1)從后(最后一個(gè)有數(shù)據(jù)位)向前到index依次后移一位，騰出index位置的空間

(2)將待插入數(shù)據(jù)賦值到index位置上，完成插入操作

可以看得出如果順序表很長(zhǎng)，在靠前的地方如果插入效率比較低(插入時(shí)間復(fù)雜度為O(n))，如果頻繁的插入那么復(fù)雜度挺高的。

刪除操作

同理，刪除也是非常占用資源的。原理和插入類似，刪除index位置的操作就是從index+1開始向后依次將數(shù)據(jù)賦值到前面位置上，具體可以看這張圖：

代碼實(shí)現(xiàn)

這里我實(shí)現(xiàn)一個(gè)順序表給大家作為參考學(xué)習(xí)：

package LinerList; 
 
public class seqlist<T> implements ListInterface<T> { 
    private Object[] date;//數(shù)組存放數(shù)據(jù) 
    private int lenth; 
    public seqlist() {//初始大小默認(rèn)為10 
        Init(10); 
    } 
 
    public void Init(int initsize) {//初始化 
        this.date=new Object[initsize]; 
        lenth=0;         
    } 
    public int length() {        
        return this.lenth; 
    } 
 
    public boolean isEmpty() {//是否為空 
        if(this.lenth==0) 
            return true; 
        return false; 
    } 
 
    /* 
     * * @param t    
     * 返回相等結(jié)果，為-1為false 
     */ 
    public int ElemIndex(T t) { 
        // TODO Auto-generated method stub 
        for(int i=0;i<date.length;i++) 
        { 
            if(date[i].equals(t)) 
            { 
                return i; 
            } 
        } 
        return -1; 
    } 
 
    /* 
     *獲得第幾個(gè)元素 
     */ 
    public T getElem(int index) throws Exception { 
        // TODO Auto-generated method stub 
        if(index<0||index>lenth-1) 
            throw new Exception("數(shù)值越界"); 
        return (T) date[index]; 
    } 
 
    public void add(T t) throws Exception {//尾部插入 
         add(lenth,t); 
    } 
 
    /* 
     *根據(jù)編號(hào)插入 
     */ 
    public void add(int index, T t) throws Exception { 
        if(index<0||index>lenth) 
            throw new Exception("數(shù)值越界"); 
        if (lenth==date.length)//擴(kuò)容 
        { 
            Object newdate[]= new Object[lenth*2]; 
            for(int i=0;i<lenth;i++) 
            { 
                newdate[i]=date[i]; 
            } 
            date=newdate; 
        } 
        for(int i=lenth-1;i>=index;i--)//后面元素后移動(dòng) 
        { 
            date[i+1]=date[i]; 
        } 
        date[index]=t;//插入元素 
        lenth++;//順序表長(zhǎng)度+1 
 
    } 
 
    public void delete(int index) throws Exception { 
        if(index<0||index>lenth-1) 
            throw new Exception("數(shù)值越界"); 
        for(int i=index;i<lenth;i++)//index之后元素前移動(dòng) 
        { 
            date[i]=date[i+1]; 
        } 
        lenth--;//長(zhǎng)度-1   
    } 
 
    @Override 
    public void set(int index, T t) throws Exception { 
        if(index<0||index>lenth-1) 
            throw new Exception("數(shù)值越界"); 
        date[index]=t; 
    } 
    public String  toString() { 
        String vaString=""; 
        for(int i=0;i<lenth;i++) 
        { 
            vaString+=date[i].toString()+" "; 
        } 
        return vaString; 
 
    } 
} 

鏈表

學(xué)習(xí)c/c++的時(shí)候鏈表應(yīng)該是很多人感覺很繞的東西，這個(gè)很大原因可能因?yàn)橹羔?，Java雖然不直接使用指針但是我們也要理解指針的原理和運(yùn)用。鏈表不同于順序表(數(shù)組)它的結(jié)構(gòu)像一條鏈一樣鏈接成一個(gè)線性結(jié)構(gòu)，而鏈表中每一個(gè)結(jié)點(diǎn)都存在不同的地址中，鏈表你可以理解為它存儲(chǔ)了指向結(jié)點(diǎn)(區(qū)域)的地址，能夠通過這個(gè)指針找到對(duì)應(yīng)結(jié)點(diǎn)。

對(duì)于物理存儲(chǔ)結(jié)構(gòu)，地址之間的聯(lián)系是無法更改的，相鄰就是相鄰。但對(duì)于鏈?zhǔn)酱鎯?chǔ)，下一位的地址是上一個(gè)主動(dòng)記錄的，可以進(jìn)行更改。這就好比親兄弟從出生就是同姓兄弟，而我們?cè)诔砷L(zhǎng)途中最好的朋友可能會(huì)由于階段性發(fā)生一些變化!

就如西天取經(jīng)的唐僧、悟空、八戒、沙和尚。他們本無聯(lián)系，但結(jié)拜為師徒兄弟，你問悟空他的師父他會(huì)立馬想到唐僧，因?yàn)槲逯干较碌募s定。

基本結(jié)構(gòu)

對(duì)于線性表，我們只需要一個(gè)data數(shù)組和length就能表示基本信息。而對(duì)于鏈表，我們需要一個(gè)node(head頭結(jié)點(diǎn))，和length分別表示存儲(chǔ)的結(jié)點(diǎn)數(shù)據(jù)和鏈表長(zhǎng)度，這個(gè)結(jié)點(diǎn)有數(shù)據(jù)域和指針域。數(shù)據(jù)域就是存放真實(shí)的數(shù)據(jù)，而指針域就是存放下一個(gè)node的指針，其具體結(jié)構(gòu)為：

class node<T>{ 
    T data;//結(jié)點(diǎn)的結(jié)果 
    node next;//下一個(gè)連接的結(jié)點(diǎn) 
    public node(){} 
    public node(T data) 
    { 
        this.data=data; 
    } 
    public node(T data, node next) { 
        this.data = data; 
        this.next = next; 
    }  
} 

帶頭結(jié)點(diǎn)鏈表VS不帶頭結(jié)點(diǎn)鏈表

有很多人會(huì)不清楚帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)鏈表的區(qū)別，甚至搞不懂什么是帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)，我給大家闡述一下：

帶頭結(jié)點(diǎn)：head指針始終指向一個(gè)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)不存儲(chǔ)有效值僅僅起到一個(gè)標(biāo)識(shí)作用(相當(dāng)于班主任帶學(xué)生)

不帶頭結(jié)點(diǎn)：head指針始終指向第一個(gè)有效結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)儲(chǔ)存有效數(shù)值。

那么帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的鏈表有啥區(qū)別呢?

查找上：無大區(qū)別，帶頭結(jié)點(diǎn)需要多找一次。

插入上：非第0個(gè)位置插入?yún)^(qū)別不大，不帶頭結(jié)點(diǎn)的插入第0號(hào)位置之后需要重新改變head頭的指向。

刪除上：非第0個(gè)位置刪除區(qū)別不大，不帶頭結(jié)點(diǎn)的刪除第0號(hào)位置之后需要重新改變head頭的指向。

頭部刪除(帶頭結(jié)點(diǎn))：帶頭結(jié)點(diǎn)的刪除和普通刪除一樣。直接head.next=head.next.next，這樣head.next就直接指向第二個(gè)元素了。第一個(gè)就被刪除了

頭部刪除(不帶頭結(jié)點(diǎn))：不帶頭結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn)(head)就存儲(chǔ)有效數(shù)據(jù)。不帶頭結(jié)點(diǎn)刪除也很簡(jiǎn)單，直接將head指向鏈表中第二個(gè)node結(jié)點(diǎn)就行了。即：head=head.next

總而言之：帶頭結(jié)點(diǎn)通過一個(gè)固定的頭可以使鏈表中任意一個(gè)結(jié)點(diǎn)都同等的插入、刪除。而不帶頭結(jié)點(diǎn)的鏈表在插入、刪除第0號(hào)位置時(shí)候需要特殊處理，最后還要改變head指向。兩者區(qū)別就是插入刪除首位(尤其插入)當(dāng)然我是建議你以后在使用鏈表時(shí)候盡量用帶頭結(jié)點(diǎn)的鏈表避免不必要的麻煩。

帶頭指針VS帶尾指針

基本上是個(gè)鏈表都是要有頭指針的，那么頭尾指針是個(gè)啥呢?

頭指針： 其實(shí)頭指針就是鏈表中head結(jié)點(diǎn)，成為頭指針。

尾指針： 尾指針就是多一個(gè)tail結(jié)點(diǎn)的鏈表，尾指針的好處就是進(jìn)行尾插入的時(shí)候可以直接插在尾指針的后面，然后再改變一下尾指針的順序即可。

但是帶尾指針的單鏈表如果刪除尾的話效率不高，需要枚舉整個(gè)鏈表找到tail前面的那個(gè)結(jié)點(diǎn)進(jìn)行刪除。

插入操作

add(int index,T t)

其中index為插入的編號(hào)位置，t為插入的數(shù)據(jù)，在帶頭結(jié)點(diǎn)的鏈表中插入在任何位置都是等效的。

加入插入一個(gè)結(jié)點(diǎn)node，根據(jù)index找到插入的前一個(gè)結(jié)點(diǎn)叫pre。那么操作流程為

1. node.next=pre.next，將插入結(jié)點(diǎn)后面先與鏈表對(duì)應(yīng)部分聯(lián)系起來。此時(shí)node.next和pre.next一致。
2. pre.next=node 將node結(jié)點(diǎn)插入到鏈表中。

當(dāng)然，很多時(shí)候鏈表需要插入在尾部，如果頻繁的插入在尾部每次枚舉到尾部的話效率可能比較低，可能會(huì)借助一個(gè)尾指針去實(shí)現(xiàn)尾部插入。

刪除操作

按照index移除(主要掌握)：delete(int index)

本方法為帶頭結(jié)點(diǎn)普通鏈表的通用方法(刪除尾也一樣)，找到該index的前一個(gè)結(jié)點(diǎn)pre，pre.next=pre.next.next

代碼實(shí)現(xiàn)

在這里我也實(shí)現(xiàn)一個(gè)單鏈表給大家作為參考使用：

package LinerList; 
 
class node<T>{ 
    T data;//結(jié)點(diǎn)的結(jié)果 
    node next;//下一個(gè)連接的結(jié)點(diǎn) 
    public node(){} 
    public node(T data) 
    { 
        this.data=data; 
    } 
    public node(T data, node next) { 
        this.data = data; 
        this.next = next; 
    } 
 
} 
public class Linkedlist<T> implements ListInterface<T>{ 
 
    node head; 
    private int length; 
    public Linkedlist() { 
        head=new node(); 
        length=0; 
    } 
    public void Init(int initsize) { 
        head.next=null; 
 
    } 
 
    public int length() { 
        return this.length; 
    } 
 
 
    public boolean isEmpty() { 
        if(length==0)return true; 
        else return false; 
    } 
 
    /* 
     * 獲取元素編號(hào) 
     */ 
    public int ElemIndex(T t) { 
        node team=head.next; 
        int index=0; 
        while(team.next!=null) 
        { 
            if(team.data.equals(t)) 
            { 
                return index; 
            } 
            index++; 
            team=team.next; 
        } 
        return -1;//如果找不到 
    } 
 
    @Override 
    public T getElem(int index) throws Exception { 
        node team=head.next; 
        if(index<0||index>length-1) 
        { 
            throw new Exception("數(shù)值越界"); 
        } 
        for(int i=0;i<index;i++) 
        { 
            team=team.next; 
        } 
        return (T) team.data; 
    } 
 
 
    public void add(T t) throws Exception { 
        add(length,t); 
 
    } 
    //帶頭結(jié)點(diǎn)的插入，第一個(gè)和最后一個(gè)一樣操作 
    public void add(int index, T value) throws Exception { 
        if(index<0||index>length) 
        { 
            throw new Exception("數(shù)值越界"); 
        } 
        node<T> team=head;//team 找到當(dāng)前位置node 
        for(int i=0;i<index;i++) 
        { 
             team=team.next; 
        } 
        node<T>node =new node(value);//新建一個(gè)node 
        node.next=team.next;//指向index前位置的下一個(gè)指針 
        team.next=node;//自己變成index位置     
        length++; 
    } 
 
 
    @Override 
    public void delete(int index) throws Exception { 
        if(index<0||index>length-1) 
        { 
            throw new Exception("數(shù)值越界"); 
        } 
        node<T> team=head;//team 找到當(dāng)前位置node 
        for(int i=0;i<index;i++)//標(biāo)記team 前一個(gè)結(jié)點(diǎn) 
        { 
             team=team.next; 
        } 
        //team.next結(jié)點(diǎn)就是我們要?jiǎng)h除的結(jié)點(diǎn) 
        team.next=team.next.next; 
        length--; 
    } 
 
    @Override 
    public void set(int index, T t) throws Exception { 
        // TODO Auto-generated method stub 
        if(index<0||index>length-1) 
        { 
            throw new Exception("數(shù)值越界"); 
        } 
        node<T> team=head;//team 找到當(dāng)前位置node 
        for(int i=0;i<index;i++) 
        { 
             team=team.next; 
        } 
        team.data=t;//將數(shù)值賦值，其他不變 
 
    } 
 
    public String toString() { 
        String va=""; 
        node team=head.next; 
        while(team!=null) 
        { 
            va+=team.data+" "; 
            team=team.next; 
        } 
        return va; 
    } 
 
} 

總結(jié)

你可能疑問代碼能跑起來不，那我來測(cè)試一下沒問題：

這里的只是簡(jiǎn)單實(shí)現(xiàn)，實(shí)現(xiàn)基本方法。鏈表也只是單鏈表。完善程度還可以優(yōu)化。能力有限， 如果有錯(cuò)誤或者優(yōu)化的地方還請(qǐng)大佬指正。

單鏈表查詢速度較慢，因?yàn)樗枰獜念^遍歷，如果在尾部插入，可以考慮設(shè)計(jì)帶尾指針的鏈表。而順序表查詢速度雖然快但是插入很費(fèi)時(shí)費(fèi)力，實(shí)際應(yīng)用根據(jù)需求選擇!

Java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優(yōu)化，并且JDK也做了大量?jī)?yōu)化。所以大家不用造輪子，可以直接用，但是手寫順序表、單鏈表還是很有學(xué)習(xí)價(jià)值的。