Java數據結構之順序表和鏈表精解
前言
兩個數據結構：順序表和鏈表
數據結構是一門學科，和語言無關。
數據 + 結構：一種描述和組織數據的方式。
1. 順序表
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。其邏輯上和物理上都是連續的。
問題引入：一個數組放在這，我們如何才能自己不去數，讓程序自己進行計數？
答：在引入變量，每次放一個元素就更新一次。（如下圖，為問題的示意）
也就是說順序表的底層其實是一個數組，在 java 當中順序表都是動態的因為 java 當中的new 其實就相當於 c 語言中的 malloc 。
代碼實現
我們來實現一個動態順序表，以下是需要支持的接口。 各個函數的具體實現部分要我們自己來寫。
public class MyArrayList {//此為創建一個接口
public int[] elem;
public int usedSize;
public static int capacity = 10;
public MyArrayList() {
this.elem = new int[capacity];//新建一個數組
}
public boolean isFull() {
return this.usedSize == capacity;//判斷數組是否已滿
}
// 在 pos 位置新增元素
public void add(int pos, int data) { //pos為要插入元素的下標，data為要插入的數據
if (pos < 0 || pos > this.usedSize) {
System.out.println("pos位置不合法！");
return;
}
//1、滿的情況 2、pos的合法情況
if (isFull()) {
//擴容
this.elem = Arrays.copyOf(this.elem, 2 * capacity);
capacity *= 2;//新的容量
}//此處調用前面 isfull（） 函數來判斷是否已滿，返回真，執行if裡面的語句，擴容兩倍；若不滿，返回假，跳過if內的語句。
for (int i = this.usedSize - 1; i >= pos; i--) {
this.elem[i + 1] = this.elem[i];
}//在前面的代碼確定數組裡面有盈餘位置的情況下，將前一個數賦給後一個位置，從而騰出 pos 位置
this.elem[pos] = data; //給pos 位置的函數賦我們想要的值（即data）
this.usedSize++;//usedsize 是奇數器，pos位置增加一個數組，自然要算上
}
// 打印順序表
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}// 此處使用for循環遍歷打印
public boolean isEmpty() {
return this.usedSize == 0;
}//判斷數組是否為空
// 判定是否包含某個元素
public boolean contains(int toFind) {
if (isEmpty()) return false;
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i] == toFind) {
return true;
}
}
return false;
}//toFind 為我們要查找的元素，先判斷是否為空，再用循環遍歷判斷是否為該數
// 查找某個元素對應的位置
public int search(int toFind) {
if (isEmpty()) return -1;
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i] == toFind) {
return i;
}
}
return -1;
}//這個查找和上面的那個判斷唯一的區別就是上面返回的是真與假，這個返回的是查到的那個數，本質的方法都是一樣的
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (isEmpty()) {
//return -1; 業務的處理
throw new RuntimeException("順序表是空的");//手動拋出錯誤(異常)
}
if (pos < 0 || pos >= this.usedSize) {
throw new RuntimeException("pos不合法");//手動拋出錯誤(異常)
}
return this.elem[pos];
}//這個其實很簡單，隻需排除一下空表和pos 不合法的情況，之後返回 elem[pos]的值就行
// 獲取順序表長度
public int size() {
return this.usedSize;
}
// 給 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;
}//這個也簡單，隻要判斷一下 數組是否不合法，是否為空，直接 this.elem[pos] = value就行瞭
//刪除第一次出現的關鍵字key
public void remove(int toRemove) {
if (isEmpty()) return;
int index = search(toRemove);
if (index == -1) {
System.out.println("沒有你要刪除的數字");
return;
}
for (int i = index; i < this.usedSize - 1; i++) {
this.elem[i] = this.elem[i + 1];
}
this.usedSize--;
}
//這裡就是判斷數組是否為空，index 是否存在（此處調上面 search 函數），最後用for 循環遍歷，將後一個元素覆蓋在前一個元素上面
// 清空順序表
public void clear() {
for (int i = 0; i < this.usedSize; i++) {
this.elem[i] = 0;
}
this.usedSize = 0;
}//用for循環遍歷每一個元素，將其賦值為 0 ，之後再將計數器 usedsized 也賦值為 0
}
順序表的寫起來是非常簡單的，但是他也是有一定的缺陷和不足的。它主要是負責實現增刪查改的功能，查改功能是很簡便的，如果直接就給定下標的話，時間復雜度就是O（1），但是增刪的話，時間復雜度就必定為 O(N)，這就非常麻煩（也就是說以後當我們工作中要用查改就選用順序表就是最優選的）。所以我們接下來就有必要引入鏈表這一種數據結構。
2. 鏈表
鏈表是一種物理存儲結構上非連續存儲結構，其存儲結構便是上面放值，下面放下一個節點的地址，也就是說，雖然他是不連續的，當上一個節點仍然能找到下一個節點，類似於鏈子一樣，一個串一個，但區別是，鏈表彼此之間不相接觸。
鏈表圖解
代碼實現
class Node {//創建一個節點類
//一個節點是有兩個域或者多個域的，以下便是創建的兩個域
public int val;//鏈表裡面的數值
public Node next;//這是一個引用變量，用於標識每個鏈表單元的下一個數的地址，因為它存的是節點，而節點的類型就是Node，所以我們也用Node 來定義這個變量。
public Node(int val) { //這是一個類裡面的一個方法用來給鏈表當中的val賦值
this.val = val;//因為next存的hi下一個節點的地址，所以我們是不知道也不能賦值的
}
}
//鏈表
public class MyLinkedList {//此處為創建鏈表的接口
public Node head;//標識單鏈表的頭節點（這也是一個引用變量）
/**
* 窮舉的方式 創建鏈表 當然很low。此處隻是為瞭好理解
*/
public void createList() {
Node node1 = new Node(12);//新建一個節點的對象node1，此為節點1，賦值為12
Node node2 = new Node(3);//此為節點2，賦值3
Node node3 = new Node(5);//此為節點3，賦值5
Node node4 = new Node(2);//此為節點4，賦值6
node1.next = node2;//node1中的next存node2（node2是一個對象的引用，存的是對象在堆中的地址）
// 也就是說node1.next指向node2指向的地址
node2.next = node3;//以下三個原理同上
node3.next = node4;
this.head = node1;//此處為定義一個head（後面head可能會有改動）
}
/**
* 打印單鏈表
*/
public void show() {
Node cur = this.head;//將head的值暫時存到cur中，這樣就是單純地是cur在變，head值不改變
while(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;//通過這道程序將cur依次向後移動最後到空的時候打印出來
}
System.out.println();
}
//得到單鏈表的長度
public int size() {
Node cur = this.head;//同樣地，此處還以cur為介質向後移動
int count = 0;
while (cur != null) {
count++;//4 cur 依次經過各個節點的時候count便隨之計數
cur = cur.next;
}
return count;
}
//查找是否包含關鍵字key是否在單鏈表當中 15
public boolean contains(int val) {//這裡函數參數中的val就是我們要查找的 key
Node cur = this.head;
while (cur != null) {//同樣的方法遍歷節點
if(cur.val == val) {
return true;
}
cur = cur.next;
}
return false;//如果遍歷完瞭都沒有找到那就肯定沒有瞭
}
//頭插法
public void addFirst(int data) {//date為要插入的數據
Node node = new Node(data);//此處為創建要插入的節點（對象）內部存儲的值為 date
if(this.head == null) {//判斷頭結點是否為空
this.head = node;// 若為空，則根本沒有鏈表，直接將要插入的節點賦給head
}else { //此為有鏈表存在的狀況
node.next = this.head;//此處操作讓head原本指向的對象(節點)成為鏈表中的第二個節點
this.head = node;
//上面的操作讓head指向瞭node指向的節點(head是頭結點的標志，自然要讓他移到第一位)
}
}
//尾插法
public void addLast(int data) {//data為要插入的數據
Node node = new Node(data);//新建一個節點改值為data
if(this.head == null) {//判斷鏈表是否為空，若為空，則為一個節點便也是最後一個
this.head = node;//直接讓head指向node指向的節點即可
}else {//若節點不為空時
Node cur = this.head;//將head中的地址賦給中間變量cur
while (cur.next != null) {
cur = cur.next; //用cur遍歷節點
}
cur.next = node;//這是的cur已經待在瞭最後一個節點上它的next上沒有東西瞭
//所以這個時候將node指向的地址交給next，既完成瞭節點的插入
}
}
public Node searchPrev(int index) {
Node cur = this.head;//同樣地，以 cur為介質
int count = 0;
while(count != index-1) {
cur = cur.next;//用cur 遍歷鏈表
count++;
}
return cur;//此時返回的 cur剛好指向 index-1這個節點
}
//任意位置插入,第一個數據節點為0號下標
public void addIndex(int index,int data) {
if(index < 0 || index > size()) {//判斷index是否合法
System.out.println("下標不合法");
return;
}
//頭插法
if(index == 0) {//index為0時，就是頭插法
addFirst(data);
return;
}
//尾插法
if(index == size()) {//index為數組長度是就是尾插法
addLast(data);
return;
}
Node cur = searchPrev(index);//讓cur 拿到第index-1位置節點地址
Node node = new Node(data);//創建一個存瞭數據為data 的節點
node.next = cur.next;//將剛剛創建的節點中的next存進 cur 中的next(即把index的地址放到node的next裡)
cur.next = node;//再將node中存著的地址放到cur的next中
//插中間歸根到底就是next的交換，以下為傳遞順序：
//index-1中index的地址 ——> node.next
//node的地址 ——> cur.next
}
//下面這段代碼用來找val的前驅節點
public Node searchPrevNode(int val) {
Node cur = this.head;//還是以 cur 為中間量
while (cur.next != null) {//cur 遍歷至數組的最後一位
if(cur.next.val == val) {//這裡是判斷cur的下一個節點中的值是否為val
return cur;//如果是的就返回cur
}
cur = cur.next;
}
return null;
}
//刪除第一次出現關鍵字為key的節點
public void remove(int val) {
if(this.head == null) return;
//單獨判斷頭節點的問題
if(this.head.val == val) {
this.head = this.head.next;
return;//這段代碼的意思就是如果就是如果第一個節點中的值就是要刪除的值
//那麼直接就讓第一個節點的引用指向下一個節點，其實就是忽略第一個起到瞭一個刪除效果
//而原來第一個節點變成瞭沒有人引用的對象會被jvm回收
}
Node cur = searchPrevNode(val);//拿到下一個節點值為val的cur
if(cur == null) {//
System.out.println("沒有你要刪除的節點！");
return;
}
//下面就是cur 存在的情況
Node del = cur.next;//創建一個節點del讓其使用cur中下一個節點的地址(也就是要刪的val地址)
cur.next = del.next;//再把del中的存的下一個地址賦給 cur，那麼就間接地抹去瞭val
}
//刪除所有值為key的節點
public void removeAllKey(int val) {
if(this.head == null) {//節點是否為空？
return;
}
Node prev = this.head;//讓 prev指向 head指向的對象(prev本質上就是前驅節點)
Node cur = this.head.next;//讓 cur指向 head.next位置
while (cur != null) { //用cur 來遍歷數組
if(cur.val == val) { //
prev.next = cur.next;//抹去要刪的節點
cur = cur.next;//移動至下一個節點處
}else {//以下是 cur處的值 不等於 val 的情況
prev = cur;//將prev移到cur的位置
cur = cur.next;//再將cur 向後移動
}
}
//隻有頭結點且頭結點便是要刪除的val的情況
if(this.head.val == val) {
this.head = this.head.next;
}
}
public void clear(){
}
}
到此這篇關於Java數據結構之順序表和鏈表精解的文章就介紹到這瞭,更多相關Java 順序表和鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！