一、線性表
二、順序表
- 應用示例：實作一個動態順序表
- 2.1列印順序表
- 2.2獲取順序表長度
- 2.3在 pos 位置新增元素
- 2.4判定是否包含某個元素
- 2.5查找某個元素對應的位置
- 2.6獲取pos位置的元素
- 2.7給 pos 位置的元素設為/更新 value
- 2.8洗掉第一次出現的關鍵字key
- 2.9清空順序表
三、鏈表
- 3.1創建一個節點
- 3.2遍歷節點
- 3.3查找是否在單鏈表當中包含關鍵字key
- 3.4得到單鏈表的長度
- 3.5頭插法
- 3.6尾插法
- 3.7任意位置插入,第一個資料節點為0號下標
- 3.8洗掉第一次出現關鍵字為key的節點
- 3.9洗掉所有值為key的節點
- 3.10清空鏈表

一、線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列，線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

二、順序表

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，
采用順序表的形式，可以寫到類里面，將來就可以面向物件了，

順序表一般可以分為:

靜態順序表:使用定長陣列存盤，
動態順序表:使用動態開辟的陣列存盤，

靜態順序表適用于確定知道需要存多少資料的場景.
靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用，相比之下動態順序表更靈活, 根據需要動態的分配空間大小，

應用示例：實作一個動態順序表

定義一個MyArrayList類，里面的成員變數有兩個：elem、usedSize，還有一個構造方法，并在構造方法里面定義一個長度為10的陣列，并在測驗類中new一個MyArrayList物件，此時其底層結構如下圖所示：
在這里插入圖片描述
堆疊里面存放的MyArrayList參考指向堆里面的物件elem、usedSize，elem又在堆上new了一個長度為10的陣列，
代碼示例：

public class MyArrayList{
    public int[] elem;
    public int usedSize;//表示當前有效資料個數

    public MyArrayList(){
        this.elem = new int[10];
    }

2.1列印順序表

代碼示例：

 // 列印順序表
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] +" ");
        }
        System.out.println();
    }

2.2獲取順序表長度

代碼示例：

// 獲取順序表長度
    public int size() {
        return this.usedSize;
    }

2.3在 pos 位置新增元素

具體思想如下：
首先判斷pos位置是否合法，如果pos小于0或者pos大于陣列有效元素的個數，則認為該位置不合法，直接結束該陳述句，
然后，再判斷該陣列是否已經滿了，如果現存有效元素個數與陣列長度相等，就表明該陣列已經滿了，則這時就需要用到 Arrays.copyOf()函式來進行擴容，將陣列長度擴大為原來的兩倍，
最后，通過for回圈來進行陣列元素的移動，從有效元素位置開始，到要添加元素的pos位置，挨將前一個元素移動到后一個元素位置，直到移動到pos位置，然后將此位置賦值為要新增的data元素，最后再將有效元素的個數加1，

具體代碼實作如下：

 public void add(int pos, int data){
 	if(pos < 0 || pos > usedSize){
 		System.out.println("pos位置不合法");
		return;
	}
	if(isFull()){
		this.elem = Arrays.copyOf(this.elem,this.elem.length * 2);
	}
	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;
}

2.4判定是否包含某個元素

代碼示例：

public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }

2.5查找某個元素對應的位置

代碼示例：

 public int search(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

2.6獲取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;
    }

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

2.8洗掉第一次出現的關鍵字key

