「Java 數據結構全面解讀」：從基礎到進階的實戰指南
數據結構是程序設計中的核心部分，用于組織和管理數據。Java 提供了豐富的集合框架和工具類，涵蓋了常見的數據結構如數組、鏈表、棧、隊列和樹等。本文將系統性地介紹這些數據結構的概念、特點以及在 Java 中的實現，并通過代碼示例進行演示。
一、數據結構基礎概念
數據結構研究的是數據的邏輯結構和物理結構，以及它們之間的關系。
1.1 數據的邏輯結構
數據的邏輯結構反映了數據元素之間的邏輯關系，而與存儲位置無關。常見邏輯結構包括：
- 散列結構：元素之間除了“同屬一個集合”外，沒有其他關系。
- 線性結構：元素之間存在一對一的關系，例如數組、鏈表。
- 樹形結構：元素之間存在一對多的關系，例如二叉樹。
- 圖形結構：元素之間存在多對多的關系。
1.2 數據的物理結構
數據的物理結構描述了數據在計算機內存中的存儲方式，主要有：
- 數組結構：元素在內存中是連續存儲的，即元素存儲在一整塊連續的存儲空間中，此時根據索引的查詢效率是非常高的，因為可以根據下標索引直接一步到位找到元素位置，如果在數組末尾添加和刪除元素效率也非常高。缺點是，如果事先申請足夠大的內存空間，可能造成空間浪費，如果事先申請較小的內存空間，可能造成頻繁擴容導致元素頻繁搬家。另外，在數組中間添加、刪除元素操作，就需要移動元素，此時效率也要打折。
- 鏈式結構：元素在內存中是不要求連續存儲的，但是元素是封裝在結點當中的，結點中需要存儲元素數據，以及相關結點對象的引用地址。結點與結點之間可以是一對一的關系，也可以一對多的關系，比如：鏈表、樹等。遍歷鏈式結構只能從頭遍歷，對于較長的鏈表來說查詢效率不高，對于樹結構來說，查詢效率比鏈表要高一點，因為每次可以確定一個分支，從而排除其他分支，但是相對于數組來說，還是數組[下標]的方式更快。樹的實現方式有很多種，無非就是在添加/刪除效率 與 查詢效率之間權衡。
- 索引結構：元素在內存中是不要求連續存儲的，但是需要有單獨的一個索引表來記錄每一個元素的地址，這種結構根據索引的查詢效率很高，但是需要額外存儲和維護索引表。。
- 哈希結構：元素的存儲位置需要通過其hashCode值來計算，查詢效率也很多，但是要考慮和解決好哈希沖突問題。
數據結構和算法是一門完整并且復雜的課程
二、Java 中常見的數據結構實現
Java 提供了豐富的數據結構支持，包括動態數組、鏈表、棧、隊列和樹等。這些數據結構主要通過 java.util 包中的類實現。
2.1 數組
動態數組特點
邏輯結構特點：線性結構
物理結構特點：
- 申請內存：一次申請一大段連續的空間，一旦申請到了，內存就固定了。
- 存儲特點：所有數據存儲在這個連續的空間中，數組中的每一個元素都是一個具體的數據（或對象），所有數據都緊密排布，不能有間隔。
例如：整型數組
例如：對象數組
自定義動態數組(拓展)示例代碼
package com.test.list;import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;public class MyArrayList<E> implements Iterable<E>{private Object[] all;private int total;public MyArrayList(){all = new Object[10];}public void add(E e) {ensureCapacityEnough();all[total++] = e;}private void ensureCapacityEnough() {if(total >= all.length){all = Arrays.copyOf(all, all.length + (all.length>>1));}}public void insert(int index, E value) {//是否需要擴容ensureCapacityEnough();//添加元素的下標檢查addCheckIndex(index);if(total-index > 0) {System.arraycopy(all, index, all, index+1, total-index);}all[index]=value;total++;}private void addCheckIndex(int index) {if(index<0 || index>total){throw new IndexOutOfBoundsException(index+"越界");}}public void delete(E e) {int index = indexOf(e);if(index==-1){throw new NoSuchElementException(e+"不存在");}delete(index);}public void delete(int index) {//刪除元素的下標檢查checkIndex(index);if(total-index-1 > 0) {System.arraycopy(all, index+1, all, index, total-index-1);}all[--total] = null;}private void checkIndex(int index) {if(index<0 || index>total){throw new IndexOutOfBoundsException(index+"越界");}}public void update(int index, E value) {//更新修改元素的下標檢查checkIndex(index);all[index] = value;}public void update(E old, E value) {int index = indexOf(old);if(index!=-1){update(index, value);}}public boolean contains(E e) {return indexOf(e) != -1;}public int indexOf(E e) {int index = -1;if(e==null){for (int i = 0; i < total; i++) {if(e == all[i]){index = i;break;}}}else{for (int i = 0; i < total; i++) {if(e.equals(all[i])){index = i;break;}}}return index;}public E get(int index) {//獲取元素的下標檢查checkIndex(index);return (E) all[index];}public int size() {return total;}public Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private int cursor;@Overridepublic boolean hasNext() {return cursor!=total;}@Overridepublic E next() {return (E) all[cursor++];}@Overridepublic void remove() {MyArrayList.this.delete(--cursor);}}
}
測試類
package com.test.list;import java.util.Iterator;public class TestMyArrayList {public static void main(String[] args) {MyArrayList<String> my = new MyArrayList<>();my.add("hello");my.add("java");my.add("java");my.add("world");my.add(null);my.add(null);my.add("list");my.add("data");System.out.println("元素個數：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("-------------------------");System.out.println("在[1]插入JAVA移動技術棧后：");my.insert(1, "JAVA移動技術棧");System.out.println("元素個數：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("--------------------------");System.out.println("刪除[1]位置的元素后：");my.delete(1);System.out.println("元素個數：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("刪除null元素后：");my.delete(null);System.out.println("元素個數：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("------------------------------");System.out.println("替換[3]位置的元素為JAVA移動技術棧后：");my.update(3, "JAVA移動技術棧");System.out.println("元素個數：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("替換java為JAVA后：");my.update("java", "JAVA");System.out.println("元素個數：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("------------------------------------");System.out.println("是否包含java：" +my.contains("java"));System.out.println("java的位置：" + my.indexOf("java"));System.out.println("haha的位置：" + my.indexOf("haha"));System.out.println("[0]位置元素是：" + my.get(0));System.out.println("------------------------------------");System.out.println("刪除字符串長度>4的元素后：");Iterator<String> iterator = my.iterator();while(iterator.hasNext()) {String next = iterator.next();if(next != null && next.length()>4) {iterator.remove();}}System.out.println("元素個數：" + my.size());for (String string : my) {System.out.println(string);}}
}
2.2 鏈表
鏈表特點
- 數據存儲在結點中，結點通過指針連接。
- 插入和刪除效率高，查詢效率低。
- Java 提供了
LinkedList類實現鏈表，支持雙向鏈表。
示例代碼
import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {LinkedList<String> linkedList = new LinkedList<>();linkedList.add("A");linkedList.add("B");linkedList.add("C");System.out.println(linkedList); // 輸出：[A, B, C]}
}
2.3 棧
棧特點
- 先進后出（FILO） 或 后進先出（LIFO）：最后插入的元素最先被移除。
- 棧只是邏輯結構，其物理結構可以是數組，也可以是鏈表，即棧結構分為順序棧和鏈式棧。
- 核心類庫中的棧結構有
Stack和LinkedList。Stack就是順序棧，它是Vector的子類，而LinkedList是鏈式棧。
核心操作方法
peek()：查看棧頂元素，不彈出。pop()：彈出棧頂元素。push(E e)：壓入棧頂。
示例代碼
import java.util.Stack;public class StackExample {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(10);stack.push(20);stack.push(30);System.out.println(stack.pop()); // 輸出：30System.out.println(stack.peek()); // 輸出：20}
}
自定義單鏈表（拓展）
package com.test.list;import java.util.Iterator;public class MyOneWayLinkedList<E> implements Iterable<E>{private Node head;private int total;public void add(E e){Node newNode = new Node(e, null);if(head == null){head = newNode;}else{Node node = head;while(node.next!=null){node = node.next;}node.next = newNode;}total++;}private Node[] findNodes(Object obj){Node[] result = new MyOneWayLinkedList.Node[2];Node node = head;Node find = null;Node beforeFind = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}beforeFind = node;node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}beforeFind = node;node = node.next;}}result[0] = beforeFind;result[1] = find;return result;}public void delete(Object obj){Node[] nodes = findNodes(obj);Node beforeFind = nodes[0];Node find = nodes[1];if(find != null){if(beforeFind == null){head = find.next;}else {beforeFind.next = find.next;}total--;}}private Node findNode(Object obj){return findNodes(obj)[1];}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value) {Node find = findNode(old);if(find != null){find.data = value;}}public int size() {return total;}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node node = head;@Overridepublic boolean hasNext() {return node != null;}@Overridepublic E next() {E value = node.data;node = node.next;return value;}}private class Node{E data;Node next;Node(E data, Node next) {this.data = data;this.next = next;}}
}
測試類
package com.test.list;public class TestMyOneWayLinkedList{public static void main(String[] args) {MyOneWayLinkedList<String> my = new MyOneWayLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");System.out.println("一共有：" + my.size());System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的結果：");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替換java,null后：");my.update("java","JAVA");my.update(null,"chai");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("刪除hello,JAVA,null后：");my.delete("hello");my.delete("JAVA");my.delete(null);System.out.println("所有元素：");for (String s : my) {System.out.println(s);}}
}
自定義雙鏈表（拓展）
package com.test.list;import java.util.Iterator;public class MyLinkedList<E> implements Iterable<E>{private Node first;private Node last;private int total;public void add(E e){Node newNode = new Node(last, e, null);if(first == null){first = newNode;}else{last.next = newNode;}last = newNode;total++;}public int size(){return total;}public void delete(Object obj){Node find = findNode(obj);if(find != null){if(find.prev != null){find.prev.next = find.next;}else{first = find.next;}if(find.next != null){find.next.prev = find.prev;}else{last = find.prev;}find.prev = null;find.next = null;find.data = null;total--;}}private Node findNode(Object obj){Node node = first;Node find = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}node = node.next;}}return find;}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value){Node find = findNode(old);if(find != null){find.data = value;}}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node node = first;@Overridepublic boolean hasNext() {return node!=null;}@Overridepublic E next() {E value = node.data;node = node.next;return value;}}private class Node{Node prev;E data;Node next;Node(Node prev, E data, Node next) {this.prev = prev;this.data = data;this.next = next;}}
}
自定義雙鏈表測試
package com.test.list;public class TestMyLinkedList {public static void main(String[] args) {MyLinkedList<String> my = new MyLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");System.out.println("一共有：" + my.size());System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的結果：");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替換java,null后：");my.update("java","JAVA");my.update(null,"chai");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("刪除hello，JAVA,null后：");my.delete("hello");my.delete("JAVA");my.delete(null);System.out.println("所有元素：");for (String s : my) {System.out.println(s);}}
}
2.4 隊列
隊列特點
隊列是邏輯結構，其物理結構可以是數組，也可以是鏈表。隊列有普通隊列、雙端隊列、并發隊列等等，核心類庫中的隊列實現類有很多（后面會學到很多），LinkedList 是雙端隊列的實現類。
Queue 除了基本的 Collection 操作外，隊列還提供其他的插入、提取和檢查操作。每個方法都存在兩種形式：一種拋出異常（操作失敗時），另一種返回一個特殊值（null 或 false，具體取決于操作）。Queue 實現通常不允許插入 null 元素，即使在允許 null 的實現中，也不應該將 null 插入到隊列中，因為 null 也用作某些方法的特殊返回值，表明隊列不包含元素。
| 拋出異常 | 返回特殊值 | |
|---|---|---|
| 插入 | add(e) | offer(e) |
| 移除 | remove() | poll() |
| 檢查 | element() | peek() |
雙端隊列（Deque）
Deque，名稱 deque 是“double ended queue（雙端隊列）”的縮寫，通常讀為“deck”。此接口定義在雙端隊列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時拋出異常，另一種形式返回一個特殊值（null 或 false，具體取決于操作）。Deque 接口的實現類有 ArrayDeque 和 LinkedList，它們一個底層是使用數組實現，一個使用雙向鏈表實現。
| 第一個元素（頭部） | 最后一個元素（尾部） | |||
|---|---|---|---|---|
| 拋出異常 | 特殊值 | 拋出異常 | 特殊值 | |
| 插入 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| 移除 | removeFirst() | pollFirst() | removeLast() | pollLast() |
| 檢查 | getFirst() | peekFirst() | getLast() | peekLast() |
此接口擴展了 Queue 接口。在將雙端隊列用作隊列時，將得到 FIFO（先進先出）行為。將元素添加到雙端隊列的末尾，從雙端隊列的開頭移除元素。從 Queue 接口繼承的方法完全等效于 Deque 方法，如下表所示：
**Queue** 方法 | 等效 **Deque** 方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
雙端隊列也可用作 LIFO（后進先出）堆棧。應優先使用此接口而不是遺留 Stack 類。在將雙端隊列用作堆棧時，元素被推入雙端隊列的開頭并從雙端隊列開頭彈出。堆棧方法完全等效于 Deque 方法，如下表所示：
| 堆棧方法 | 等效 **Deque** 方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
結論：Deque 接口的實現類既可以用作 FILO 堆棧使用，又可以用作 FIFO 隊列使用。
示例代碼
import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {Queue<String> queue = new LinkedList<>();queue.add("A");queue.add("B");queue.add("C");System.out.println(queue.poll()); // 輸出：ASystem.out.println(queue.peek()); // 輸出：B}
}
2.5 二叉樹
二叉樹特點
- 每個節點最多有兩個子節點。
- Java 提供了
TreeMap和TreeSet類實現基于紅黑樹的有序集合。
示例代碼
import java.util.TreeMap;public class TreeMapExample {public static void main(String[] args) {TreeMap<Integer, String> treeMap = new TreeMap<>();treeMap.put(1, "One");treeMap.put(2, "Two");treeMap.put(3, "Three");System.out.println(treeMap); // 輸出：{1=One, 2=Two, 3=Three}}
}
普通二叉樹：
public class BinaryTree<E>{private TreeNode root; //二叉樹的根結點private int total;//結點總個數private class TreeNode{//至少有以下幾個部分TreeNode parent;TreeNode left;E data;TreeNode right;public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {this.parent = parent;this.left = left;this.data = data;this.right = right;}}
}
TreeMap紅黑樹：
public class TreeMap<K,V> {private transient Entry<K,V> root;private transient int size = 0;static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK;/*** Make a new cell with given key, value, and parent, and with* {@code null} child links, and BLACK color.*/Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}}
}
三、總結與建議
Java 提供了對常見數據結構的完整支持，無論是基礎的數組、鏈表，還是復雜的樹、隊列，都可以通過標準庫輕松實現。在實際開發中，應根據場景選擇合適的數據結構：
- 快速隨機訪問：選擇
ArrayList。 - 頻繁插入和刪除：選擇
LinkedList。 - 先進后出：選擇
Stack。 - 先進先出：選擇
Queue。 - 有序存儲：選擇
TreeMap或TreeSet。
通過對這些數據結構的深入理解和靈活運用，可以顯著提升程序的性能和可維護性。
--SpringCloud簡介)
