站長資訊網本篇文章給大家帶來了關于java的相關知識，其中主要介紹了關于順序表和鏈表的相關內容，順序表就是一個數組，是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，下面一起來看一下，希望對大家有幫助。
程序員必備接口測試調試工具：立即使用
Apipost = Postman + Swagger + Mock + Jmeter
Api設計、調試、文檔、自動化測試工具
后端、前端、測試，同時在線協作，內容實時同步
推薦學習：《java視頻教程》
1. 線性表
線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。
2. 順序表
其實就是一個數組。【增刪查改】那為什么還有寫一個順序表，直接用數組就好了嘛？不一樣，寫到類里面 將來就可以 面向對象了。
2.1 概念及結構
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。
順序表一般可以分為：
- 靜態順序表：使用定長數組存儲。
- 動態順序表：使用動態開辟的數組存儲。
靜態順序表適用于確定知道需要存多少數據的場景.
靜態順序表的定長數組導致N定大了，空間開多了浪費，開少了不夠用.
相比之下動態順序表更靈活, 根據需要動態的分配空間大小.
2.2 接口實現
我們來實現一個動態順序表. 以下是需要支持的接口.
這里我們挨個拆解出來：
public class MyArrayList { public int[] elem; public int usedSize;//有效的數據個數 public MyArrayList() { this.elem = new int[10]; } // 打印順序表public void display() { } System.out.println();}// 獲取順序表長度public int size() { return 0;}// 在 pos 位置新增元素public void add(int pos, int data) {}// 判定是否包含某個元素public boolean contains(int toFind) { return true;}// 查找某個元素對應的位置public int search(int toFind) { return -1;}// 獲取 pos 位置的元素public int getPos(int pos) { return -1;}// 給 pos 位置的元素設為 valuepublic void setPos(int pos, int value) {}//刪除第一次出現的關鍵字keypublic void remove(int toRemove) {}// 清空順序表public void clear() {}}
這是我們順序表的基本結構。下面我們就把順序表的功能一個一個拆解出來：
打印數據表：
public void display() { for (int i = 0; i < this.usedSize; i++) { System.out.print(this.elem[i] + " "); } System.out.println();}
獲取順序表長度：
public int size() { return this.usedSize;}
在 pos 位置新增元素：
public void add(int pos, int data) { if(pos < 0 || pos > this.usedSize) { System.out.println("pos 位置不合法"); return; } if(isFull()){ this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } for (int i = this.usedSize-1; i >= pos; i--) { this.elem[i + 1] = this.elem[i]; } this.elem[pos] = data; this.usedSize++;}//判斷數組元素是否等于有效數據個數public boolean isFull() { return this.usedSize == this.elem.length;}
判斷是否包含某個元素：
public boolean contains(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) { return true; } } return false;}
查找某個元素對應的位置：
public int search(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) { return i; } } return -1;}
獲取 pos 位置的元素：
public int getPos(int pos) { if (pos < 0 || pos >= this.usedSize){ System.out.println("pos 位置不合法"); return -1;//所以 這里說明一下,業務上的處理，這里不考慮 } if(isEmpty()) { System.out.println("順序表為空！"); return -1; } return this.elem[pos];}//判斷數組鏈表是否為空public boolean isEmpty() { return this.usedSize == 0;}
給 pos 位置的元素設為 value：
public void setPos(int pos, int value) { if(pos < 0 || pos >= this.usedSize) { System.out.println("pos 位置不合法"); return; } if(isEmpty()) { System.out.println("順序表為空！"); return; } this.elem[pos] = value;}//判斷數組鏈表是否為空public boolean isEmpty() { return this.usedSize == 0;}
刪除第一次出現的關鍵字key：
public void remove(int toRemove) { if(isEmpty()) { System.out.println("順序表為空！"); return; } int index = search(toRemove);//index記錄刪除元素的位置 if(index == -1) { System.out.println("沒有你要刪除的數字！"); } for (int i = index; i < this.usedSize - 1; i++) { this.elem[i] = this.elem[i + 1]; } this.usedSize--; //this.elem[usedSize] = null;引用數組必須這樣做才可以刪除}
清空順序表：
public void clear() { this.usedSize = 0;}
2.3 順序表的問題及思考
-
順序表中間/頭部的插入刪除，時間復雜度為O(N)
-
增容需要申請新空間，拷貝數據，釋放舊空間。會有不小的消耗。
-
增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間。
思考： 如何解決以上問題呢？下面給出了鏈表的結構來看看。
3. 鏈表
3.1 鏈表的概念及結構
鏈表是一種物理存儲結構上非連續存儲結構，數據元素的邏輯順序是通過鏈表中的引用鏈接次序實現的 。
實際中鏈表的結構非常多樣，如果按一般來分的話就是四種：
-
單向鏈表
-
雙向鏈表
-
循環鏈表
-
雙向循環鏈表
如果細分的話就有以下情況組合起來就有8種鏈表結構：
- 單向、雙向
- 帶頭、不帶頭
- 循環、非循環
這八種分別為：
-
單向 帶頭 循環
-
單向 不帶頭 循環
-
單向 帶頭 非循環
-
單向 不帶頭 非循環
-
雙向 帶頭 循環
-
雙向 不帶頭 循環
-
雙向 帶頭 非循環
-
雙向 不帶頭 非循環
注：上述加粗是我們重點需要學習的！！！
雖然有這么多的鏈表的結構，但是我們重點掌握兩種:
- 無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中
