Java数据结构实现详解

本文详细介绍了各种基本数据结构的Java实现，包括线性数据结构和非线性数据结构。每种数据结构都包含了基本操作方法、时间复杂度分析以及使用示例，可以作为学习数据结构与算法的参考资料。

一、线性数据结构

线性数据结构是一种数据元素之间存在一对一关系的数据结构，元素按照线性顺序排列。

1. 数组 (Array)

数组是最基本的数据结构，它在内存中是连续存储的，可以通过索引快速访问元素。

特点：

  • 固定大小（静态数组）或可动态调整大小（动态数组）
  • 随机访问元素的时间复杂度为 O(1)
  • 在数组中间插入或删除元素的时间复杂度为 O(n)

主要操作及时间复杂度：

  • 访问元素：O(1)
  • 在末尾添加/删除元素：O(1) 均摊
  • 在中间添加/删除元素：O(n)
  • 查找元素：O(n)

数组结构示意图：

1
2
3
+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 |  -> 索引: 0,1,2,3,4,5
+---+---+---+---+---+---+

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class DynamicArray<E> {
    private E[] data;
    private int size;
  
    // 构造函数，传入数组的容量capacity构造Array
    @SuppressWarnings("unchecked")
    public DynamicArray(int capacity) {
        data = (E[])new Object[capacity];
        size = 0;
    }
  
    // 获取数组中的元素个数
    public int getSize() {
        return size;
    }
  
    // 获取数组的容量
    public int getCapacity() {
        return data.length;
    }
  
    // 在index位置插入一个新元素e
    public void add(int index, E e) {
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
      
        if(size == data.length)
            resize(2 * data.length);
      
        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];
      
        data[index] = e;
        size ++;
    }
  
    // 获取index索引位置的元素
    public E get(int index) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }
  
    // 修改index索引位置的元素为e
    public void set(int index, E e) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }
  
    // 查找数组中是否有元素e
    public boolean contains(E e) {
        for(int i = 0; i < size; i++) {
            if(data[i].equals(e))
                return true;
        }
        return false;
    }
  
    // 删除index位置的元素，返回删除的元素
    public E remove(int index) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
      
        E ret = data[index];
        for(int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null;
      
        if(size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return ret;
    }
  
    // 将数组空间的容量变成newCapacity大小
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0; i < size; i++)
            newData[i] = data[i];
        data = newData;
    }
}

操作示意图：

在索引2处插入元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
原数组：
+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | - |
+---+---+---+---+---+---+

移动元素：
+---+---+---+---+---+---+
| 1 | 2 | - | 3 | 4 | 5 |
+---+---+---+---+---+---+

插入新元素：
+---+---+---+---+---+---+
| 1 | 2 | 6 | 3 | 4 | 5 |
+---+---+---+---+---+---+

应用场景：

  • 需要频繁随机访问元素的场景
  • 数据量固定的场景
  • 需要存储基本数据类型的场景
  • 多维数据结构（如矩阵）的实现

2. 链表 (LinkedList)

链表是由一系列节点组成的线性集合，每个节点包含数据和指向下一个节点的引用。

3. 栈 (Stack)

栈是一种后进先出（LIFO）的线性数据结构，只允许在一端（栈顶）进行插入和删除操作。

二、树形数据结构

树形数据结构是一种非线性数据结构，它以层次方式存储数据，每个节点可以有多个子节点。

1. 二叉树 (Binary Tree)

二叉树是每个节点最多有两个子节点的树形数据结构。

二叉树的结构示意图：

1
2
3
4
5
6
7
    1
   / \
  2   3
 / \   \
4   5   6
   /
  7

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class BinaryTree<E> {
    private class Node {
        public E data;
        public Node left, right;

        public Node(E data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BinaryTree() {
        root = null;
        size = 0;
    }

    // 前序遍历
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if(node == null)
            return;
      
        System.out.println(node.data);
        preOrder(node.left);
        preOrder(node.right);
    }

    // 中序遍历
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if(node == null)
            return;

        inOrder(node.left);
        System.out.println(node.data);
        inOrder(node.right);
    }

    // 后序遍历
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if(node == null)
            return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }

    // 层序遍历
    public void levelOrder() {
        if(root == null)
            return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            Node cur = queue.remove();
            System.out.println(cur.data);

            if(cur.left != null)
                queue.add(cur.left);
            if(cur.right != null)
                queue.add(cur.right);
        }
    }
}

