數據結構與算法之線性表(順序表、鏈表)詳解

原創公眾號：bigsai
文章已收錄在 全網都在關注的數據結構與算法學習倉庫 歡迎star

前言

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

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

  • 線性表：邏輯結構， 就是對外暴露數據之間的關係，不關心底層如何實現，數據結構的邏輯結構大分類就是線性結構和非線性結構而順序表、鏈表都是一種線性表。
  • 順序表、鏈表：物理結構，他是實現一個結構實際物理地址上的結構。比如順序表就是用數組實現。而鏈表用指針完成主要工作。不同的結構在不同的場景有不同的區別。

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

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

線性表基本架構

對於一個線性表來說。不管它的具體實現如何，但是它們的方法函數名和實現效果應該一致(即使用方法相同、達成邏輯上效果相同，差別的是運行效率)。線性表的概念與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位置上，完成插入操作

image-20210104194146220

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

刪除操作

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

image-20210104201346674

代碼實現

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

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雖然不直接使用指針但是我們也要理解指針的原理和運用。鏈表不同於順序表(數組)它的結構像一條鏈一樣鏈接成一個線性結構，而鏈表中每一個節點都存在不同的地址中，鏈表你可以理解為它存儲了指向節點(區域)的地址，能夠通過這個指針找到對應節點。

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

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

image-20210104215538219

基本結構

對於線性表，我們只需要一個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頭的指向。

image-20210104231252005

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

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

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

image-20210104231732318

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

帶頭指針VS帶尾指針

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

頭指針： 其實頭指針就是鏈表中head節點，成為頭指針。

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

image-20210105111135281

但是帶尾指針的單鏈表如果刪除尾的話效率不高，需要枚舉整個鏈表找到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節點插入到鏈表中。

image-20210105001736232

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

刪除操作

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

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

image-20210105161038897

代碼實現

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

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;
	}

}

總結

你可能會問這個是否正確啊，那我來測試一下：

image-20210105164129930

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

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

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

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

原創不易，bigsai請園友們幫兩件事幫忙一下:

  1. 點贊、關注支持一下， 您的肯定是我創作的源源動力。

  2. 微信搜索「bigsai」，2021我需要你的支持！

咱們下次再見！

image-20201114211553660

VirMach 便宜 VPS

QNews

QNews