Java常见数据结构面试题（带答案）

Java常见数据结构面试题（带答案）完整攻略

介绍

在Java面试中，数据结构不可避免地成为一部分的考察内容。因此，掌握Java常见数据结构，对于提高面试成功率十分必要。本篇攻略将会介绍常见的Java数据结构，并提供相应的面试题目和答案，希望可以帮助面试者在面试当中更好地展示自己的实力。

目录

1. 结构体

2. 数组

3. 链表

4. 栈

5. 队列

6. 树

7. 哈希表

结构体

在Java中并没有结构体这种数据结构，但是可以通过类来模拟。在面试时，通常会考察对于结构体的实现和使用情况。比如：

面试题目：如何创建一个结构体

结构体在Java中可以通过类来实现。例如，创建一个Person的结构体：

class Person {
    int age;
    String name;
}

这里我们定义了一个名为Person的类，其中有两个成员变量：age和name。然后就可以使用这个结构体来存储和操作个人信息了。

示例：定义一个结构体

class Person {
    int age;
    String name;
}

数组

数组是一种最基本的数据结构，也是最常见的。在Java中，数组和C语言中的数组类似，但是Java中的数组长度是可以动态改变的。

面试题目：如何初始化一个数组

Java中可以通过new关键字来初始化一个数组。例如：

int[] arr = new int[10];

这里定义了一个长度为10的数组arr，并将其初始化为全部为0的默认值。

示例：定义并初始化一个数组

int[] arr = {1, 2, 3, 4, 5};

这里定义了一个长度为5的数组arr，并将其初始化为1、2、3、4、5这5个数字。

链表

链表是一种线性数据结构，由若干个节点组成，每个节点包含一个数据和指向下一个节点的指针。在Java中实现链表通常使用节点类，然后通过节点之间的链接来组成链表。

面试题目：如何在链表头添加一个节点

在链表头添加节点通常是链表插入操作中最常用的，也是最基本的。例如：

Node newNode = new Node(data);
newNode.next = head;
head = newNode;

这里我们定义了一个名为newNode的节点，并将其指向原来的链表头head。然后再将newNode作为新的链表头。

示例：添加一个节点到链表头

假设有一个名为head的链表头，我们需要在这个链表头前插入一个名为newNode的节点：

Node newNode = new Node(data);
newNode.next = head;
head = newNode;

这里我们创建了一个名为newNode的节点，并将其指向原来的链表头head，然后将newNode作为新的链表头。

栈

栈是一种线性数据结构，只能在栈顶进行插入和删除操作。在面试过程中，常常会考察栈的实现和操作情况。

面试题目：如何实现栈的Push操作

栈的Push操作其实就是在栈顶插入一个元素。在Java中可以通过ArrayList等其他集合类/基础数据类型数组来实现。例如，在Java中使用ArrayList来实现Push操作：

ArrayList<Integer> stack = new ArrayList<>();
stack.add(data);

这里定义一个名为stack的ArrayList，并且使用add()方法将data插入到stack的末尾。

示例：使用ArrayList来实现Stack的Push操作

假设我们有一个ArrayList的变量stack和一个名为data的int型数据。那么可以通过以下代码来实现Push操作：

stack.add(data);

这里使用add()方法将data插入到stack的末尾。

队列

队列也是一种线性数据结构，但是和栈不同的是队列只能在队首和队尾进行插入和删除操作。通常，Java中可以使用LinkedList等其他集合类来实现队列。

面试题目：如何实现队列的Enqueue操作

在Java中可以使用LinkedList等其他集合类来实现队列的Enqueue操作。例如：

LinkedList<Integer> queue = new LinkedList<Integer>();
queue.add(data);

这里定义了一个名为queue的LinkedList变量，并使用add()方法将data插入到队列的末尾。

示例：使用LinkedList来实现队列的Enqueue操作

假设我们有一个LinkedList的变量queue和一个名为data的int型数据。那么可以通过以下代码来实现Enqueue操作：

queue.add(data);

这里使用add()方法将data插入到队列的末尾。

树

树是一种非线性数据结构，由若干个节点和边组成。在Java中，我们通常使用树的节点类来模拟树的实现。

面试题目：如何遍历一棵树

树的遍历通常有三种方式：先序遍历、中序遍历和后序遍历。在Java中可以使用递归和循环两种方式来实现。

例如，在Java中使用递归的先序遍历方式：

void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

这里定义了一个名为preOrder的函数，接受一个名为root的TreeNode变量，并使用递归的方式实现了以先序遍历方式遍历整棵树的功能。

示例：使用递归的方式实现树的先序遍历

假设我们有一个根节点为root的树，并需要使用递归的方式实现先序遍历。那么可以通过以下代码来实现：

void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

这里使用递归的方式实现了以先序遍历方式遍历整棵树的功能。

哈希表

哈希表是一种非常重要的数据结构，在Java中可以使用HashMap等其他集合类来实现哈希表。

面试题目：如何使用哈希表查找元素

在Java中可以使用get()方法来查找哈希表中的元素。例如：

HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("apple", 1);
int value = map.get("apple");

这里定义了一个名为map的HashMap，并使用put()方法将"apple"与1这一键值对存入到map中。然后再使用get()方法查找"apple"对应的值。

示例：使用HashMap查找元素

假设我们有一个名为map的HashMap，其中已经存入了键值对："apple"和1。那么可以通过以下代码来查找"apple"对应的值：

int value = map.get("apple");

这里使用get()方法查找"apple"对应的值。