一文搞懂線性表(順序表、鏈表)

語言: CN / TW / HK



點擊上方 bigsai 關注我


前言

通過前面數據結構與算法基礎知識我麼知道了數據結構的一些概念和重要性,那麼我們今天總結下線性表相關的內容。當然,我用自己的理解分享給大家。(ps你有混淆是節點還是結點嘛)

其實説實話,可能很多人依然分不清線性表順序表,和鏈表之間的區別和聯繫!

  • 線性表:邏輯結構, 就是對外暴露數據之間的關係,不關心底層如何實現,數據結構的邏輯結構大分類就是線性結構和非線性結構而順序表、鏈表都是一種線性表。

  • 順序表、鏈表:物理結構,他是實現一個結構實際物理地址上的結構。比如順序表就是用數組實現。而鏈表用指針完成主要工作。不同的結構在不同的場景有不同的區別。

在Java中,大家都知道List接口類型,這就是邏輯結構,因為他就是封裝了一個線性關係的一系列方法和數據。而具體的實現其實就是跟物理結構相關的內容。比如順序表的內容存儲使用數組的,然後一個get,set,add方法都要基於數組來完成,而鏈表是基於指針的。當我們考慮對象中的數據關係就要考慮指針的屬性。指針的指向和value。

下面用一個圖來淺析線性表的關係。可能有些不太確切,但是其中可以參考,並且後面也會根據這個圖舉例。


線性表基本架構

對於一個線性表來説。不管它的具體實現如何,但是它們的方法函數名和實現效果應該一致(即使用方法相同、達成邏輯上效果相同,差別的是運行效率)。線性表的概念與Java的接口/抽象類有那麼幾分相似。最著名的就是List的Arraylist和LinkedList,List是一種邏輯上的結構,表示這種結構為線性表,而ArrayList,LinkedList更多的是一種物理結構(數組和鏈表)。

所以基於面向對象的編程思維,我們可以將線性表寫成一個接口,而具體實現的順序表和鏈表的類可以實現這個線性表的方法,提高程序的可讀性,還有一點比較重要的,記得初學數據結構與算法時候實現的線性表都是固定類型(int),隨着知識的進步,我們應當採用泛型來實現更合理。至於接口的具體設計如下:

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

順序表

順序表是基於數組實現的,所以所有實現需要基於數組特性。對於順序表的結構應該有一個存儲數據的數組data和有效使用長度length.

還有需要注意的是初始化數組的大小,你可以固定大小,但是筆者為了可用性如果內存不夠將擴大二倍。

下面着重講解一些初學者容易混淆的概念和方法實現。

插入操作

add(int index,T t)

其中index為插入的編號位置,t為插入的數據,插入的流程為:

(1)從後(最後一個有數據位)向前到index依次後移一位,騰出index位置的空間

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


可以看得出如果順序表很長,在靠前的地方如果插入效率比較低(插入時間複雜度為O(n)),如果頻繁的插入那麼複雜度挺高的。

刪除操作

同理,刪除也是非常佔用資源的。原理和插入類似,刪除index位置的操作就是從index+1開始向後依次將數據賦值到前面位置上,具體可以看這張圖:


代碼實現

這裏我實現一個順序表給大家作為參考學習:

package LinerList;

public class seqlist<Timplements ListInterface<T{
    private Object[] date;//數組存放數據
    private int lenth;
    public seqlist() {//初始大小默認為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   
     * 返回相等結果,為-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;
    }

    /*
     *獲得第幾個元素
     */

