Java 原生實現常見數據結構

一、引言

在計算機科學的廣袤領域中，數據結構猶如構建高樓大廈的基石，其重要性不言而喻。它們為數據的組織、存儲與操作提供了標準化的方式，直接影響著算法的效率以及軟件系統的整體性能。Java，作為一門廣泛應用于企業級開發、移動應用開發、大數據處理等眾多領域的編程語言，雖然其類庫已經內置了豐富的數據結構實現，但深入探究如何用 Java 原生代碼實現這些數據結構，對于每一位渴望提升編程內功、透徹理解計算機底層原理的開發者來說，都具有不可估量的價值。這不僅能夠加深我們對數據結構本質的認識，更能在面對復雜多變的業務需求和性能挑戰時，游刃有余地進行定制化開發與優化。本文將帶領讀者踏上一段深入的編程之旅，詳細介紹如何用 Java 原生代碼實現幾種常見且極為重要的數據結構——數組、鏈表、棧和隊列，并對它們的特性、應用場景以及性能特點進行全面剖析。

二、數組（Array）

（一）概念

數組，作為一種最為基礎和常用的線性數據結構，在內存中呈現為一段連續的存儲空間。它猶如一列整齊排列的儲物柜，每個儲物柜都有其唯一的編號（索引），從 0 開始，依次遞增。這些儲物柜專門用于存放相同類型的數據元素，例如整數、浮點數或者對象引用等。這種連續存儲的特性使得數組在隨機訪問元素時具有極高的效率，只需通過索引，就能在常量時間內迅速定位并獲取到指定位置的元素。然而，數組的長度在創建之初就已確定，這就好比儲物柜的數量一旦確定就難以輕易更改，當需要插入或刪除元素時，尤其是在數組中間位置進行操作時，往往需要移動大量后續元素，這無疑會帶來較大的時間開銷。

（二）代碼實現

public class MyArray {private int[] data; // 存儲數組元素的內部數組private int size; // 當前數組中元素的個數// 構造函數，初始化數組的容量public MyArray(int capacity) {data = new int[capacity];size = 0;}// 獲取數組中元素的個數public int getSize() {return size;}// 獲取數組的容量public int getCapacity() {return data.length;}// 判斷數組是否為空public boolean isEmpty() {return size == 0;}// 在數組末尾添加元素public void addLast(int element) {add(size, element);}// 在數組指定位置添加元素public void add(int index, int element) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index > size) {throw new IllegalArgumentException("索引不合法");}// 當數組已滿時，進行擴容操作if (size == data.length) {resize(2 * data.length);}// 將指定位置及之后的元素向后移動一位，為新元素騰出空間for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = element;size++;}// 獲取指定位置的元素public int get(int index) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index >= size) {throw new IllegalArgumentException("索引不合法");}return data[index];}// 修改指定位置的元素public void set(int index, int newElement) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index >= size) {throw new IllegalArgumentException("索引不合法");}data[index] = newElement;}// 查找元素是否在數組中存在，返回索引，不存在返回 -1public int contains(int element) {for (int i = 0; i < size; i++) {if (data[i] == element) {return i;}}return -1;}// 刪除指定位置的元素，并返回被刪除的元素public int remove(int index) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index >= size) {throw new IllegalArgumentException("索引不合法");}int ret = data[index];// 將指定位置之后的元素向前移動一位，覆蓋要刪除的元素for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;// 當數組元素數量過少時，進行縮容操作，以節省內存空間if (size == data.length / 4 && data.length / 2!= 0) {resize(data.length / 2);}return ret;}// 從數組末尾刪除元素public int removeLast() {return remove(size - 1);}// 數組擴容或縮容方法private void resize(int newCapacity) {int[] newData = new int[newCapacity];// 將原數組中的元素復制到新數組中for (int i = 0; i < size; i++) {newData[i] = data[i];}data = newData;}
}

可以通過以下方式測試這個自定義數組類：

