常用的Java資料結構知識點彙總

2022-03-02 16:01:22

1. 資料結構分類

按照線性和非線性可以將Java資料結構分為兩大類：

①線性資料結構：陣列、連結串列、棧、佇列
②非線性資料結構：樹、堆、雜湊表、圖

2. 線性資料結構

2.1 陣列

陣列是一種將元素儲存於連續記憶體空間的資料結構，並且要求元素的型別相同。

// 定義一個陣列長度為5的陣列array
int[] array = new int[5];
// 為陣列的元素賦值
array[0] = 4;
array[1] = 3;
array[2] = 2;
array[3] = 1;
array[4] = 0;

直接賦值：

// 一種方式
int[] array = {4, 3, 2, 1, 0};
// 另一種方式
int[] array = new int[]{4, 3, 2, 1, 0};

2.2 可變陣列

可變陣列是在一般陣列的基礎上結合擴容機制進行改進的具有靈活長度的陣列。

// 定義一個可變陣列
List<Integer> changeable_array = new ArrayList<>();
// 向可變陣列的尾部新增元素
array.add(4);
array.add(3);
array.add(2);
array.add(1);
array.add(0);

2.3 連結串列

連結串列可以定義為一個類，該類的包含兩個成員變數的：節點的值val、後繼節點的參照next。節點是構成連結串列的基本單位，這種資料結構在記憶體空間的儲存地址是非連續的。

// 定義連結串列類
class ListNode {
    // 節點的值
    int val;
    // 後繼節點的參照
    ListNode next;
    ListNode(int x){
        this. val = x;
    }
}

構建多個連結串列類的物件，並構建這些節點範例之間的參照指向：

①節點head的節點值為2，其後繼節點是值為1的節點n2。
②節點n2的節點值為1，其後繼節點是值為0的節點n3。
③該連結串列的頭節點為head，尾節點為n3。

// 範例化節點
ListNode head = new ListNode(2);
ListNode n2 = new ListNode(1);
ListNode n3 = new ListNode(0);
// 構建三個節點之間的參照指向
head.next = n2;
n2.next = n3;

2.4 棧

棧是一種抽象資料結構，特點是“後進先出”，可由陣列或者連結串列實現。

// 定義一個棧，使用Java的Vector類的子類Stack
Stack<Integer> stack = new Stack<>();

入棧操作 push()：

// 元素0入棧
stack.push(0);
// 元素1入棧
stack.push(1);

出棧操作 pop()：

// 元素1出棧
stack.pop();
// 元素0出棧
stack.pop();

在Java中可以使用Stack、ArrayDeque、LinkedList實現棧，但通常情況下，不推薦使用Vector類以及其子類Stack，

一般使用LinkedList來實現棧：

LinkedList<Integer> stack = new LinkedList<>();

入棧操作 addLast()：

// 元素0入棧
stack.addLast(0);
// 元素1入棧
stack.addLast(1);

出棧操作 removeLast()：

// 元素1出棧
stack.removeLast();
// 元素0入棧
stack.removeLast();

2.5 佇列

佇列是一種抽象資料結構，特點是“先進先出”，可由連結串列實現。
LinkedList類實現了Queue介面，因此可以把LinkedList當成Queue來用。

Queue<Integer> queue = new LinkedList<>();

入隊操作 offer()：

// 元素0入隊
queue.offer(0);
// 元素1入隊
queue.offer(1);

出隊操作poll()，該函數的返回值為出隊的那個元素：

// 元素0出隊
queue.poll();
// 元素1出隊
queue.poll();

element()：返回第一個元素
peek()：返回第一個元素
區別：在佇列元素為空的情況下，element() 方法會丟擲NoSuchElementException異常，peek() 方法只會返回 null。

queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
queue.offer("e");
queue.element(); //輸出a
queue.peek(); //輸出a

3. 非線性資料結構

3.1 樹

樹是一種非線性的資料結構，可分為二元樹和多叉樹。
二元樹可定義為一個類，該類包含三個成員變數：節點值val、左子節點left、右子節點right。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        this.val = x;
    }
}

二元樹各節點範例化：

// 根節點root
TreeNode root = new TreeNode(0);
TreeNode n2 = new TreeNode(1);
TreeNode n3 = new TreeNode(2);
TreeNode n4 = new TreeNode(3);
TreeNode n5 = new TreeNode(4);