    public T getElem(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index<0||index>lenth-1)
            throw new Exception("數值越界");
        return (T) date[index];
    }

    public void add(T t) throws Exception {//尾部插入
         add(lenth,t);
    }

    /*
     *根據編號插入
     */

    public void add(int index, T t) throws Exception {
        if(index<0||index>lenth)
            throw new Exception("數值越界");
        if (lenth==date.length)//擴容
        {
            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--)//後面元素後移動
        {
            date[i+1]=date[i];
        }
        date[index]=t;//插入元素
        lenth++;//順序表長度+1

    }

    public void delete(int index) throws Exception {
        if(index<0||index>lenth-1)
            throw new Exception("數值越界");
        for(int i=index;i<lenth;i++)//index之後元素前移動
        {
            date[i]=date[i+1];
        }
        lenth--;//長度-1  
    }

    @Override
    public void set(int index, T t) throws Exception {
        if(index<0||index>lenth-1)
            throw new Exception("數值越界");
        date[index]=t;
    }
    public String  toString() {
        String vaString="";
        for(int i=0;i<lenth;i++)
        {
            vaString+=date[i].toString()+" ";
        }
        return vaString;

    }
}

鏈表

學習c/c++的時候鏈表應該是很多人感覺很繞的東西,這個很大原因可能因為指針,Java雖然不直接使用指針但是我們也要理解指針的原理和運用。鏈表不同於順序表(數組)它的結構像一條鏈一樣鏈接成一個線性結構,而鏈表中每一個結點都存在不同的地址中,鏈表你可以理解為它存儲了指向結點(區域)的地址,能夠通過這個指針找到對應結點。

對於物理存儲結構,地址之間的聯繫是無法更改的,相鄰就是相鄰。但對於鏈式存儲,下一位的地址是上一個主動記錄的,可以進行更改。這就好比親兄弟從出生就是同姓兄弟,而我們在成長途中最好的朋友可能會由於階段性發生一些變化!

就如西天取經的唐僧、悟空、八戒、沙和尚。他們本無聯繫,但結拜為師徒兄弟,你問悟空他的師父會立馬想到唐僧,因為五指山下的約定。


基本結構

對於線性表,我們只需要一個data數組和length就能表示基本信息。而對於鏈表,我們需要一個node(head頭結點),和length分別表示存儲的結點數據和鏈表長度,這個結點有數據域指針域。數據域就是存放真實的數據,而指針域就是存放下一個node的指針,其具體結構為:

class node<T>{
    T data;//結點的結果
    node next;//下一個連接的結點
    public node(){}
    public node(T data)
    
{
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    } 
}

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

有很多人會不清楚帶頭結點和不帶頭結點鏈表的區別,甚至搞不懂什麼是帶頭結點和不帶頭結點,我給大家闡述一下:

帶頭結head指針始終指向一個結點,這個結點不存儲有效值僅僅起到一個標識作用(相當於班主任帶學生)

不帶頭結head指針始終指向第一個有效結點,這個結點儲存有效數值。

那麼帶頭結點和不帶頭結點的鏈表有啥區別呢?

查找上:無大區別,帶頭結點需要多找一次。

插入上:非第0個位置插入區別不大,不帶頭結點的插入第0號位置之後需要重新改變head頭的指向。


刪除上:非第0個位置刪除區別不大,不帶頭結點的刪除第0號位置之後需要重新改變head頭的指向。

頭部刪除(帶頭結點):帶頭結點的刪除和普通刪除一樣。直接head.next=head.next.next,這樣head.next就直接指向第二個元素了。第一個就被刪除了

頭部刪除(不帶頭結點):不帶頭結點的第一個結點(head)就存儲有效數據。不帶頭結點刪除也很簡單,直接將head指向鏈表中第二個node結點就行了。即:head=head.next


總而言之:帶頭結點通過一個固定的頭可以使鏈表中任意一個結點都同等的插入、刪除。而不帶頭結點的鏈表在插入、刪除第0號位置時候需要特殊處理,最後還要改變head指向。兩者區別就是插入刪除首位(尤其插入)當然我是建議你以後在使用鏈表時候儘量用帶頭結點的鏈表避免不必要的麻煩。

帶頭指針VS帶尾指針

基本上是個鏈表都是要有頭指針的,那麼頭尾指針是個啥呢?

頭指針: 其實頭指針就是鏈表中head結點,成為頭指針。

尾指針: 尾指針就是多一個tail結點的鏈表,尾指針的好處就是進行尾插入的時候可以直接插在尾指針的後面,然後再改變一下尾指針的順序即可。


