自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

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

作者： bigsai
運維 數(shù)據(jù)庫運維
通過前面數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識我么知道了數(shù)據(jù)結(jié)構(gòu)的一些概念和重要性，那么我們今天總結(jié)下線性表相關(guān)的內(nèi)容。當(dāng)然，我用自己的理解分享給大家。

 [[373937]]

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

前言

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

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

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

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

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

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

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

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

  1. package LinerList; 
  2. public interface ListInterface<T> {     
  3.     void Init(int initsize);//初始化表 
  4.     int length(); 
  5.     boolean isEmpty();//是否為空 
  6.     int ElemIndex(T t);//找到編號 
  7.     T getElem(int index) throws Exception;//根據(jù)index獲取數(shù)據(jù) 
  8.     void add(int index,T t) throws Exception;//根據(jù)index插入數(shù)據(jù) 
  9.     void delete(int index) throws Exception; 
  10.     void add(T t) throws Exception;//尾部插入 
  11.     void set(int index,T t) throws Exception; 
  12.     String toString();//轉(zhuǎn)成String輸出   
  13. } 

順序表

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

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

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

插入操作

add(int index,T t)

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

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

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

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

刪除操作

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

代碼實現(xiàn)

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

  1. package LinerList; 
  2.  
  3. public class seqlist<T> implements ListInterface<T> { 
  4.     private Object[] date;//數(shù)組存放數(shù)據(jù) 
  5.     private int lenth; 
  6.     public seqlist() {//初始大小默認(rèn)為10 
  7.         Init(10); 
  8.     } 
  9.  
  10.     public void Init(int initsize) {//初始化 
  11.         this.date=new Object[initsize]; 
  12.         lenth=0;         
  13.     } 
  14.     public int length() {        
  15.         return this.lenth; 
  16.     } 
  17.  
  18.     public boolean isEmpty() {//是否為空 
  19.         if(this.lenth==0) 
  20.             return true; 
  21.         return false; 
  22.     } 
  23.  
  24.     /* 
  25.      * * @param t    
  26.      * 返回相等結(jié)果，為-1為false 
  27.      */ 
  28.     public int ElemIndex(T t) { 
  29.         // TODO Auto-generated method stub 
  30.         for(int i=0;i<date.length;i++) 
  31.         { 
  32.             if(date[i].equals(t)) 
  33.             { 
  34.                 return i; 
  35.             } 
  36.         } 
  37.         return -1; 
  38.     } 
  39.  
  40.     /* 
  41.      *獲得第幾個元素 
  42.      */ 
  43.     public T getElem(int index) throws Exception { 
  44.         // TODO Auto-generated method stub 
  45.         if(index<0||index>lenth-1) 
  46.             throw new Exception("數(shù)值越界"); 
  47.         return (T) date[index]; 
  48.     } 
  49.  
  50.     public void add(T t) throws Exception {//尾部插入 
  51.          add(lenth,t); 
  52.     } 
  53.  
  54.     /* 
  55.      *根據(jù)編號插入 
  56.      */ 
  57.     public void add(int index, T t) throws Exception { 
  58.         if(index<0||index>lenth) 
  59.             throw new Exception("數(shù)值越界"); 
  60.         if (lenth==date.length)//擴容 
  61.         { 
  62.             Object newdate[]= new Object[lenth*2]; 
  63.             for(int i=0;i<lenth;i++) 
  64.             { 
  65.                 newdate[i]=date[i]; 
  66.             } 
  67.             date=newdate; 
  68.         } 
  69.         for(int i=lenth-1;i>=index;i--)//后面元素后移動 
  70.         { 
  71.             date[i+1]=date[i]; 
  72.         } 
  73.         date[index]=t;//插入元素 
  74.         lenth++;//順序表長度+1 
  75.  
  76.     } 
  77.  
  78.     public void delete(int index) throws Exception { 
  79.         if(index<0||index>lenth-1) 
  80.             throw new Exception("數(shù)值越界"); 
  81.         for(int i=index;i<lenth;i++)//index之后元素前移動 
  82.         { 
  83.             date[i]=date[i+1]; 
  84.         } 
  85.         lenth--;//長度-1   
  86.     } 
  87.  
  88.     @Override 
  89.     public void set(int index, T t) throws Exception { 
  90.         if(index<0||index>lenth-1) 
  91.             throw new Exception("數(shù)值越界"); 
  92.         date[index]=t; 
  93.     } 
  94.     public String  toString() { 
  95.         String vaString=""; 
  96.         for(int i=0;i<lenth;i++) 
  97.         { 
  98.             vaString+=date[i].toString()+" "; 
  99.         } 
  100.         return vaString; 
  101.  
  102.     } 
  103. } 

鏈表

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

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

就如西天取經(jīng)的唐僧、悟空、八戒、沙和尚。他們本無聯(lián)系，但結(jié)拜為師徒兄弟，你問悟空他的師父他會立馬想到唐僧，因為五指山下的約定。

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

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

  1. class node<T>{ 
  2.     T data;//結(jié)點的結(jié)果 
  3.     node next;//下一個連接的結(jié)點 
  4.     public node(){} 
  5.     public node(T data) 
  6.     { 
  7.         this.data=data; 
  8.     } 
  9.     public node(T data, node next) { 
  10.         this.data = data; 
  11.         this.next = next; 
  12.     }  
  13. } 

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

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

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

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

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

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

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

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

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

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

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

帶頭指針VS帶尾指針

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

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

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

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

插入操作

add(int index,T t)

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

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

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

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

刪除操作

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

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

