前言

本文主要講解數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的線性表
內(nèi)容包括其特點泽西、結(jié)構(gòu)（順序存儲結(jié)構(gòu) & 鏈?zhǔn)浇Y(jié)構(gòu)）等予颤，希望你們會喜歡。

1. 簡介

示意圖

其中癣亚，線性表的存儲結(jié)構(gòu)最為重要
下面，我將主要講解其 順序存儲結(jié)構(gòu) & 鏈?zhǔn)酱鎯Y(jié)構(gòu)

2. 順序存儲結(jié)構(gòu)

實現(xiàn)方式：數(shù)組
下面贾虽，我將主要講解其結(jié)構(gòu)特點 & 相關(guān)操作

2.1 結(jié)構(gòu)特點

存儲線性表的數(shù)據(jù)元素的方式 = 一段地址連續(xù)的存儲單元
具備：起始位置逃糟、數(shù)組長度（最大存儲容量） & 線性表長度（當(dāng)前長度）

示意圖

示意圖

概念說明

概念	說明
數(shù)組長度	存放線性表的空間長度（固定不變）
線性表長度	存放線性表數(shù)據(jù)元素的長度（動態(tài)變化）
地址	存儲單元的編號
數(shù)組下標(biāo)	第 i 個元素 = 數(shù)組下標(biāo)第 i-1 的位置

2.2 對應(yīng)操作

順序存儲結(jié)構(gòu)的操作包括：插入 & 刪除

操作1：插入

示意圖

操作2：刪除

示意圖

注：線性表的存取數(shù)據(jù)時間性能 = O（1）

2.3 結(jié)構(gòu)優(yōu)、缺點

示意圖

2.4 應(yīng)用場景

已知長度蓬豁、數(shù)據(jù)元素個數(shù)變化不大绰咽、存、取數(shù)據(jù)頻率高的場景

2.5 總結(jié)

示意圖

3. 鏈?zhǔn)酱鎯Y(jié)構(gòu)

實現(xiàn)方式：鏈表
下面地粪，我將主要講解其結(jié)構(gòu)特點 & 相關(guān)操作

3.1 結(jié)構(gòu)特點

示意圖

鏈表示意圖（以單鏈表為例）

示意圖
存儲元素說明示意圖

示意圖

下面將主要重點講解各種鏈表：（重點講解）單鏈表取募、雙向鏈表、循環(huán)鏈表蟆技、靜態(tài)鏈表

3.2 單鏈表

3.2.1 定義

每個結(jié)點只有1個指針域

3.2.2 示意圖

示意圖

3.2.3 操作（讀取玩敏、插入斗忌、刪除、整表創(chuàng)建旺聚、整表刪除）

讀取
算法思路：工作指針向后移

int j ;

// 1. 聲明1動態(tài)指針
LinkList p ; 

// 2. 讓p指向鏈表L的第一個結(jié)點
// L = 頭結(jié)點
p = L ->next

// 3. 設(shè)置計數(shù)器
j = 1;
while ( p && j<i ){

p = p->next织阳；// 指向下一個結(jié)點
++j;

}

// 直到到了i結(jié)點，直接取出
e = p->data

插入

通過遍歷找到i結(jié)點砰粹，生成一個空結(jié)點唧躲，然后插入

示意圖

刪除

示意圖

整表創(chuàng)建

示意圖
整表刪除

示意圖

單鏈表實現(xiàn)

public class UnidirectionalLinkedList<T> {

    /**
     * 設(shè)置結(jié)點結(jié)構(gòu)
     */
    // a. 結(jié)點結(jié)構(gòu)
    private class Node<T>{
        private T data;
        private Node<T> next ;
        public Node(T data){
            this.data = data;
        }
    }

    // b. 頭結(jié)點
    private Node<T> first;
    // c. 當(dāng)前結(jié)點
    private Node<T> currentNode;
    // d. 鏈表長度
    private int size;

    /**
     * 構(gòu)造函數(shù)
     * 作用：初始化結(jié)點
     */
    public UnidirectionalLinkedList(){
        currentNode = first = null;
        size = 0;
    }

    /**
     * 1. 添加結(jié)點
     * 內(nèi)容：在頭 / 尾 添加結(jié)點 & 在特定位置插入結(jié)點
     */