但是帶尾指針的單鏈表如果刪除尾的話效率不高,需要枚舉整個鏈表找到tail前面的那個結點進行刪除。

插入操作

add(int index,T t)
其中index為插入的編號位置,t為插入的數據,在帶頭結點的鏈表中插入在任何位置都是等效的。
加入插入一個結點node,根據index找到插入的前一個結點叫pre。那麼操作流程為

  1. node.next=pre.next,將插入結點後面先與鏈表對應部分聯繫起來。此時node.next和pre.next一致。

  2. pre.next=node 將node結點插入到鏈表中。


當然,很多時候鏈表需要插入在尾部,如果頻繁的插入在尾部每次枚舉到尾部的話效率可能比較低,可能會藉助一個尾指針去實現尾部插入。

刪除操作

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

本方法為帶頭結點普通鏈表的通用方法(刪除尾也一樣),找到該index的前一個結點pre,pre.next=pre.next.next


代碼實現

在這裏我也實現一個單鏈表給大家作為參考使用:

package LinerList;

class node<T>{
    T data;//結點的結果
    node next;//下一個連接的結點
    public node(){}
    public node(T data)
    
{
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    }

}
public class Linkedlist<Timplements 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;
    }

    /*
     * 獲取元素編號
     */

    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("數值越界");
        }
        for(int i=0;i<index;i++)
        {
            team=team.next;
        }
        return (T) team.data;
    }


    public void add(T t) throws Exception {
        add(length,t);

    }
    //帶頭結點的插入,第一個和最後一個一樣操作
    public void add(int index, T value) throws Exception {
        if(index<0||index>length)
        {
            throw new Exception("數值越界");
        }
        node<T> team=head;//team 找到當前位置node
        for(int i=0;i<index;i++)
        {
             team=team.next;
        }
        node<T>node =new node(value);//新建一個node
        node.next=team.next;//指向index前位置的下一個指針
        team.next=node;//自己變成index位置    
        length++;
    }


    @Override
    public void delete(int index) throws Exception {
        if(index<0||index>length-1)
        {
            throw new Exception("數值越界");
        }
        node<T> team=head;//team 找到當前位置node
        for(int i=0;i<index;i++)//標記team 前一個結點
        {
             team=team.next;
        }
        //team.next結點就是我們要刪除的結點
        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("數值越界");
        }
        node<T> team=head;//team 找到當前位置node
        for(int i=0;i<index;i++)
        {
             team=team.next;
        }
        team.data=t;//將數值賦值,其他不變

    }

    public String toString() {
        String va="";
        node team=head.next;
        while(team!=null)
        {
            va+=team.data+" ";
            team=team.next;
        }
        return va;
    }

}

總結

你可能疑問代碼能跑起來不,那我來測試一下沒問題:


這裏的只是簡單實現,實現基本方法。鏈表也只是單鏈表。完善程度還可以優化。能力有限, 如果有錯誤或者優化的地方還請大佬指正

單鏈表查詢速度較慢,因為他需要從頭遍歷,如果在尾部插入,可以考慮設計帶尾指針的鏈表。而順序表查詢速度雖然快但是插入很費時費力,實際應用根據需求選擇

Java中的Arraylist和LinkedList就是兩種方式的代表,不過LinkedList使用雙向鏈表優化,並且JDK也做了大量優化。所以大家不用造輪子,可以直接用,但是手寫順序表、單鏈表還是很有學習價值的。

單鏈表搞懂了,雙鏈表也就不遠了(下集預告)!

推薦閲讀

  跳錶 | 會跳的鏈表原來這麼diao
  數據結構與算法之基本概念
「乾貨總結」程序員必知必會的十大排序算法
  花5分鐘看這篇之前,你才發現你不懂RESTful
「五大常用算法」一文圖解分治算法和思想

歡迎關注、轉發、在看分享,咱們下次再見!


點個在看你最好看

本文分享自微信公眾號 - bigsai(bigsai)。
如有侵權,請聯繫 [email protected] 刪除。
本文參與“OSC源創計劃”,歡迎正在閲讀的你也加入,一起分享。