構建二元樹各節點之間的參照指向：

// 根節點的左子節點為n2，其值為1
root.left = n2;
// 根節點的右子節點為n3，其值為2
root.right = n3;
// 節點n2的左子節點為n4，其值為3
n2.left = n4;
// 節點n2的右子節點為n5，其值為4
n2.right = n5;

3.2 圖

圖是一種非線性資料結構，由頂點（vertex）和邊（edge）組成，每條邊都連線著兩個頂點。
圖分為有向圖和無向圖。

以無向圖為例：

①頂點集合： vertices = {1, 2, 3, 4, 5}
②邊集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

（1）圖的表示方法：鄰接矩陣（無向圖的鄰接矩陣是一個斜對角對稱矩陣）
⭐鄰接矩陣適用於儲存稠密圖，即頂點較多、邊較少。

// 儲存圖的頂點
int[] vertices = {1, 2, 3, 4, 5};
// 儲存圖的邊
int[][] edges = {{0, 1, 1, 1, 1},
                 {1, 0, 0, 1, 0},
                 {1, 0, 0, 0, 1},
                 {1, 1, 0, 0, 1},
                 {1, 0, 1, 1, 0}};
int[] vertices = {1, 2, 3, 4, 5};

（2）圖的表示方法：鄰接表

⭐鄰接表適用於儲存稀疏圖，即頂點多、邊較少。

// 儲存圖的頂點
int[] vertices = {1, 2, 3, 4, 5};
// 儲存邊的集合
List<List<Integer>> edges = new ArrayList<>();
// edge[i]表示圖的頂點i對應的邊集合
List<Integer> edge_1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
List<Integer> edge_2 = new ArrayList<>(Arrays.asList(0, 3));
List<Integer> edge_3 = new ArrayList<>(Arrays.asList(0, 4));
List<Integer> edge_4 = new ArrayList<>(Arrays.asList(0, 1, 4));
List<Integer> edge_5 = new ArrayList<>(Arrays.asList(0, 2, 3));
edges.add(edge_1);
edges.add(edge_2);
edges.add(edge_3);
edges.add(edge_4);
edges.add(edge_5);

3.3 雜湊表

雜湊表是一種非線性的資料結構，實質是將鍵（key）通過Hash函數完成到值（value）的對映。

// 初始化雜湊表
Map<String, Integer> dict = new HashMap<>();

新增鍵 - 值對：

dict.put("python", 101);
dict.put("c", 102);
dict.put("java", 103);

通過鍵 key查詢對應的值 value：

dict.get("python");    // 101
dict.get("c");        // 102
dict.get("java");    // 103

設計一個簡單的Hash函數構建程式語言 ==> 編號的對映，構建一個雜湊表（假設不考慮低碰撞率、高魯棒性）：

String[] program_lang = {"python", "c", "java"};

int hash(int idx){
    int index = (idx -1 % 100);
    return index;
}

names[hash(101)];    // python
names[hash(101)];    // c
names[hash(101)];    // java

3.4 堆

（1）堆是一種基於完全二元樹的資料結構，可由陣列實現。
完全二元樹：一棵深度為k的有n個結點的二元樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1 ≤ i ≤ n）的結點與滿二元樹中編號為i的結點在二元樹中的位置相同，則這棵二元樹稱為完全二元樹。
（2）基於堆的原理實現的排序演演算法稱為堆排序。
（3）基於堆實現的資料結構稱為優先佇列。
（4）堆分為大頂堆、小頂堆：①大頂堆：任意節點的值不大於其父節點的值，即根節點最大，任意子節點小於等於父節點。②小頂堆：任意節點的值不小於其父節點的值，即根節點最小，任意子節點大於等於父節點。

// 初始化小頂堆，操作為 優先佇列
Queue<Integer> heap = new PriorityQueue<>();

元素入堆add()：

// 元素入堆
heap.add(0);
heap.add(4);
heap.add(2);
heap.add(6);
heap.add(8);

元素出堆 poll()：

// 元素出堆（從小到大）
heap.poll(); // -> 0
heap.poll(); // -> 2
heap.poll(); // -> 4
heap.poll(); // -> 6
heap.poll(); // -> 8

到此這篇關於常用的Java資料結構知識點彙總的文章就介紹到這了,更多相關常用的Java資料結構分享內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！