快捷導(dǎo)航

常用的Java數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)匯總

更新時(shí)間：2022年03月03日 16:13:55 作者：LeBron?Le

這篇文章主要介紹了常用的Java數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)匯總，數(shù)據(jù)結(jié)構(gòu)分線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)，下面對(duì)此作詳細(xì)介紹，需要的小伙伴可以參考一下，希望對(duì)你的學(xué)習(xí)或工作有所幫助

1. 數(shù)據(jù)結(jié)構(gòu)分類

按照線性和非線性可以將Java數(shù)據(jù)結(jié)構(gòu)分為兩大類：

①線性數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列
②非線性數(shù)據(jù)結(jié)構(gòu)：樹、堆、散列表、圖

2. 線性數(shù)據(jù)結(jié)構(gòu)

2.1 數(shù)組

數(shù)組是一種將元素存儲(chǔ)于連續(xù)內(nèi)存空間的數(shù)據(jù)結(jié)構(gòu)，并且要求元素的類型相同。

// 定義一個(gè)數(shù)組長度為5的數(shù)組array
int[] array = new int[5];
// 為數(shù)組的元素賦值
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 可變數(shù)組

可變數(shù)組是在一般數(shù)組的基礎(chǔ)上結(jié)合擴(kuò)容機(jī)制進(jìn)行改進(jìn)的具有靈活長度的數(shù)組。

// 定義一個(gè)可變數(shù)組
List<Integer> changeable_array = new ArrayList<>();
// 向可變數(shù)組的尾部添加元素
array.add(4);
array.add(3);
array.add(2);
array.add(1);
array.add(0);

2.3 鏈表

鏈表可以定義為一個(gè)類，該類的包含兩個(gè)成員變量的：節(jié)點(diǎn)的值val、后繼節(jié)點(diǎn)的引用next。節(jié)點(diǎn)是構(gòu)成鏈表的基本單位，這種數(shù)據(jù)結(jié)構(gòu)在內(nèi)存空間的存儲(chǔ)地址是非連續(xù)的。

// 定義鏈表類
class ListNode {
?? ?// 節(jié)點(diǎn)的值
?? ?int val;
?? ?// 后繼節(jié)點(diǎn)的引用
?? ?ListNode next;
?? ?ListNode(int x){
?? ??? ?this. val = x;
?? ?}
}

構(gòu)建多個(gè)鏈表類的對(duì)象，并構(gòu)建這些節(jié)點(diǎn)實(shí)例之間的引用指向：

①節(jié)點(diǎn)head的節(jié)點(diǎn)值為2，其后繼節(jié)點(diǎn)是值為1的節(jié)點(diǎn)n2。
②節(jié)點(diǎn)n2的節(jié)點(diǎn)值為1，其后繼節(jié)點(diǎn)是值為0的節(jié)點(diǎn)n3。
③該鏈表的頭節(jié)點(diǎn)為head，尾節(jié)點(diǎn)為n3。

// 實(shí)例化節(jié)點(diǎn)
ListNode head = new ListNode(2);
ListNode n2 = new ListNode(1);
ListNode n3 = new ListNode(0);
// 構(gòu)建三個(gè)節(jié)點(diǎn)之間的引用指向
head.next = n2;
n2.next = n3;

2.4 棧

棧是一種抽象數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是“后進(jìn)先出”，可由數(shù)組或者鏈表實(shí)現(xiàn)。

// 定義一個(gè)棧，使用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實(shí)現(xiàn)棧，但通常情況下，不推薦使用Vector類以及其子類Stack，

一般使用LinkedList來實(shí)現(xiàn)棧：

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

入棧操作 addLast()：

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

出棧操作 removeLast()：

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

2.5 隊(duì)列

隊(duì)列是一種抽象數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是“先進(jìn)先出”，可由鏈表實(shí)現(xiàn)。
LinkedList類實(shí)現(xiàn)了Queue接口，因此可以把LinkedList當(dāng)成Queue來用。

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

入隊(duì)操作 offer()：

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

出隊(duì)操作poll()，該函數(shù)的返回值為出隊(duì)的那個(gè)元素：

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

