目錄

• • 前言
  • 線性表基本架構
  • 順序表
  • • 插入
    • 刪除
    • 其他操作
  • 鏈表
  • • 基本結構
    • 插入
    • 帶頭節(jié)點與不帶頭節(jié)點
    • 插入尾
    • 刪除
    • 其他
  • 代碼實現(xiàn)
  • • 順序表
    • 鏈表
    • 測試與結果
  • 總結

原創(chuàng)公眾號：bigsai 文章收藏在GitHub

前言

通過前面數(shù)據(jù)結構與算法前導我么知道了數(shù)據(jù)結構的一些概念和重要性，那么我們今天總結下線性表相關的內容。當然，我用自己的理解解分享給大家。

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

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

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

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

線性表基本架構

對于一個線性表來說。不管它的具體實現(xiàn)方法如何，我們應該有的函數(shù)名稱和實現(xiàn)效果應該一致。你也可以感覺的到在一些結構的設計。比如List的Arraylist和LinkedList。Map的HashMap和currentHashMap他們的接口api都是相同的，但是底層設計實現(xiàn)肯定是有區(qū)別的。

所以，基于面向對象的編程思維，我們可以將線性表寫成一個接口，而具體實現(xiàn)的順序表和鏈表可以繼承這個接口的方法，提高程序的可讀性。

還有一點比較重要的，記得初學數(shù)據(jù)結構與算法時候實現(xiàn)的線性表都是固定類型(int),隨著知識的進步，我們應當采用泛型來實現(xiàn)更合理。至于接口的具體設計如下：

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();//轉成String輸出 }

順序表

順序表是基于數(shù)組實現(xiàn)的，所以一些方法要基于數(shù)組的特性。對于順序表應該有的基礎屬性為一個數(shù)組data和一個length.

還有需要注意的是初始化數(shù)組的大小，你可以固定大小，但是筆者為了可用性如果內存不夠將擴大二倍。當然這樣很可能因為空間使用問題造成很大的浪費。

一些基本的額方法就不說了，下面著重講解一些初學者容易混淆的概念和方法實現(xiàn)。這里把順序表比作一隊坐在板凳上的人。

插入

add(int index,T t)
其中index為插入的編號位置，t為插入的數(shù)據(jù)



-根據(jù)圖片你就很好理解插入操作。當插入一個index時候，他的后面所有元素都要后移一位。你可以看的出插入時候整個操作的臃腫性。所以這也是順序表性能表現(xiàn)最差的地方,頻繁的插入，刪除。

刪除

同理，刪除也是非常占用資源的。原理和插入類似，不過人走了，空一個小板凳后面的人需要往前挪。

其他操作

其他操作就很簡單了。比如如果按照編號獲取數(shù)據(jù)getElem(int index)，你可以直接根據(jù)數(shù)據(jù)坐標返回。a[index]，而其他操作，可以通過遍歷直接操作數(shù)組即可。

鏈表

我想，表應該是很多人感覺很繞的東西，這個很大原因可能因為指針。很多人說java沒指針，其實java他也有隱形指針。只不過不能直接用罷了。

指針建立的數(shù)據(jù)關系往往比數(shù)組這些要抽象的多。對于指針域，你把他當成一個對象就好了，不過這個對象指向的是另一個同等級對象。對于這個關系，你可以比作每個person類。每個person類都有老公(老婆),而這個老公老婆也是一個實際對象，可以理解這更像一種邏輯約定關系，而不是硬生生的關系吧。
指針你可以考慮成腦子記憶。上面的順序表我們說它有序因為每個小板凳(數(shù)組)有編號，我們可以根據(jù)這個來確定位置。而對于鏈表來說，你可以看作成一個站在操場上的一隊人。而他的操作也略有不同，下面針對一些比較特殊和重要的進行歸納。

基本結構

對于線性表，我們只需要一個data數(shù)組和length就能表示基本信息。而對于鏈表，我們需要一個node(head頭節(jié)點)，和length,當然，這個node也是一個結構體。

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

當然，這個節(jié)點有數(shù)據(jù)域和指針域。數(shù)據(jù)域就是存放真實的數(shù)據(jù)，而指針域就是存放下一個node的指針。所以相比順序表，如果用滿數(shù)組情況下，鏈表占用更多的資源，因為它要存放指針占用資源。

插入

add(int index,T t)
其中index為插入的編號位置，t為插入的數(shù)據(jù)
加入插入一個節(jié)點node，根據(jù)index找到插入的前一個節(jié)點叫pre。那么操作流程為

node.next=pre.next如下1的操作，將插入節(jié)點后面聯(lián)系起來。此時node.next和pre.next一致。

pre.next=node因為我們要插入node，而node鏈可以替代pre自身的next。那么直接將pre指向node。那么就相當于原始鏈表插入了一個node。

帶頭節(jié)點與不帶頭節(jié)點

很多人搞不清什么是帶頭節(jié)點和不帶頭節(jié)點。帶頭節(jié)點就是head節(jié)點不放數(shù)據(jù)，第0項從head后面那個開始數(shù)。而不帶頭節(jié)點的鏈表head放數(shù)據(jù)，head節(jié)點就是第0位。
主要區(qū)別：

• 帶頭節(jié)點和不帶頭節(jié)點的主要區(qū)別就在插入刪除首位，尤其是首位插入。帶頭節(jié)點找元素需要多遍歷一次因為它的第一個head節(jié)點是頭節(jié)點，不存數(shù)據(jù)(可看作一列火車的火車頭)。而方便的就是帶頭節(jié)點在首位插入更簡單。因為插入第0位也是在head的后面。
• 而不帶頭節(jié)點的鏈表就需要特殊考慮首位。因為插入第0位其實是插入head的前面。假設有head，插入node。具體操作為：
  