public class Main {public static void main(String[] args) {MyArray myArray = new MyArray(10);myArray.addLast(1);myArray.addLast(2);myArray.add(1, 3);System.out.println("數組元素個數: " + myArray.getSize());System.out.println("數組容量: " + myArray.getCapacity());System.out.println("索引為 1 的元素: " + myArray.get(1));myArray.remove(1);System.out.println("刪除元素后數組元素個數: " + myArray.getSize());}
}

三、鏈表（Linked List）

（一）概念

鏈表，同樣屬于線性數據結構的范疇，但與數組截然不同。它就像是一條由多個節點連接而成的鏈條，每個節點恰似鏈條上的一環，包含了數據元素以及指向下一個節點的指針（在單鏈表的情況下）。鏈表的節點在內存中并非連續存儲，而是通過指針相互鏈接，這種離散存儲的方式使得鏈表在插入和刪除元素時具有獨特的優勢，只需調整相關節點的指針指向，無需像數組那樣大規模地移動元素，從而在頻繁進行插入和刪除操作的場景中表現出色。然而，鏈表在隨機訪問元素方面相對較弱，因為要訪問某個特定位置的元素，需要從鏈表頭開始逐個遍歷節點，直到找到目標節點，這一過程的時間復雜度為 O(n)，其中 n 為鏈表的長度。

（二）代碼實現（以單鏈表為例）

// 定義鏈表節點類
class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;this.next = null;}
}// 自定義單鏈表類
public class MyLinkedList {private ListNode head; // 頭節點private int size; // 鏈表節點個數// 獲取鏈表長度public int getSize() {return size;}// 判斷鏈表是否為空public boolean isEmpty() {return size == 0;}// 在鏈表頭部添加節點public void addFirst(int val) {ListNode newNode = new ListNode(val);newNode.next = head;head = newNode;size++;}// 在鏈表指定位置添加節點public void add(int index, int val) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index > size) {throw new IllegalArgumentException("索引不合法");}if (index == 0) {addFirst(val);return;}ListNode prev = head;// 找到要插入位置的前一個節點for (int i = 0; i < index - 1; i++) {prev = prev.next;}ListNode newNode = new ListNode(val);newNode.next = prev.next;prev.next = newNode;size++;}// 在鏈表末尾添加節點public void addLast(int val) {add(size, val);}// 獲取指定位置的節點的值public int get(int index) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index >= size) {throw new IllegalArgumentException("索引不合法");}ListNode cur = head;// 遍歷鏈表，找到指定位置的節點for (int i = 0; i < index; i++) {cur = cur.next;}return cur.val;}// 修改指定位置節點的值public int set(int index, int newVal) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index >= size) {throw new IllegalArgumentException("索引不合法");}ListNode cur = head;// 遍歷鏈表，找到指定位置的節點for (int i = 0; i < index; i++) {cur = cur.next;}int oldVal = cur.val;cur.val = newVal;return oldVal;}// 查找元素是否在鏈表中存在，返回索引，不存在返回 -1public int contains(int val) {ListNode cur = head;for (int i = 0; i < size; i++) {if (cur.val == val) {return i;}cur = cur.next;}return -1;}// 刪除指定位置的節點，并返回被刪除節點的值public int remove(int index) {// 檢查索引的合法性，若索引不合法則拋出異常if (index < 0 || index >= size) {throw new IllegalArgumentException("索引不合法");}if (index == 0) {return removeFirst();}ListNode prev = head;// 找到要刪除位置的前一個節點for (int i = 0; i < index - 1; i++) {prev = prev.next;}ListNode retNode = prev.next;prev.next = retNode.next;size--;return retNode.val;}// 從鏈表頭部刪除節點，并返回被刪除節點的值public int removeFirst() {if (isEmpty()) {throw new IllegalArgumentException("鏈表為空");}ListNode retNode = head;head = head.next;size--;return retNode.val;}// 從鏈表末尾刪除節點，并返回被刪除節點的值public int removeLast() {return remove(size - 1);}
}

以下是測試代碼：

public class Main {public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.addFirst(1);myLinkedList.addLast(2);myLinkedList.add(1, 3);System.out.println("鏈表長度: " + myLinkedList.getSize());System.out.println("索引為 1 的節點值: " + myLinkedList.get(1));myLinkedList.remove(1);System.out.println("刪除節點后鏈表長度: " + myLinkedList.getSize());}
}