代碼實現(xiàn)

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

  1. package LinerList; 
  2.  
  3. class node<T>{ 
  4.     T data;//結(jié)點的結(jié)果 
  5.     node next;//下一個連接的結(jié)點 
  6.     public node(){} 
  7.     public node(T data) 
  8.     { 
  9.         this.data=data; 
  10.     } 
  11.     public node(T data, node next) { 
  12.         this.data = data; 
  13.         this.next = next; 
  14.     } 
  15.  
  16. } 
  17. public class Linkedlist<T> implements ListInterface<T>{ 
  18.  
  19.     node head; 
  20.     private int length; 
  21.     public Linkedlist() { 
  22.         head=new node(); 
  23.         length=0; 
  24.     } 
  25.     public void Init(int initsize) { 
  26.         head.next=null; 
  27.  
  28.     } 
  29.  
  30.     public int length() { 
  31.         return this.length; 
  32.     } 
  33.  
  34.  
  35.     public boolean isEmpty() { 
  36.         if(length==0)return true; 
  37.         else return false; 
  38.     } 
  39.  
  40.     /* 
  41.      * 獲取元素編號 
  42.      */ 
  43.     public int ElemIndex(T t) { 
  44.         node team=head.next; 
  45.         int index=0; 
  46.         while(team.next!=null) 
  47.         { 
  48.             if(team.data.equals(t)) 
  49.             { 
  50.                 return index; 
  51.             } 
  52.             index++; 
  53.             team=team.next; 
  54.         } 
  55.         return -1;//如果找不到 
  56.     } 
  57.  
  58.     @Override 
  59.     public T getElem(int index) throws Exception { 
  60.         node team=head.next; 
  61.         if(index<0||index>length-1) 
  62.         { 
  63.             throw new Exception("數(shù)值越界"); 
  64.         } 
  65.         for(int i=0;i<index;i++) 
  66.         { 
  67.             team=team.next; 
  68.         } 
  69.         return (T) team.data; 
  70.     } 
  71.  
  72.  
  73.     public void add(T t) throws Exception { 
  74.         add(length,t); 
  75.  
  76.     } 
  77.     //帶頭結(jié)點的插入，第一個和最后一個一樣操作 
  78.     public void add(int index, T value) throws Exception { 
  79.         if(index<0||index>length) 
  80.         { 
  81.             throw new Exception("數(shù)值越界"); 
  82.         } 
  83.         node<T> team=head;//team 找到當(dāng)前位置node 
  84.         for(int i=0;i<index;i++) 
  85.         { 
  86.              team=team.next; 
  87.         } 
  88.         node<T>node =new node(value);//新建一個node 
  89.         node.next=team.next;//指向index前位置的下一個指針 
  90.         team.next=node;//自己變成index位置     
  91.         length++; 
  92.     } 
  93.  
  94.  
  95.     @Override 
  96.     public void delete(int index) throws Exception { 
  97.         if(index<0||index>length-1) 
  98.         { 
  99.             throw new Exception("數(shù)值越界"); 
  100.         } 
  101.         node<T> team=head;//team 找到當(dāng)前位置node 
  102.         for(int i=0;i<index;i++)//標(biāo)記team 前一個結(jié)點 
  103.         { 
  104.              team=team.next; 
  105.         } 
  106.         //team.next結(jié)點就是我們要刪除的結(jié)點 
  107.         team.next=team.next.next; 
  108.         length--; 
  109.     } 
  110.  
  111.     @Override 
  112.     public void set(int index, T t) throws Exception { 
  113.         // TODO Auto-generated method stub 
  114.         if(index<0||index>length-1) 
  115.         { 
  116.             throw new Exception("數(shù)值越界"); 
  117.         } 
  118.         node<T> team=head;//team 找到當(dāng)前位置node 
  119.         for(int i=0;i<index;i++) 
  120.         { 
  121.              team=team.next; 
  122.         } 
  123.         team.data=t;//將數(shù)值賦值，其他不變 
  124.  
  125.     } 
  126.  
  127.     public String toString() { 
  128.         String va=""; 
  129.         node team=head.next; 
  130.         while(team!=null) 
  131.         { 
  132.             va+=team.data+" "; 
  133.             team=team.next; 
  134.         } 
  135.         return va; 
  136.     } 
  137.  
  138. } 

總結(jié)

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

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

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

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

 

責(zé)任編輯：武曉燕 來源： bigsai
線性表鏈表數(shù)據(jù)
相關(guān)推薦

2023-11-08 07:56:38

單鏈表雙鏈表

2021-04-20 09:18:41

順序存儲結(jié)構(gòu)

2018-06-06 08:54:23

數(shù)據(jù)結(jié)構(gòu)存儲

2020-10-20 13:50:47

MySQL數(shù)據(jù)庫鎖

2024-04-12 12:19:08

語言模型AI

2022-03-24 08:51:48

Redis互聯(lián)網(wǎng)NoSQL

2021-03-22 10:05:59

netstat命令Linux

2023-09-08 08:20:46

ThreadLoca多線程工具

2023-09-15 12:00:01

API應(yīng)用程序接口

2023-11-06 06:43:23

單鏈表查詢數(shù)據(jù)結(jié)構(gòu)

2021-10-17 19:48:10

擴展頁表虛擬機

2020-09-27 08:00:49

分庫分表

2021-01-13 05:21:59

參數(shù)

2021-06-30 08:45:02

內(nèi)存管理面試

2022-08-15 15:39:23

JavaScript面向?qū)ο?/a>數(shù)據(jù)

2023-04-03 15:04:00

RPCPHP語言

2023-10-16 08:16:31

Bean接口類型

2024-06-05 11:43:10

2020-03-18 14:00:47

MySQL分區(qū)數(shù)據(jù)庫

2019-11-19 08:00:00

神經(jīng)網(wǎng)絡(luò)AI人工智能
點贊
收藏

51CTO技術(shù)棧公眾號