首先，判斷順序表示是否為空，
然后，應用5中得search()函式來查找要洗掉的元素，如果陣列中沒有要洗掉的陣列，則直接結束該陳述句，
最后，如果找到了要洗掉的元素，則利用for回圈從要洗掉元素位置開始，到有效元素個數-1位置截止，依次將后一個元素賦值給前一個元素，最后將有效元素個數減1，
代碼示例：

 public void remove(int toRemove) {
        if (isEmpty()){
            System.out.println("順序表為空");
            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--;
    }

2.9清空順序表

代碼示例：

public void clear() {
        this.usedSize = 0;//簡單型別

        //如果是參考資料型別，就要將所有的資料都要置為空
        /*for (int i = 0; i < usedSize; i++) {
            this.elem[i] == null;
        }
 		this.usedSize = 0;
		*/
    }

三、鏈表

鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的，
鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

單向、雙向
帶頭、不帶頭
回圈、非回圈

這里主要講解單向、不帶頭、非回圈及雙向、不帶頭、非回圈，

鏈表是由一個一個的節點組成，節點中包括：val資料域及next域存放下一個節點的地址，每一個節點都有一個地址，每個節點中的next域就存放著下一個節點的地址，
head里面存放的就是第一個節點（頭節點）的地址，head.next存盤的就是下一個節點的地址，
head叫做頭節點，最后一個節點叫做尾節點，尾節點的的next域為null，
鏈表的結構可以用畫圖的方式表示如下：
在這里插入圖片描述
上圖所畫鏈表為單向不帶頭非回圈鏈表，

具體代碼實作如下：

//ListNode代表一個節點
class ListNode{
    public int val;
    public ListNode next; //存盤的是節點的地址
	
	//有參構造
    public ListNode(int val){
        this.val = val;
    }
}

3.1創建一個節點

代碼示例：

public class MyLinkedList {
    public ListNode head;//鏈表的頭參考

    //創建一個節點
    public void createList(){
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        this.head = listNode1;//定義頭結點指向第一個節點的位置
    }

3.2遍歷節點

代碼示例：

public void display(){
        ListNode cur = this.head;//定義一個cur節點指向頭節點
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

3.3查找是否在單鏈表當中包含關鍵字key

代碼示例：

 public boolean contains(int key){
        ListNode cur = this.head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

3.4得到單鏈表的長度

代碼示例：

    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

3.5頭插法

代碼示例：

public void addFirst(int data){
        ListNode node = new ListNode(data);//定義一個新的node節點
        node.next = head;
        head = node;
        /*if (this.head == null){
            this.head = node;
        }else{
            node.next = head;
            head = node;
        }*/
    }

切記：系結位置的時候，一定要先系結后面，

所畫示意圖表示如下：
在這里插入圖片描述
測驗代碼如下：

public class TestDemo {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(12);
        myLinkedList.addFirst(23);
        myLinkedList.addFirst(34);
        myLinkedList.addFirst(45);
        myLinkedList.addFirst(56);
        }
  }

顯示結果：
頭插法

3.6尾插法

所畫示意圖表示如下：
在這里插入圖片描述

代碼示例：

public class TestDemo {
public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
	 		this.head = node;
		}else{
		ListNode cur = head.next;
		while(cur.next != null){
			cur = cur.next 
			}
			cur.next = node;
		}		
}

測驗代碼如下：

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
	}
}

顯示結果：
在這里插入圖片描述

3.7任意位置插入,第一個資料節點為0號下標

所畫示意圖表示如下：

代碼示例：

/**
     * 要插入到目標位置，必須先找到目標位置的前一個位置
     * 找到index-1位置的節點的地址
     * @param index
     * @return
     */
    public ListNode findIndex(int index){
        ListNode cur = this.head;
        while (index - 1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //任意位置插入,第一個資料節點為0號下標
    public void addIndex(int index,int data){
        if (index < 0 || index > size()){
            System.out.println("index位置不合法");
            return;
        }
        if (index == 0){
            addFirst(data);// 頭插
            return;
        }
        if (index == size()){
            addLast(data); //尾插
            return;
        }
        ListNode cur = findIndex(index);//要插入位置的前一個節點
        ListNode node = new ListNode(data); //要插入的節點
        node.next = cur.next;
        cur.next = node;
    }

3.8洗掉第一次出現關鍵字為key的節點

如要洗掉值為23的節點，則所畫示意圖表示如下：
在這里插入圖片描述
代碼示例：

 //找到要洗掉的關鍵字key的前驅
    public ListNode searchPerv(int key){
        ListNode cur = this.head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //洗掉第一次出現關鍵字為key的節點
    public void remove(int key){
        if (this.head == null){
            System.out.println("單鏈表為空，不能洗掉");
            return;
        }
        if (this.head.val == key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPerv(key);
        if (cur == null){
            System.out.println("沒有要洗掉的節點！！！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
 }

3.9洗掉所有值為key的節點

所畫示意圖表示如下：
在這里插入圖片描述
代碼示例：

public ListNode removeAllKey(int key){
        if (this.head == null){
            return null;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后判斷頭節點是否是要洗掉的key
        if (this.head.val == key){
            head = head.next;
        }
        return this.head;
    }

3.10清空鏈表

所畫示意圖表示如下：
在這里插入圖片描述
代碼示例：

public void clear(){
//        this.head = null;
    while (this.head != null){
        ListNode curNext = head.next;
        this.head.next = null;
        this.head = curNext;
        }
    }

以上，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/347106.html

標籤：java

上一篇：C++的虛函式表和虛析構

下一篇：Java重點 —— 類和物件

Java中順序表及鏈表詳解

目錄

一、線性表

二、順序表

應用示例：實作一個動態順序表

2.1列印順序表

2.2獲取順序表長度

2.3在 pos 位置新增元素

2.4判定是否包含某個元素

2.5查找某個元素對應的位置

2.6獲取pos位置的元素

2.7給 pos 位置的元素設為/更新 value

2.8洗掉第一次出現的關鍵字key

2.9清空順序表

三、鏈表

3.1創建一個節點

3.2遍歷節點

3.3查找是否在單鏈表當中包含關鍵字key

3.4得到單鏈表的長度

3.5頭插法

3.6尾插法

3.7任意位置插入,第一個資料節點為0號下標

3.8洗掉第一次出現關鍵字為key的節點

3.9洗掉所有值為key的節點

3.10清空鏈表