2. 二叉搜索树 (Binary Search Tree)

二叉搜索树是一种特殊的二叉树，它满足以下性质：

  • 左子树上所有节点的值均小于当前节点的值
  • 右子树上所有节点的值均大于当前节点的值
  • 左右子树也分别是二叉搜索树

二叉搜索树示意图：

1
2
3
4
5
    5
   / \
  3   7
 / \   \
2   4   8

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class BST<E extends Comparable<E>> {
    private class Node {
        public E data;
        public Node left, right;

        public Node(E data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    // 向二分搜索树中添加新的元素e
    public void add(E e) {
        root = add(root, e);
    }

    // 向以node为根的二分搜索树中插入元素e，递归算法
    private Node add(Node node, E e) {
        if(node == null) {
            size++;
            return new Node(e);
        }

        if(e.compareTo(node.data) < 0)
            node.left = add(node.left, e);
        else if(e.compareTo(node.data) > 0)
            node.right = add(node.right, e);

        return node;
    }

    // 查找二分搜索树中是否包含元素e
    public boolean contains(E e) {
        return contains(root, e);
    }

    // 看以node为根的二分搜索树中是否包含元素e，递归算法
    private boolean contains(Node node, E e) {
        if(node == null)
            return false;

        if(e.compareTo(node.data) == 0)
            return true;
        else if(e.compareTo(node.data) < 0)
            return contains(node.left, e);
        else
            return contains(node.right, e);
    }

    // 删除最小值所在节点，返回最小值
    public E removeMin() {
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    // 删除以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    private Node removeMin(Node node) {
        if(node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    // 寻找二分搜索树的最小元素
    public E minimum() {
        if(size == 0)
            throw new IllegalArgumentException("BST is empty");
        return minimum(root).data;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if(node.left == null)
            return node;
        return minimum(node.left);
    }
}

应用场景：

  • 文件系统的目录结构
  • 数据库索引
  • 表达式解析
  • 优先队列实现

3. 平衡二叉树 (AVL Tree)

AVL树是一种自平衡二叉搜索树，任何节点的两个子树的高度差不超过1。

AVL树的结构示意图：

1
2
3
4
5
6
7
  节点的平衡因子 = 左子树高度 - 右子树高度

     4(0)
    /    \
 2(-1)    6(0)
  /      /   \
1(0)   5(0)  7(0)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
public class AVLTree<E extends Comparable<E>> {
    private class Node {
        public E data;
        public Node left, right;
        public int height;

        public Node(E data) {
            this.data = data;
            left = null;
            right = null;
            height = 1;
        }
    }

    private Node root;
    private int size;

    // 获得节点的高度
    private int getHeight(Node node) {
        if(node == null)
            return 0;
        return node.height;
    }

    // 获得节点的平衡因子
    private int getBalanceFactor(Node node) {
        if(node == null)
            return 0;
        return getHeight(node.left) - getHeight(node.right);
    }

    // 右旋转
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T3 = x.right;

        x.right = y;
        y.left = T3;

        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

    // 左旋转
    private Node leftRotate(Node y) {
        Node x = y.right;
        Node T2 = x.left;

        x.left = y;
        y.right = T2;

        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

    // 添加新元素
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if(node == null) {
            size++;
            return new Node(e);
        }

        if(e.compareTo(node.data) < 0)
            node.left = add(node.left, e);
        else if(e.compareTo(node.data) > 0)
            node.right = add(node.right, e);
        else
            return node;

        // 更新height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // 计算平衡因子
        int balanceFactor = getBalanceFactor(node);

        // 平衡维护
        // LL
        if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
            return rightRotate(node);

        // RR
        if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
            return leftRotate(node);

        // LR
        if(balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RL
        if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }
}

4. 红黑树 (Red-Black Tree)

红黑树是一种自平衡二叉搜索树，通过节点的颜色来维持树的平衡。

红黑树的性质：

  1. 每个节点要么是红色，要么是黑色
  2. 根节点是黑色
  3. 每个叶子节点（NIL）是黑色
  4. 如果一个节点是红色的，则它的子节点必须是黑色的
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

红黑树示意图：

1
2
3
4
5
6
7
8
       [B]7
      /    \
   [B]3    [B]11
    /  \      \
 [R]1  [R]5   [R]13

[B] - 黑色节点
[R] - 红色节点

应用场景：

  • Java的TreeMap和TreeSet的底层实现
  • Linux内核中的完全公平调度器
  • 数据库索引
  • 文件系统

三、哈希表 (Hash Table)

哈希表是一种通过哈希函数将键映射到值的数据结构，它提供了快速的插入、删除和查找操作。

哈希表结构示意图：

1
2
3
4
5
6
7
8
9
index  →  链表（处理冲突）
 |
 [0] → [k1,v1] → [k5,v5]
 [1] → [k2,v2]
 [2]
 [3] → [k3,v3]
 [4] → [k4,v4] → [k6,v6]
 [5]
 [6]

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class HashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;

    private class Node {
        public K key;
        public V value;
        public Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Node[] table;
    private int size;

    public HashMap() {
        table = new Node[DEFAULT_CAPACITY];
        size = 0;
    }

    // 计算哈希值
    private int hash(K key) {
        return Math.abs(key.hashCode() % table.length);
    }

    // 添加元素
    public void put(K key, V value) {
        int index = hash(key);
        Node node = table[index];

        while(node != null) {
            if(node.key.equals(key)) {
                node.value = value;
                return;
            }
            node = node.next;
        }

        table[index] = new Node(key, value, table[index]);
        size++;

        if(size >= table.length * LOAD_FACTOR)
            resize();
    }

    // 获取元素
    public V get(K key) {
        int index = hash(key);
        Node node = table[index];

        while(node != null) {
            if(node.key.equals(key))
                return node.value;
            node = node.next;
        }

        return null;
    }

    // 删除元素
    public V remove(K key) {
        int index = hash(key);
        Node node = table[index];
        Node prev = null;

        while(node != null) {
            if(node.key.equals(key)) {
                if(prev == null)
                    table[index] = node.next;
                else
                    prev.next = node.next;
                size--;
                return node.value;
            }
            prev = node;
            node = node.next;
        }

        return null;
    }

    // 扩容
    private void resize() {
        Node[] oldTable = table;
        table = new Node[oldTable.length * 2];
        size = 0;

        for(Node node : oldTable) {
            while(node != null) {
                put(node.key, node.value);
                node = node.next;
            }
        }
    }
}

四、图 (Graph)

图是一种由顶点和边组成的非线性数据结构，用于表示元素之间的关系。

图的表示方法：

  1. 邻接矩阵：
1
2
3
4
5
    A  B  C  D
A   0  1  1  0
B   1  0  1  1
C   1  1  0  1
D   0  1  1  0
  1. 邻接表：
1
2
3
4
A → [B, C]
B → [A, C, D]
C → [A, B, D]
D → [B, C]

代码实现（邻接表）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Graph {
    private int V;   // 顶点数
    private LinkedList<Integer>[] adj;    // 邻接表

    @SuppressWarnings("unchecked")
    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for(int i = 0; i < v; i++)
            adj[i] = new LinkedList<>();
    }

    // 添加边
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);    // 无向图实现
    }

    // 广度优先搜索
    public void BFS(int s) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while(!queue.isEmpty()) {
            s = queue.poll();
            System.out.print(s + " ");

            for(int n : adj[s]) {
                if(!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    // 深度优先搜索
    public void DFS(int s) {
        boolean[] visited = new boolean[V];
        DFSUtil(s, visited);
    }

    private void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for(int n : adj[v]) {
            if(!visited[n])
                DFSUtil(n, visited);
        }
    }
}

应用场景：

  • 社交网络
  • 地图导航
  • 网络拓扑
  • 任务调度

特点：

  • 后进先出（LIFO）
  • 只能从栈顶访问元素
  • 可以用数组或链表实现

栈的结构示意图：

1
2
3
4
5
6
7
8
9
10
    ↑ 栈顶
+---+
| 4 |  <- 最后入栈的元素
+---+
| 3 |
+---+
| 2 |
+---+
| 1 |  <- 最先入栈的元素
+---+

基于数组实现的栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class ArrayStack<E> {
    private Array<E> array;

    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    public int getSize() {
        return array.getSize();
    }

    public boolean isEmpty() {
        return array.isEmpty();
    }

    // 入栈操作
    public void push(E e) {
        array.addLast(e);
    }

    // 出栈操作
    public E pop() {
        return array.removeLast();
    }

    // 查看栈顶元素
    public E peek() {
        return array.getLast();
    }
}

4. 队列 (Queue)

队列是一种先进先出（FIFO）的线性数据结构，只允许在一端（队尾）进行插入操作，在另一端（队首）进行删除操作。

特点：

  • 先进先出（FIFO）
  • 队首删除，队尾添加
  • 可以用数组或链表实现

队列的结构示意图：

1
2
3
4
队首 →  +---+---+---+---+
        | 1 | 2 | 3 | 4 |  ← 队尾
        +---+---+---+---+
出队 ←   最先进入的元素   → 入队

循环队列实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class CircularQueue<E> {
    private E[] data;
    private int front, tail;
    private int size;

    public CircularQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public boolean isEmpty() {
        return front == tail;
    }

    public boolean isFull() {
        return (tail + 1) % data.length == front;
    }

    // 入队操作
    public void enqueue(E e) {
        if (isFull())
            throw new IllegalStateException("Queue is full");
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    // 出队操作
    public E dequeue() {
        if (isEmpty())
            throw new IllegalStateException("Queue is empty");
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        return ret;
    }

    // 查看队首元素
    public E getFront() {
        if (isEmpty())
            throw new IllegalStateException("Queue is empty");
        return data[front];
    }

    public int getSize() {
        return size;
    }
}

应用场景：

  • 栈：

    • 函数调用栈
    • 表达式求值
    • 括号匹配
    • 浏览器前进/后退功能

  • 队列：

    • 任务调度
    • 消息队列
    • 打印机打印任务
    • 广度优先搜索

特点：

  • 动态大小
  • 插入和删除操作简单
  • 不支持随机访问

链表结构示意图：

1
2
3
4
5
6
7
8
9
单链表：
+---+    +---+    +---+    +---+
| 1 |->  | 2 |->  | 3 |->  | 4 |->  NULL
+---+    +---+    +---+    +---+

双向链表：
+---+    +---+    +---+    +---+
NULL <-| 1 |<-> | 2 |<-> | 3 |<-> | 4 |->  NULL
+---+    +---+    +---+    +---+

主要操作及时间复杂度：

  • 访问元素：O(n)
  • 在头部添加/删除元素：O(1)
  • 在尾部添加/删除元素：O(n)（单链表）或 O(1)（带尾指针的链表）
  • 在中间添加/删除元素：O(n)

操作示意图：

在位置2插入新节点：

1
2
3
4
5
6
7
8
9
原链表：
+---+    +---+    +---+    +---+
| 1 |->  | 2 |->  | 3 |->  | 4 |
+---+    +---+    +---+    +---+

插入新节点：
+---+    +---+    +---+    +---+    +---+
| 1 |->  | 2 |->  | 5 |->  | 3 |->  | 4 |
+---+    +---+    +---+    +---+    +---+

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
public class LinkedList<E> {
    private class Node {
        public E data;       // 节点数据
        public Node next;    // 指向下一个节点的引用

        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node dummyHead;  // 虚拟头节点
    private int size;        // 链表大小

    public LinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }

    // 获取链表中的元素个数
    public int getSize() {
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在链表头添加新元素
    public void addFirst(E e) {
        add(0, e);
    }

    // 在链表末尾添加新元素
    public void addLast(E e) {
        add(size, e);
    }

    // 在指定位置添加新元素
    public void add(int index, E e) {
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for(int i = 0; i < index; i++)
            prev = prev.next;

        prev.next = new Node(e, prev.next);
        size++;
    }

    // 获取指定位置的元素
    public E get(int index) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0; i < index; i++)
            cur = cur.next;
        return cur.data;
    }

    // 修改指定位置的元素
    public void set(int index, E e) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0; i < index; i++)
            cur = cur.next;
        cur.data = e;
    }

    // 查找链表中是否有元素e
    public boolean contains(E e) {
        Node cur = dummyHead.next;
        while(cur != null) {
            if(cur.data.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    // 删除指定位置的元素
    public E remove(int index) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        Node prev = dummyHead;
        for(int i = 0; i < index; i++)
            prev = prev.next;

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size--;

        return retNode.data;
    }
}

应用场景：

  • 需要频繁插入和删除元素的场景

  • 不需要随机访问的场景

  • 内存空间要求灵活的场景

  • 实现其他数据结构（如栈、队列、哈希表的拉链法等）
    prev = prev.next;
    }

    Node retNode = prev.next;
    prev.next = retNode.next;
    retNode.next = null;
    size–;

    return retNode.data;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

### 3. 栈 (Stack)

栈是一种后进先出(LIFO)的线性表，只能在一端（栈顶）进行插入和删除操作。

**特点：**
- 后进先出(LIFO)
- 只能从栈顶访问元素

**主要操作及时间复杂度：**
- 压栈(push)：O(1)
- 出栈(pop)：O(1)
- 查看栈顶元素(peek)：O(1)

**代码示例：**

```java
// 将元素压入栈顶
public void push(E e) {
    array.addLast(e);
}

// 弹出栈顶元素
public E pop() {
    return array.removeLast();
}

// 查看栈顶元素
public E peek() {
    return array.getLast();
}

应用场景：

  • 函数调用栈
  • 表达式求值
  • 括号匹配
  • 深度优先搜索

4. 队列 (Queue)

队列是一种先进先出(FIFO)的线性表，只能在一端（队尾）进行插入操作，在另一端（队头）进行删除操作。

特点：

  • 先进先出(FIFO)
  • 只能从队头删除元素，从队尾添加元素

主要操作及时间复杂度：

  • 入队(enqueue)：O(1)
  • 出队(dequeue)：O(1)
  • 查看队首元素(front)：O(1)

应用场景：

  • 任务调度
  • 消息队列
  • 广度优先搜索

二、非线性数据结构

非线性数据结构是一种数据元素之间存在一对多关系的数据结构，元素不是按照线性顺序排列的。

1. 树 (Tree)

树是一种层次结构，由节点组成，每个节点可以有多个子节点。

1.1 二叉树 (Binary Tree)

二叉树是每个节点最多有两个子节点（左子节点和右子节点）的树结构。

特点：

  • 每个节点最多有两个子节点
  • 具有层次结构

主要操作及时间复杂度：

  • 前序遍历：O(n)
  • 中序遍历：O(n)
  • 后序遍历：O(n)
  • 层序遍历：O(n)

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 前序遍历
private void preOrder(Node node) {
    if (node == null) {
        return;
    }

    System.out.print(node.data + " ");
    preOrder(node.left);
    preOrder(node.right);
}

// 中序遍历
private void inOrder(Node node) {
    if (node == null) {
        return;
    }

    inOrder(node.left);
    System.out.print(node.data + " ");
    inOrder(node.right);
}

// 后序遍历
private void postOrder(Node node) {
    if (node == null) {
        return;
    }

    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.data + " ");
}

1.2 二叉搜索树 (Binary Search Tree)

二叉搜索树是一种特殊的二叉树，对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。

特点：

  • 左子树上所有节点的值均小于根节点的值
  • 右子树上所有节点的值均大于根节点的值
  • 左右子树也分别为二叉搜索树

主要操作及时间复杂度：

  • 查找：平均 O(log n)，最坏 O(n)
  • 插入：平均 O(log n)，最坏 O(n)
  • 删除：平均 O(log n)，最坏 O(n)

1.3 平衡二叉树 (AVL Tree)

平衡二叉树是一种特殊的二叉搜索树，它要求每个节点的左右子树的高度差不超过1。

特点：

  • 是一棵二叉搜索树
  • 每个节点的左右子树的高度差不超过1

主要操作及时间复杂度：

  • 查找：O(log n)
  • 插入：O(log n)
  • 删除：O(log n)

2. 堆 (Heap)

堆是一种特殊的完全二叉树，分为最大堆和最小堆。

特点：

  • 最大堆：每个节点的值都大于或等于其子节点的值
  • 最小堆：每个节点的值都小于或等于其子节点的值
  • 是完全二叉树

主要操作及时间复杂度：

  • 插入元素：O(log n)
  • 删除最大/最小元素：O(log n)
  • 获取最大/最小元素：O(1)
  • 构建堆：O(n)

应用场景：

  • 优先队列
  • 堆排序
  • 图算法（如Dijkstra算法）

3. 图 (Graph)

图是由顶点和边组成的非线性数据结构，用于表示物体之间的关系。

特点：

  • 由顶点和边组成
  • 可以是有向的或无向的
  • 可以是带权的或不带权的

表示方法：

  • 邻接矩阵
  • 邻接表

主要操作及时间复杂度：

  • 添加顶点：O(1)
  • 添加边：O(1)
  • 深度优先搜索(DFS)：O(V + E)，其中V为顶点数，E为边数
  • 广度优先搜索(BFS)：O(V + E)
  • 最短路径算法（如Dijkstra）：O(V^2 + E)或O((V+E)logV)（使用优先队列）
  • 最小生成树算法（如Prim）：O(V^2)或O(ElogV)（使用优先队列）

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 添加边
public void addEdge(V from, V to, int weight) {
    // 确保顶点存在
    addVertex(from);
    addVertex(to);

    int fromIndex = vertexMap.get(from);
    int toIndex = vertexMap.get(to);

    // 添加边
    adjList.get(fromIndex).add(new Edge(toIndex, weight));
    edgeCount++;

    // 如果是无向图，则添加反向边
    if (!directed) {
        adjList.get(toIndex).add(new Edge(fromIndex, weight));
    }
}

// 深度优先遍历
private void dfsHelper(int vertex, boolean[] visited, List<V> result) {
    visited[vertex] = true;
    result.add(vertexList.get(vertex));

    for (Edge edge : adjList.get(vertex)) {
        if (!visited[edge.to]) {
            dfsHelper(edge.to, visited, result);
        }
    }
}

4. 哈希表 (Hash Table)

哈希表是一种能够实现关联数组的数据结构，它通过哈希函数将键映射到值。

特点：

  • 通过键直接访问元素
  • 平均查找、插入和删除时间复杂度为O(1)
  • 可能存在哈希冲突

主要操作及时间复杂度：

  • 插入：平均O(1)，最坏O(n)
  • 查找：平均O(1)，最坏O(n)
  • 删除：平均O(1)，最坏O(n)

解决哈希冲突的方法：

  • 链地址法（拉链法）
  • 开放地址法（线性探测、二次探测、双重哈希）

应用场景：

  • 实现字典或映射
  • 缓存实现
  • 集合实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.util.*;

public class CollectionExample {
    public static void main(String[] args) {
        // List 示例
        System.out.println("List Example:");
        // ArrayList 是基于动态数组实现的，适合频繁访问元素的场景。
        List<String> list = new ArrayList<>();
        list.add("Apple"); // 在末尾添加一个元素
        list.add("Banana");
        list.add("Cherry");

        System.out.println("Initial List: " + list);
        System.out.println("Size of List: " + list.size()); // 返回长度
        System.out.println("Is List empty? " + list.isEmpty()); // 是否为空

        String element = list.get(1); // 获取第i个元素
        System.out.println("Element at index 1: " + element);

        list.set(1, "Blueberry"); // 将第i个元素设置为val
        System.out.println("Updated List: " + list);

        list.clear(); // 清空
        System.out.println("Cleared List: " + list);

        // Stack 示例
        System.out.println("\nStack Example:");
        // Stack 是继承自 Vector 的后进先出 (LIFO) 栈。
        Stack<Integer> stack = new Stack<>();
        stack.push(10); // 压入元素
        stack.push(20);
        stack.push(30);

        System.out.println("Initial Stack: " + stack);
        System.out.println("Size of Stack: " + stack.size()); // 返回长度
        System.out.println("Is Stack empty? " + stack.empty()); // 栈是否为空

        int topElement = stack.pop(); // 弹出栈顶元素，并返回栈顶元素
        System.out.println("Popped Element: " + topElement);
        System.out.println("Updated Stack after pop: " + stack);

        int peekElement = stack.peek(); // 返回栈顶元素
        System.out.println("Peeked Element: " + peekElement);
        System.out.println("Stack after peek: " + stack);

        stack.clear(); // 清空
        System.out.println("Cleared Stack: " + stack);

        // Queue 示例
        System.out.println("\nQueue Example:");
        // LinkedList 实现了 Queue 接口，适合用作队列。
        Queue<String> queue = new LinkedList<>();
        queue.add("Red"); // 在队尾添加元素
        queue.add("Green");
        queue.add("Blue");

        System.out.println("Initial Queue: " + queue);
        System.out.println("Size of Queue: " + queue.size()); // 返回长度
        System.out.println("Is Queue empty? " + queue.isEmpty()); // 是否为空

        String headElement = queue.remove(); // 删除并返回队头
        System.out.println("Removed Element: " + headElement);
        System.out.println("Updated Queue after remove: " + queue);

        String peekHead = queue.peek(); // 返回队头
        System.out.println("Peeked Head Element: " + peekHead);
        System.out.println("Queue after peek: " + queue);

        queue.clear(); // 清空
        System.out.println("Cleared Queue: " + queue);

        // Set 示例
        System.out.println("\nSet Example:");
        // HashSet 不允许重复元素，内部使用哈希表实现。
        Set<String> set = new HashSet<>();
        set.add("Carrot"); // 添加元素
        set.add("Broccoli");
        set.add("Carrot"); // Duplicate, will not be added

        System.out.println("Initial Set: " + set);
        System.out.println("Size of Set: " + set.size()); // 返回元素数
        System.out.println("Does Set contain 'Carrot'? " + set.contains("Carrot")); // 是否包含某个元素
        System.out.println("Does Set contain 'Potato'? " + set.contains("Potato"));

        set.remove("Broccoli"); // 删除元素
        System.out.println("Updated Set after remove: " + set);

        set.clear(); // 清空
        System.out.println("Cleared Set: " + set);

        // TreeSet 示例
        System.out.println("\nTreeSet Example:");
        // TreeSet 不允许重复元素，内部使用红黑树实现，支持有序遍历。
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(5); // 添加元素
        treeSet.add(3);
        treeSet.add(8);

        System.out.println("Initial TreeSet: " + treeSet);
        System.out.println("Ceiling of 4: " + treeSet.ceiling(4)); // 返回大于等于key的最小元素，不存在则返回null
        System.out.println("Floor of 6: " + treeSet.floor(6)); // 返回小于等于key的最大元素，不存在则返回null

        treeSet.clear(); // 清空
        System.out.println("Cleared TreeSet: " + treeSet);

        // Map 示例
        System.out.println("\nMap Example:");
        // HashMap 使用哈希表实现，键值对存储，不允许重复键。
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 25); // 添加关键字和其对应的值
        map.put("Bob", 30);
        map.put("Charlie", 35);

        System.out.println("Initial Map: " + map);
        System.out.println("Size of Map: " + map.size()); // 返回元素数
        System.out.println("Value for key 'Bob': " + map.get("Bob")); // 返回关键字对应的值
        System.out.println("Does Map contain key 'Alice'? " + map.containsKey("Alice")); // 是否包含关键字
        System.out.println("Does Map contain key 'David'? " + map.containsKey("David"));

        map.remove("Bob"); // 删除关键字
        System.out.println("Updated Map after remove: " + map);

        map.clear(); // 清空
        System.out.println("Cleared Map: " + map);

        // TreeMap 示例
        System.out.println("\nTreeMap Example:");
        // TreeMap 使用红黑树实现，键值对存储，按键排序，不允许重复键。
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("Eve", 28); // 添加关键字和其对应的值
        treeMap.put("Dan", 22);
        treeMap.put("Frank", 27);

        System.out.println("Initial TreeMap: " + treeMap);
        System.out.println("Entry ceiling of 'Dean': " + treeMap.ceilingEntry("Dean").getValue()); // 返回大于等于key的最小元素，不存在则返回null
        System.out.println("Entry floor of 'George': " + treeMap.floorEntry("George").getValue()); // 返回小于等于key的最大元素，不存在则返回null

        treeMap.clear(); // 清空
        System.out.println("Cleared TreeMap: " + treeMap);
    }
}




import java.util.*;

public class CollectionExample {
public static void main(String[] args) {
// List 示例
System.out.println(“List Example:”);
// ArrayList 是基于动态数组实现的，适合频繁访问元素的场景。
List list = new ArrayList<>();
list.add(“Apple”); // 在末尾添加一个元素
list.add(“Banana”);
list.add(“Cherry”);

System.out.println("Initial List: " + list);
System.out.println("Size of List: " + list.size()); // 返回长度
System.out.println("Is List empty? " + list.isEmpty()); // 是否为空

String element = list.get(1); // 获取第i个元素
System.out.println("Element at index 1: " + element);

list.set(1, "Blueberry"); // 将第i个元素设置为val
System.out.println("Updated List: " + list);

list.clear(); // 清空
System.out.println("Cleared List: " + list);

// Stack 示例
System.out.println("\nStack Example:");
// Stack 是继承自 Vector 的后进先出 (LIFO) 栈。
Stack<Integer> stack = new Stack<>();
stack.push(10); // 压入元素
stack.push(20);
stack.push(30);

System.out.println("Initial Stack: " + stack);
System.out.println("Size of Stack: " + stack.size()); // 返回长度
System.out.println("Is Stack empty? " + stack.empty()); // 栈是否为空

int topElement = stack.pop(); // 弹出栈顶元素，并返回栈顶元素
System.out.println("Popped Element: " + topElement);
System.out.println("Updated Stack after pop: " + stack);

int peekElement = stack.peek(); // 返回栈顶元素
System.out.println("Peeked Element: " + peekElement);
System.out.println("Stack after peek: " + stack);

stack.clear(); // 清空
System.out.println("Cleared Stack: " + stack);

// Queue 示例
System.out.println("\nQueue Example:");
// LinkedList 实现了 Queue 接口，适合用作队列。
Queue<String> queue = new LinkedList<>();
queue.add("Red"); // 在队尾添加元素
queue.add("Green");
queue.add("Blue");

System.out.println("Initial Queue: " + queue);
System.out.println("Size of Queue: " + queue.size()); // 返回长度
System.out.println("Is Queue empty? " + queue.isEmpty()); // 是否为空

String headElement = queue.remove(); // 删除并返回队头
System.out.println("Removed Element: " + headElement);
System.out.println("Updated Queue after remove: " + queue);

String peekHead = queue.peek(); // 返回队头
System.out.println("Peeked Head Element: " + peekHead);
System.out.println("Queue after peek: " + queue);

queue.clear(); // 清空
System.out.println("Cleared Queue: " + queue);

// Set 示例
System.out.println("\nSet Example:");
// HashSet 不允许重复元素，内部使用哈希表实现。
Set<String> set = new HashSet<>();
set.add("Carrot"); // 添加元素
set.add("Broccoli");
set.add("Carrot"); // Duplicate, will not be added

System.out.println("Initial Set: " + set);
System.out.println("Size of Set: " + set.size()); // 返回元素数
System.out.println("Does Set contain 'Carrot'? " + set.contains("Carrot")); // 是否包含某个元素
System.out.println("Does Set contain 'Potato'? " + set.contains("Potato"));

set.remove("Broccoli"); // 删除元素
System.out.println("Updated Set after remove: " + set);

set.clear(); // 清空
System.out.println("Cleared Set: " + set);

// TreeSet 示例
System.out.println("\nTreeSet Example:");
// TreeSet 不允许重复元素，内部使用红黑树实现，支持有序遍历。
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(5); // 添加元素
treeSet.add(3);
treeSet.add(8);

System.out.println("Initial TreeSet: " + treeSet);
System.out.println("Ceiling of 4: " + treeSet.ceiling(4)); // 返回大于等于key的最小元素，不存在则返回null
System.out.println("Floor of 6: " + treeSet.floor(6)); // 返回小于等于key的最大元素，不存在则返回null

treeSet.clear(); // 清空
System.out.println("Cleared TreeSet: " + treeSet);

// Map 示例
System.out.println("\nMap Example:");
// HashMap 使用哈希表实现，键值对存储，不允许重复键。
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25); // 添加关键字和其对应的值
map.put("Bob", 30);
map.put("Charlie", 35);

System.out.println("Initial Map: " + map);
System.out.println("Size of Map: " + map.size()); // 返回元素数
System.out.println("Value for key 'Bob': " + map.get("Bob")); // 返回关键字对应的值
System.out.println("Does Map contain key 'Alice'? " + map.containsKey("Alice")); // 是否包含关键字
System.out.println("Does Map contain key 'David'? " + map.containsKey("David"));

map.remove("Bob"); // 删除关键字
System.out.println("Updated Map after remove: " + map);

map.clear(); // 清空
System.out.println("Cleared Map: " + map);

// TreeMap 示例
System.out.println("\nTreeMap Example:");
// TreeMap 使用红黑树实现，键值对存储，按键排序，不允许重复键。
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Eve", 28); // 添加关键字和其对应的值
treeMap.put("Dan", 22);
treeMap.put("Frank", 27);

System.out.println("Initial TreeMap: " + treeMap);
System.out.println("Entry ceiling of 'Dean': " + treeMap.ceilingEntry("Dean").getValue()); // 返回大于等于key的最小元素，不存在则返回null
System.out.println("Entry floor of 'George': " + treeMap.floorEntry("George").getValue()); // 返回小于等于key的最大元素，不存在则返回null

treeMap.clear(); // 清空
System.out.println("Cleared TreeMap: " + treeMap);

}
}

总结

本文详细介绍了各种基本数据结构的Java实现，包括线性数据结构（数组、链表、栈、队列）和非线性数据结构（树、堆、图、哈希表）。每种数据结构都有其特定的应用场景和性能特点，在实际编程中，需要根据具体问题选择合适的数据结构。

通过学习和掌握这些数据结构的实现原理和使用方法，可以提高编程效率和代码质量，为解决复杂问题打下坚实的基础。