element()：返回第一個(gè)元素
peek()：返回第一個(gè)元素
區(qū)別：在隊(duì)列元素為空的情況下，element() 方法會(huì)拋出NoSuchElementException異常，peek() 方法只會(huì)返回 null。

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

3. 非線性數(shù)據(jù)結(jié)構(gòu)

3.1 樹

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，可分為二叉樹和多叉樹。
二叉樹可定義為一個(gè)類，該類包含三個(gè)成員變量：節(jié)點(diǎn)值val、左子節(jié)點(diǎn)left、右子節(jié)點(diǎn)right。

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

二叉樹各節(jié)點(diǎn)實(shí)例化：

// 根節(jié)點(diǎn)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);

構(gòu)建二叉樹各節(jié)點(diǎn)之間的引用指向：

// 根節(jié)點(diǎn)的左子節(jié)點(diǎn)為n2，其值為1
root.left = n2;
// 根節(jié)點(diǎn)的右子節(jié)點(diǎn)為n3，其值為2
root.right = n3;
// 節(jié)點(diǎn)n2的左子節(jié)點(diǎn)為n4，其值為3
n2.left = n4;
// 節(jié)點(diǎn)n2的右子節(jié)點(diǎn)為n5，其值為4
n2.right = n5;

3.2 圖

圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)（vertex）和邊（edge）組成，每條邊都連接著兩個(gè)頂點(diǎn)。
圖分為有向圖和無向圖。

以無向圖為例：

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

（1）圖的表示方法：鄰接矩陣（無向圖的鄰接矩陣是一個(gè)斜對(duì)角對(duì)稱矩陣）
?鄰接矩陣適用于存儲(chǔ)稠密圖，即頂點(diǎn)較多、邊較少。

// 存儲(chǔ)圖的頂點(diǎn)
int[] vertices = {1, 2, 3, 4, 5};
// 存儲(chǔ)圖的邊
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）圖的表示方法：鄰接表

?鄰接表適用于存儲(chǔ)稀疏圖，即頂點(diǎn)多、邊較少。

// 存儲(chǔ)圖的頂點(diǎn)
int[] vertices = {1, 2, 3, 4, 5};
// 存儲(chǔ)邊的集合
List<List<Integer>> edges = new ArrayList<>();
// edge[i]表示圖的頂點(diǎn)i對(duì)應(yīng)的邊集合
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 散列表

散列表是一種非線性的數(shù)據(jù)結(jié)構(gòu)，實(shí)質(zhì)是將鍵（key）通過Hash函數(shù)完成到值（value）的映射。

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

添加鍵 - 值對(duì)：

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

通過鍵 key查找對(duì)應(yīng)的值 value：

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

設(shè)計(jì)一個(gè)簡單的Hash函數(shù)構(gòu)建編程語言 ==> 編號(hào) 的映射，構(gòu)建一個(gè)散列表（假設(shè)不考慮低碰撞率、高魯棒性）：

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）堆是一種基于完全二叉樹的數(shù)據(jù)結(jié)構(gòu)，可由數(shù)組實(shí)現(xiàn)。
完全二叉樹：一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1 ≤ i ≤ n）的結(jié)點(diǎn)與滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。
（2）基于堆的原理實(shí)現(xiàn)的排序算法稱為堆排序。
（3）基于堆實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)稱為優(yōu)先隊(duì)列。
（4）堆分為大頂堆、小頂堆：①大頂堆：任意節(jié)點(diǎn)的值不大于其父節(jié)點(diǎn)的值，即根節(jié)點(diǎn)最大，任意子節(jié)點(diǎn)小于等于父節(jié)點(diǎn)。②小頂堆：任意節(jié)點(diǎn)的值不小于其父節(jié)點(diǎn)的值，即根節(jié)點(diǎn)最小，任意子節(jié)點(diǎn)大于等于父節(jié)點(diǎn)。

// 初始化小頂堆，操作為 優(yōu)先隊(duì)列
Queue<Integer> heap = new PriorityQueue<>();

元素入堆a(bǔ)dd()：

// 元素入堆
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

到此這篇關(guān)于常用的Java數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)匯總的文章就介紹到這了,更多相關(guān)常用的Java數(shù)據(jù)結(jié)構(gòu)分享內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: