java常见的数据结构|面试以及常见问题

在数据结构相关的面试中，面试官可能会从理论基础、实际应用、算法实现及优化等方面提问。以下是一些数据结构面试常见问题及其简要说明：

基础概念与原理

1. 数据结构三要素是什么？

   • 存储结构（物理结构）：数据元素在计算机中如何存储。
   • 数据的逻辑结构：数据元素之间的逻辑关系，如线性结构、树形结构、图状结构和集合等。
   • 数据操作（运算）：针对特定数据结构所进行的操作，如插入、删除、查找、更新等。

2. 请描述几种基本的数据结构及其特点。

   • 数组：连续存储，支持随机访问，但插入/删除效率较低（需移动大量元素）。
   • 链表：非连续存储，每个节点包含数据和指向下一个节点的指针，插入/删除较灵活，但无法直接按索引访问。
   • 栈：后进先出（LIFO）结构，主要操作包括push、pop和peek。
   • 队列：先进先出（FIFO）结构，主要操作是enqueue、dequeue。
   • 树：多层级的节点组织形式，如二叉树、平衡树（AVL树）、红黑树等。
   • 图：由顶点和边组成，可以表示更复杂的实体间关系。
   • 哈希表：通过哈希函数映射键到地址，提供常数时间复杂度的查找（理想情况下）。

3. 解释一下动态数组和普通数组的区别。

   • 动态数组可以在需要时自动扩展其容量，以容纳更多的元素，而无需预先确定数组大小。

算法相关问题

4. 简述快速排序的过程。

   • 快速排序是一种基于分治策略的排序算法，通过选取一个基准元素将数组划分为两部分，左边小于基准，右边大于基准，然后递归地对左右两边进行快速排序。

5. 比较各种排序算法的优缺点（如冒泡排序、插入排序、选择排序、归并排序、堆排序等）。

高级问题

6. 如何判断一个单链表是否存在环？

   • 可以使用快慢指针（Floyd判圈法），一个指针每次前进一步，另一个指针每次前进两步，如果存在环，则两个指针最终会在环内相遇。

7. 设计一个LRU缓存系统。

   • 实现最近最少使用（Least Recently Used）缓存策略，通常可以通过双向链表和哈希表结合实现。

8. B树/B+树的特点及其适用场景。

   • B树适用于磁盘存储索引结构，减少磁盘I/O次数；B+树所有叶子节点形成有序链表，适合范围查询。

9. 图的深度优先搜索（DFS）和广度优先搜索（BFS）的过程和区别。

应用场景

10. 举例说明数组在实际开发中的应用。
    • 例如，在数据库索引、图像像素矩阵、程序参数列表等多个场景中都会用到数组。

以下是几个Java实现的数据结构面试常见问题及其说明:

1. 链表反转：

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    ListNode nextNode;

    while (curr != null) {
        nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }

    return prev;
}

// 示例用法
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;

ListNode reversedHead = reverseList(node1);  // 反转后的头结点是原链表的尾结点
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

2. 栈与队列的实现：

（a）栈（Stack）：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        
        // 入栈操作
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 出栈操作
        System.out.println(stack.pop());  // 输出 3
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（b）队列（Queue）：

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 入队操作
        queue.add(1);
        queue.add(2);
        queue.add(3);

        // 出队操作
        System.out.println(queue.poll());  // 输出 1
    }
}

// 或者实现简单的循环队列
class MyCircularQueue {
    private int[] queue;
    private int front, rear, capacity;

    public MyCircularQueue(int k) {
        this.queue = new int[k];
        this.capacity = k;
        this.front = -1;
        this.rear = -1;
    }

    public boolean enQueue(int value) {
        // ... 实现入队逻辑 ...
    }

    public boolean deQueue() {
        // ... 实现出队逻辑 ...
    }

    // ... 其他方法如判断队列是否为空、获取队首元素等 ...
}
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

3. 二叉搜索树（BST）插入与查找：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class BST {
    TreeNode root;

    void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        if (val < node.val) {
            node.left = insertRec(node.left, val);
        } else if (val > node.val) {
            node.right = insertRec(node.right, val);
        } else {
            // 如果等于节点值，则无需插入
            return node;
        }
        return node;
    }

    // 查找方法实现略...
}
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

4. 哈希表实现映射：

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();

        // 插入键值对
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);

        // 查找键对应的值
        System.out.println(map.get("banana"));  // 输出 2
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16