一文搞懂線性表(順序表、連結串列)
點選上方 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也做了大量優化。所以大家不用造輪子，可以直接用，但是手寫順序表、單鏈表還是很有學習價值的。
單鏈表搞懂了，雙鏈表也就不遠了(下集預告)！
推薦閱讀
歡迎關注、轉發、在看分享，咱們下次再見！
點個在看你最好看
本文分享自微信公眾號 - bigsai（bigsai）。
如有侵權，請聯絡 [email protected] 刪除。
本文參與“OSC源創計劃”，歡迎正在閱讀的你也加入，一起分享。
- 結合大學四年經驗，帶你揭祕高效自學Java的方法和路線(從認識、方法、反饋3個角度出發)
- 因為LRU設計效率太低被pass了
- 動態規劃，就這些最常見了！
- 刷題難，程式設計師如何玩轉力扣？
- 如何搞定力扣刷題？
- 什麼是字典樹
- 資料結構與演算法—棧詳解
- 520，花一夜給女神寫走迷宮遊戲
- 雙鏈表最詳細圖解
- 大數加減乘除，一文搞定！
- (阿里高頻筆試)大數加減乘除，一文徹底搞定
- 【手寫資料結構】雙鏈表最詳細圖解
- 經典筆試題: 二叉樹中和為某一值的路徑(路徑總和)
- 資料結構與演算法必知基礎知識
- 一文搞懂線性表(順序表、連結串列)
- LeetCode 90子集Ⅱ&91解碼方法
- 跳錶(SkipList)|會跳的連結串列真的非常diao
- 三本逆襲成為學霸碩士研究生
- 5張圖搞懂Java引用拷貝、淺拷貝、深拷貝
- 花五分鐘看這篇之前，你才發現你不懂RESTful