    // a. 在鏈表頭部加入1個結(jié)點
    // 即，把新加入的結(jié)點設(shè)置為第一結(jié)點
    public void addFirstNode(T data){

        // 1. 將需添加的內(nèi)容封裝成結(jié)點
        Node<T> newNode = new Node<T>(data);
        // 2. 將新添加結(jié)點的指針域指向舊第1個結(jié)點
        newNode.next = first;
        // 3. 將新添加結(jié)點設(shè)置為第1個結(jié)點
        first = newNode;
        // 4. 鏈表長度+1
        size++;
    }

    // b. 在鏈表尾部加入1個結(jié)點
    // 即碱璃，把新加入的結(jié)點設(shè)置為最后結(jié)點
    public void addNode(T data){
        // 1. 檢查當(dāng)前鏈表是否為空
        if (isEmpty()){
            addFirstNode(data);
            return;
        }
        // 2. 把當(dāng)前指針定位到最后一個結(jié)點
        locateNode(size-1);
        // 3. 將需添加的內(nèi)容封裝成結(jié)點
        currentNode.next = new Node<T>(data);
        // 4. 鏈表長度+1
        size++;
    }

    // c. 在鏈表中插入結(jié)點
    public T insertNode(int index, T data) {
        // 1. 檢查當(dāng)前鏈表是否為空
        if (isEmpty()){
            addFirstNode(data);
            return null;
        }

        // 2. 把當(dāng)前指針定位到需插入的結(jié)點位置
        locateNode(index);
        // 3. 將需添加的內(nèi)容封裝成結(jié)點
        Node<T> insertNode = new Node<T>(data);
        // 4. 把需插入結(jié)點位置的下1個結(jié)點 賦給 插入的結(jié)點
        insertNode.next = currentNode.next;
        // 5. 把插入結(jié)點 賦給 需插入的結(jié)點的位置
        currentNode.next = insertNode;
        // 6. 鏈表長度+1
        size++;
        // 7. 返回插入結(jié)點的數(shù)據(jù)
        return insertNode.data;
    }


