Java 数据结构基础:数组和链表

面试一定会被问到的基础知识。

数组

数组是存放在连续内存空间上的相同类型数据的集合。

概念有两个要点:一个是连续内存,另一个是相同数据类型

连续内存决定了数组的存取较为方便,通过下标可以方便地进行索引。数组的下标从0开始。连续内存也决定了在特定位置增添数组内元素时,有时需要移动其他元素的地址。数组内的元素无法删除,只能覆盖

Java中,没有指针的概念,寻址操作完全交给虚拟机。其二维数组每行头节点的排列,没有规则,也就谈不上连续。

排序算法

排序算法按照使用外存与否,可以分为内部排序外部排序;按照是否依赖于内部元素互相比较与否,可以分为比较排序非比较排序

比较排序中,按照比较后进行的不同操作,又可分为交换排序选择排序插入排序归并排序等。比较排序适用于一切需要排序的情况。

非比较排序是通过确定每个元素之前,应该有多少个元素来排序。基数排序是非比较排序。

交换排序
冒泡排序
  • 比较相邻的元素,如果前面的大于后面,交换它们
  • 循环中,每一对元素都进行比较
  • 重复过程,排除上次循环中已经沉到最底部的元素
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < array.length; i++) {
boolean exchange = false;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j + 1] > array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
exchange = true;
}
}
if (!exchange) return;
}

优化:

可以考虑在算法中加入一个布尔值,用来标识该轮有没有进行数据的交换。若在一轮循环中没有进行数据交换,说明无序区已经排好序,可以直接退出循环。

快速排序

基本思想是通过一趟排序将待排序记录分隔成独立的两部分,其中一部分元素都比另一部分关键字小,然后递归地分别对这两部分记录进行排序,以达到整个序列有序的目的。

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
public class QuickSort {
public static int partition(int[] array, int low, int high) {
// 取最后一个元素作为中心元素
int pivot = array[high];
// 定义指向比中心元素大的指针,首先指向第一个元素
int pointer = low;
// 遍历数组中的所有元素,将比中心元素大的放在右边,比中心元素小的放在左边
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
// 将比中心元素小的元素和指针指向的元素交换位置
// 如果第一个元素小于等于中心元素,这里就是自己和自己交换位置,指针和索引都向下一位移动
// 如果元素比中心元素大,索引向下移动,指针指向这个较大的元素,直到找到比中心元素小的元素,并交换位置,指针向下移动
int temp = array[i];
array[i] = array[pointer];
array[pointer] = temp;
pointer++;
}
System.out.println(Arrays.toString(array));
}
// 将中心元素和指针指向的元素交换位置
int temp = array[pointer ];
array[pointer] = array[high];
array[high] = temp;
return pointer;
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// 获取划分子数组的位置
int position = partition(array, low, high);
// 左子数组递归调用
quickSort(array, low, position -1);
// 右子数组递归调用
quickSort(array, position + 1, high);
}
}
public static void main(String[] args) {
int[] array = {6,72,113,11,23};
quickSort(array, 0, array.length -1);
System.out.println("排序后的结果");
System.out.println(Arrays.toString(array));
}
}
选择排序

简单选择排序

  • 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置(首个元素)
  • 再从剩余未排序元素中继续寻找最小(大)元素,放到已经排序序列的末尾
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < array.length; i++) {
int index = i; // 假设初始第一个最小
for (int j = i; j < array.length; j++) {
if (array[j] < array[index]) {
index = j; // 找到了更小的
}
}
// 和头一个交换,也就是未排序元素中首个元素,也就在已排序序列的末尾
int temp = array[index];
array[index] = array[i];
array[i] = temp;
}
插入排序

直接插入排序:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

1
2
3
4
5
6
7
8
for (int i = 0; i < array.length - 1; i++) {
int index = i, current = array[i + 1]; //初始,假设第一个有序; 取下一个元素,准备排序
while (index >= 0 && current < array[index]) { // 如果排序元素小于当前递归的元素, 把前面比其大的元素都进行后移
array[index + 1] = array[index];
index--;
}
array[index + 1] = current; // 直至找到合适的位置,进行插入
}

链表

链表是一种通过指针(或者是对象)串联在一起的线性结构。每一个节点由两部分组成,一个是数据域,一个是指针域(对象域)(存放指向下一个节点的指针(或对象))。最后一个节点的指针域(或对象)为空。

链表的入口节点,称为链表的头节点。链表有以下几种类型:

  • 单链表。其指针域只能指向节点的下一节点。
  • 双链表。每一个节点有两个指针域,一个指向上一节点,一个指向下一节点。可以向前查询,也可以向后查询。
  • 循环链表。循环链表的首尾相连。

链表通过指针域链接在内存中的各个节点。节点在内存中不是连续分布的。

Java中,链表节点的定义可以如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class ListNode {
int val; // 节点上存储的元素
ListNode next; // 下一个节点的对象
public ListNode(){} // 节点的默认构造函数
public ListNode(int val) { // 节点的有参构造函数
this.val = val;
this.next = null;
}
public ListNode(int val, ListNode next) { // 节点的有参构造函数
this.val = val;
this.next = next;
}
};

链表操作

删除节点

链表-删除节点

删除节点 D:

1
c.next = c.next.next;

删除后节点 D 仍然留在内存里,由于Java有自己的内存回收机制,可以不用额外处理。

添加节点

链表-添加节点

在节点 D 的前面添加节点 F:

1
2
3
ListNode f = new ListNode();
f.next = c.next; // 先修改要添加节点的 next 域
c.next = f; // 再修改节点 D 前面节点的 next 域

性能分析

链表-链表与数据性能对比

  • 数组长度固定,无法修改。
  • 链表长度不固定,可以动态增删