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

點(diǎn)擊上方?bigsai?關(guān)注我

前言

通過前面數(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)， 就是對外暴露數(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)在不同的場景有不同的區(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)我們考慮對象中的數(shù)據(jù)關(guān)系就要考慮指針的屬性。指針的指向和value。

下面用一個(gè)圖來淺析線性表的關(guān)系。可能有些不太確切，但是其中可以參考，并且后面也會(huì)根據(jù)這個(gè)圖舉例。

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

對于一個(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);//找到編號
????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ù)組特性。對于順序表的結(jié)構(gòu)應(yīng)該有一個(gè)存儲(chǔ)數(shù)據(jù)的數(shù)組data和有效使用長度length.

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

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

插入操作

add(int index,T t)

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

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

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

可以看得出如果順序表很長，在靠前的地方如果插入效率比較低(插入時(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????????{
????????????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ù)編號插入
?????*/
????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????????????{
????????????????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++;//順序表長度+1

????}

????public?void?delete(int?index)?throws?Exception?{
????????if(index<0||index>lenth-1)
????????????throw?new?Exception("數(shù)值越界");
????????for(int?i=index;i//index之后元素前移動(dòng)
????????{
????????????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("數(shù)值越界");
????????date[index]=t;
????}
????public?String??toString()?{
????????String?vaString="";
????????for(int?i=0;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è)指針找到對應(yīng)結(jié)點(diǎn)。

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

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

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

對于線性表，我們只需要一個(gè)data數(shù)組和length就能表示基本信息。而對于鏈表，我們需要一個(gè)node(head頭結(jié)點(diǎn))，和length分別表示存儲(chǔ)的結(jié)點(diǎn)數(shù)據(jù)和鏈表長度，這個(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號位置之后需要重新改變head頭的指向。

刪除上：非第0個(gè)位置刪除區(qū)別不大，不帶頭結(jié)點(diǎn)的刪除第0號位置之后需要重新改變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)刪除也很簡單，直接將head指向鏈表中第二個(gè)node結(jié)點(diǎn)就行了。即：head=head.next

總而言之：帶頭結(jié)點(diǎn)通過一個(gè)固定的頭可以使鏈表中任意一個(gè)結(jié)點(diǎn)都同等的插入、刪除。而不帶頭結(jié)點(diǎn)的鏈表在插入、刪除第0號位置時(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為插入的編號位置，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)后面先與鏈表對應(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;
????}

????/*
?????*?獲取元素編號
?????*/
????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????????{
????????????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?team=head;//team?找到當(dāng)前位置node
????????for(int?i=0;i????????{
?????????????team=team.next;
????????}
????????nodenode?=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?team=head;//team?找到當(dāng)前位置node
????????for(int?i=0;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?team=head;//team?找到當(dāng)前位置node
????????for(int?i=0;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é)

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

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

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

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

單鏈表搞懂了，雙鏈表也就不遠(yuǎn)了(下集預(yù)告)！

推薦閱讀

歡迎關(guān)注、轉(zhuǎn)發(fā)、在看分享，咱們下次再見！

點(diǎn)個(gè)在看你最好看