    /**
     * 2. 刪除結(jié)點
     * 內(nèi)容：刪除第1個結(jié)點 & 刪除特定位置的結(jié)點
     */
    // a. 刪除第1個結(jié)點弄痹，并返回該結(jié)點數(shù)據(jù)
    public T removeFirstNode()  {
        // 1. 檢查當(dāng)前鏈表第一個結(jié)點是否為空
        if (first == null){
            try {
                throw new Exception("鏈表為空！");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        // 2. 獲取被刪除結(jié)點的數(shù)據(jù)
        T temp = first.data;
        // 3. 將第2個結(jié)點設(shè)置為第1個結(jié)點
        first = first.next;
        // 4. 鏈表長度減1
        size--;

        // 5. 返回被刪除結(jié)點的數(shù)據(jù)
        return temp;
    }


    // b. 刪除特定位置的結(jié)點,并將里面的數(shù)據(jù)返回
    public T removeNode(int index)  {
        // 1. 檢查當(dāng)前鏈表是否為空
        if (isEmpty()){
            try {
                throw new Exception("鏈表為空嵌器！");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        // 2. 把當(dāng)前指針（currentNode）定位到 需刪除結(jié)點（index）的前1個結(jié)點
        locateNode(index-1);
        // 3. 獲取被刪除結(jié)點的數(shù)據(jù)
        T temp = currentNode.next.data;
        // 4. 將需刪除結(jié)點（index）的前1個結(jié)點 的下1個結(jié)點 設(shè)置為 需刪除結(jié)點（index）的下1個結(jié)點
        currentNode.next = currentNode.next.next;
        // 5. 鏈表長度減1
        size--;
        // 6. 返回被刪除結(jié)點的數(shù)據(jù)
        return temp;
    }

    /**
     * 3. 獲取特定位置的結(jié)點
     * 內(nèi)容：將當(dāng)前指針（currentNode）定位到所需結(jié)點位置肛真、根據(jù)索引位置獲取結(jié)點數(shù)據(jù)
     */

    // a. 將當(dāng)前指針（currentNode）定位到所需結(jié)點位置
    private void locateNode(int index){
        // 1. 判斷指針是否越界
        if (index <0 && index >size){
            try {
                throw new IndexOutOfBoundsException("參數(shù)越界！");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        int i = 0;
        // 2. 通過遍歷鏈表爽航，尋找索引index所指結(jié)點
        for(currentNode = first; currentNode.next != null && i < index; i++){
            currentNode = currentNode.next;
        }
    }

    // b. 根據(jù)索引位置獲取結(jié)點數(shù)據(jù)
    public T getNode(int index)  {
        // 1. 判斷鏈表是否為空
        if (isEmpty()){
            try {
                throw new Exception("鏈表為空蚓让！");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        // 2. 把當(dāng)前指針（currentNode）定位到 所需索引位置（index）
        locateNode(index);
        // 3. 返回當(dāng)前指針的數(shù)據(jù)，即所需索引位置的數(shù)據(jù)
        return currentNode.data;
    }

    /**
     * 檢查當(dāng)前鏈表是否為空
     */
    public boolean isEmpty(){
        if (size == 0){
            return true;
        }else {
            return false;
        }
    }


    public static void main(String[] args){
        // 1. 創(chuàng)建鏈表 & 加入結(jié)點數(shù)據(jù)
        UnidirectionalLinkedList<Integer> list = new UnidirectionalLinkedList<Integer>();
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        list.addNode(4);
        list.addNode(5);

        // 2. 輸出當(dāng)前鏈表數(shù)據(jù)
        System.out.println("鏈表數(shù)據(jù)如下：");
        for (int i = 0; i < list.size;i++){
            
            try {

                System.out.print(list.getNode(i)+" ");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        System.out.println("-----------------------");


        // 3. 獲得某個位置結(jié)點的數(shù)據(jù)
        System.out.println("位置3的數(shù)據(jù)是：" + list.getNode(3));


        System.out.println("-----------------------");


        // 4. 插入結(jié)點：在位置4插入岳掐，數(shù)據(jù) = 66
        System.out.println("在位置4插入的data："+list.insertNode(3,66));
        System.out.println("插入后：");
        for (int i = 0; i < list.size;i++){
            try {
                System.out.print(list.getNode(i)+" ");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        System.out.println("-----------------------");

        // 5. 刪除結(jié)點
        System.out.println("刪除index為3的data："+list.removeNode(3));
        System.out.println("刪除后：");
        for (int i = 0; i < list.size;i++){
            try {
                System.out.print(list.getNode(i)+" ");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }


}

測試結(jié)果

鏈表數(shù)據(jù)如下：1 2 3 4 5 
-----------------------
位置3的數(shù)據(jù)是：4
-----------------------
在位置4插入的data：66
插入后：1 2 3 4 66 5 
-----------------------
刪除index為3的data：4
刪除后：1 2 3 66 5

3.3 循環(huán)鏈表

定義
將單鏈表的終端結(jié)點的指針指向頭結(jié)點凭疮、使得單鏈表頭尾相接、形成1個環(huán)

也稱單循環(huán)鏈表

示意圖

示意圖

3.4 雙向鏈表

3.4.1 定義

每個結(jié)點有2個指針域：1指向后驅(qū)結(jié)點元素串述、2指向前驅(qū)結(jié)點元素

即在單鏈表的結(jié)點中，再設(shè)置一個指向前驅(qū)結(jié)點的指針域

3.4.2 示意圖

示意圖

3.4.3 鏈表操作（插入& 刪除）

示意圖

注：插入 & 刪除都需要同時改變2個指針變量

3.4.4 特點

缺點：占用空間多 = 記錄2個指針
優(yōu)點：算法時間性能高 = 良好對稱性（前寞肖、后指針）

即纲酗，用空間換時間

3.5 靜態(tài)鏈表

示意圖

4. 存儲結(jié)構(gòu)對比

示意圖

5. 總結(jié)

本文主要講解了數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的線性表
下面我將繼續(xù)對 數(shù)據(jù)結(jié)構(gòu)進行講解，有興趣可以繼續(xù)關(guān)注Carson_Ho的簡書

歡迎關(guān)注Carson_Ho的簡書新蟆！

不定期分享關(guān)于安卓開發(fā)的干貨觅赊，追求短、平琼稻、快吮螺，但卻不缺深度。

請點贊帕翻！因為你的鼓勵是我寫作的最大動力鸠补！

相關(guān)文章閱讀
Android開發(fā)：最全面、最易懂的Android屏幕適配解決方案
 Android事件分發(fā)機制詳解：史上最全面嘀掸、最易懂
 Android開發(fā)：史上最全的Android消息推送解決方案
 Android開發(fā)：最全面紫岩、最易懂的Webview詳解
 Android開發(fā)：JSON簡介及最全面解析方法!
Android四大組件：BroadcastReceiver史上最全面解析
 Android四大組件：Service服務(wù)史上最全面解析

Carson帶你學(xué)數(shù)據(jù)結(jié)構(gòu)：手把手帶你深入學(xué)習(xí)線性表