• node.next=head；(node指向head，node這條鏈成我們想要的鏈)
• head=node；(很多人想不明白，其實這個時候node才是插入后最長鏈的首位節(jié)點，head在他的后面，而在鏈表中head通常表示首位節(jié)點，所以head不表示第二個節(jié)點，直接"="node節(jié)點。這樣head和node都表示操作完成的鏈表。但是對外暴露的只有head。所以head只能指向第一個節(jié)點！)

插入尾

• 而在插入尾部的時候，需要注意尾部的next為null。不能和插入普通位置相比！

刪除

按照index移除：delete(int index)

• 找到該index的節(jié)點node。node.next=node.next.nex

按照尾部移除(拓展)：deleteEnd()
這個方法我沒有寫，但是我給大家講一下，按照尾部刪除的思想就是：

聲明一個node為head。

當node.next！=null時node=node.next 指向下一個

當node.next==null時候。說明這個節(jié)點時最后一個。你可以node=null。這個這個node的前驅pre的next就是null。這個節(jié)點就被刪除了。

頭部刪除(帶頭節(jié)點)：

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

頭部刪除(不帶頭節(jié)點)

• 我們知道不帶頭節(jié)點的第一個就是存貨真價實的元素的。不帶頭節(jié)點刪除也很簡單。直接將head移到第二位就行了。即：head=head.next
  

其他

• 對于其他操作，主要時結合查找。而單鏈表的查找時從head開始。然后另一個節(jié)點team=head或head.next。然后用這個節(jié)點不停的等于它指向的next去查找我們需要的內容即while(循環(huán)條件){team=team.next}類似。
• 不同教程和人寫的線性表也不一致，這里只給出一個樣例學習使用而并不是標準，希望大家審視。
• 在實現(xiàn)上用了帶頭節(jié)點的鏈表實現(xiàn)，因為比較方便管理，不需要很多if else.

代碼實現(xiàn)

順序表

package LinerList;public class seqlist<T> implements ListInterface<T> {private Object[] date;//數(shù)組存放數(shù)據(jù)private int lenth;public seqlist() {//初始大小默認為10Init(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 stubfor(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 stubif(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)//擴容{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("數(shù)值越界");for(int i=index;i<lenth;i++)//index之后元素前移動{date[i]=date[i+1];}lenth--;//長度-1 }@Overridepublic 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;} }

鏈表

package LinerList;class node<T>{T data;//節(jié)點的結果node next;//下一個連接的節(jié)點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;//如果找不到}@Overridepublic 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é)點的插入，第一個和最后一個一樣操作public void add(int index, T value) throws Exception {if(index<0||index>length){throw new Exception("數(shù)值越界");}node<T> team=head;//team 找到當前位置nodefor(int i=0;i<index;i++){team=team.next;}node<T>node =new node(value);//新建一個nodenode.next=team.next;//指向index前位置的下一個指針team.next=node;//自己變成index位置 length++;}@Overridepublic void delete(int index) throws Exception {if(index<0||index>length-1){throw new Exception("數(shù)值越界");}node<T> team=head;//team 找到當前位置nodefor(int i=0;i<index;i++)//標記team 前一個節(jié)點{team=team.next;}//team.next節(jié)點就是我們要刪除的節(jié)點team.next=team.next.next;length--;}@Overridepublic void set(int index, T t) throws Exception {// TODO Auto-generated method stubif(index<0||index>length-1){throw new Exception("數(shù)值越界");}node<T> team=head;//team 找到當前位置nodefor(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;}}

測試與結果

package LinerList; public class test {public static void main(String[] args) throws Exception {// TODO Auto-generated method stubSystem.out.println("線性表測試：");ListInterface<Integer>list=new seqlist<Integer>();list.add(5);list.add(6);list.add(1,8);list.add(3,996);list.add(7);System.out.println(list.ElemIndex(8));System.out.println(list.toString());list.set(2, 222);System.out.println(list.toString());list.delete(4);System.out.println(list.toString());System.out.println(list.length()); System.out.println("鏈表測試：");list=new Linkedlist<Integer>();list.add(5);list.add(6);list.add(1,8);list.add(3,996);list.add(7);System.out.println(list.ElemIndex(8));System.out.println(list.toString());list.set(2, 222);System.out.println(list.toString());list.delete(4);System.out.println(list.toString());System.out.println(list.length()); } }

輸出:

線性表測試：
1
5 8 6 996 7
5 8 222 996 7
5 8 222 996
4
鏈表測試：
1
5 8 6 996 7
5 222 6 996 7
5 222 6 996
4

總結

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

單鏈表查詢速度較慢，因為他需要從頭遍歷。如果頻繁操作尾部，可以考慮鏈表中不僅有head在加尾tail節(jié)點。而順序表查詢速度雖然快但是插入很費時費力。實際應用根據(jù)需求選擇！

java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優(yōu)化，并且jdk的api做了大量優(yōu)化。所以大家不用造輪子，可以直接用，但是還是很有學習價值的。

如果有不理解或者不懂的可以聯(lián)系交流討論。

原創(chuàng)不易，bigsai請csdn的朋友們幫兩件事幫忙一下:

點贊、在看、分享支持一下， 您的肯定是我創(chuàng)作的源源動力。

微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。

咱們下次再見！

總結

以上是生活随笔為你收集整理的数据结构于算法—线性表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。