一文搞懂線性表(順序表、鏈表)
本文轉載自微信公眾號「 bigsai」，作者 bigsai 。轉載本文請聯系 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);//找到編號
- 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<T> implements 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。那么操作流程為
- node.next=pre.next，將插入結點后面先與鏈表對應部分聯系起來。此時node.next和pre.next一致。
- 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<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("數值越界");
- }
- 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也做了大量優化。所以大家不用造輪子，可以直接用，但是手寫順序表、單鏈表還是很有學習價值的。
