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