四、棧（Stack）

（一）概念

棧，作為一種特殊的線性數據結構，遵循后進先出（LIFO）的操作原則。可以將其形象地比喻為一個只能從頂部放入和取出物品的儲物箱。棧只提供了兩個基本操作：入棧（push），即將元素壓入棧頂；出棧（pop），即將棧頂元素彈出。這種特性使得棧在處理具有嵌套結構或需要回溯的問題時大顯身手，例如函數調用棧、表達式求值以及括號匹配等場景。當一個函數被調用時，其相關的局部變量、返回地址等信息就會被壓入棧中，當函數執行完畢后，這些信息又會按照后進先出的順序從棧中彈出，從而實現函數調用的正確返回和資源的回收。

（二）代碼實現（基于數組實現棧）

public class MyStack {private int[] data; // 存儲棧元素的內部數組private int top; // 棧頂指針，指向棧頂元素的下一個位置// 構造函數，初始化棧的容量public MyStack(int capacity) {data = new int[capacity];top = 0;}// 判斷棧是否為空public boolean isEmpty() {return top == 0;}// 獲取棧中元素的個數public int size() {return top;}// 入棧操作public void push(int element) {// 當棧已滿時，進行擴容操作if (top == data.length) {resize(2 * data.length);}data[top++] = element;}// 出棧操作，返回彈出的棧頂元素public int pop() {// 檢查棧是否為空，若為空則拋出異常if (isEmpty()) {throw new IllegalArgumentException("棧為空");}int ret = data[top - 1];top--;// 當棧中元素數量過少時，進行縮容操作，以節省內存空間if (top == data.length / 4 && data.length / 2!= 0) {resize(data.length / 2);}return ret;}// 獲取棧頂元素，但不彈出public int peek() {// 檢查棧是否為空，若為空則拋出異常if (isEmpty()) {throw new IllegalArgumentException("棧為空");}return data[top - 1];}// 棧的擴容或縮容方法private void resize(int newCapacity) {int[] newData = new int[newCapacity];// 將原棧中的元素復制到新棧中for (int i = 0; i < top; i++) {newData[i] = data[i];}data = newData;}
}

測試代碼示例：

public class Main {public static void main(String[] args) {MyStack myStack = new MyStack(10);myStack.push(1);myStack.push(2);System.out.println("棧頂元素: " + myStack.peek());System.out.println("彈出元素: " + myStack.pop());System.out.println("棧是否為空: " + myStack.isEmpty());}
}

五、隊列（Queue）

（一）概念

隊列，與棧類似，也是一種線性數據結構，但它遵循先進先出（FIFO）的原則。就像日常生活中的排隊場景，先到達的人先接受服務。隊列提供了兩個核心操作：入隊（enqueue），即在隊尾添加元素；出隊（dequeue），即從隊頭取出元素。隊列在許多實際應用場景中有著廣泛的應用，例如任務調度系統中，任務按照提交的先后順序依次被處理；消息隊列中，消息按照發送的順序被接收和處理，以確保消息的順序性和公平性。

（二）代碼實現（基于鏈表實現隊列，也可以基于數組實現）

// 定義隊列節點類（與鏈表節點類似）
class QueueNode {int val;QueueNode next;QueueNode(int val) {this.val = val;this.next = null;}
}public class MyQueue {private QueueNode head; // 隊頭節點private QueueNode tail; // 隊尾節點private int size; // 隊列中元素的個數// 判斷隊列是否為空public boolean isEmpty() {return size == 0;}// 獲取隊列中元素的個數public int getSize() {return size;}// 入隊操作，在隊尾添加元素public void enqueue(int element) {QueueNode newNode = new QueueNode(element);if (isEmpty()) {head = tail = newNode;} else {tail.next = newNode;tail = newNode;}size++;}// 出隊操作，從隊頭取出元素并返回public int dequeue() {if (isEmpty()) {throw new IllegalArgumentException("隊列為空");}int ret = head.val;head = head.next;if (head == null) {tail = null;}size--;return ret;}//