时间复杂度: 一般看的是最坏的情况

1.数组:

是一块连续的内存 , 需要初始化是执行元素,或者长度;

数组可以通过索引,时间复杂度**O(1)**访问元素

数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

2.链表:

是一块不连续的内存 , 所以长度是不可变的;

链表的组成单位是节点（node）对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”

链表查找元素需要从头到尾查找 , 所以时间复杂度是O(n)

链表分为: 1.单向链表 2.双向链表(相较于单向链表维护了一个prev节点) 3.循环链表(尾节点的下一个是收节点):也分为双向循环链表和单向循环链表

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

单项链表:

1
2
3
4
5
6
/* 链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向下一节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

双向链表:

1
2
3
4
5
6
7
/* 双向链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向后继节点的引用
    ListNode prev;  // 指向前驱节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}
image-20260312194004145

3.列表(List)

列表（list）是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。

1
2
3
4
5
6
/* 初始化列表 */
// 无初始值
List<Integer> nums1 = new ArrayList<>();
// 有初始值（注意数组的元素类型需为包装类 Integer[]）
Integer[] numbers = new Integer[] { 1, 3, 2, 5, 4 };
List<Integer> nums = new ArrayList<>(Arrays.asList(numbers));

拼接两个链表

1
2
3
4
5
6
/* 拼接两个列表 */
 List<Integer> list2=new ArrayList<>(Arrays.asList(new Integer[]{6,7,8,9,0}));
        list1.addAll(list2);
        for (Integer i : list1) {
            System.out.println(i);
        }

排序列表

1
2
/* 排序列表 */
Collections.sort(list1);  // 排序后，列表元素从小到大排列

列表实现

许多编程语言内置了列表，例如 Java、C++、Python 等。它们的实现比较复杂，各个参数的设定也非常考究，例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。

为了加深对列表工作原理的理解，我们尝试实现一个简易版列表，包括以下三个重点设计。

  • 初始容量：选取一个合理的数组初始容量。在本示例中，我们选择 10 作为初始容量。
  • 数量记录：声明一个变量 size ，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容。
  • 扩容机制：若插入元素时列表容量已满，则需要进行扩容。先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组。在本示例中，我们规定每次将数组扩容至之前的 2 倍。ArrayList初始容量为0,第一次添加元素时容量变为10,每次扩容为1.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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* 列表类 */
class MyList {
    private int[] arr; // 数组（存储列表元素）
    private int capacity = 10; // 列表容量
    private int size = 0; // 列表长度（当前元素数量）
    private int extendRatio = 2; // 每次列表扩容的倍数

```java
/* 构造方法 */
public MyList() {
    arr = new int[capacity];
}

/* 获取列表长度（当前元素数量） */
public int size() {
    return size;
}

/* 获取列表容量 */
public int capacity() {
    return capacity;
}

/* 访问元素 */
public int get(int index) {
    // 索引如果越界，则抛出异常，下同
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("索引越界");
    return arr[index];
}

/* 更新元素 */
public void set(int index, int num) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("索引越界");
    arr[index] = num;
}

/* 在尾部添加元素 */
public void add(int num) {
    // 元素数量超出容量时，触发扩容机制
    if (size == capacity())
        extendCapacity();
    arr[size] = num;
    // 更新元素数量
    size++;
}

/* 在中间插入元素 */
public void insert(int index, int num) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("索引越界");
    // 元素数量超出容量时，触发扩容机制
    if (size == capacity())
        extendCapacity();
    // 将索引 index 以及之后的元素都向后移动一位
    for (int j = size - 1; j >= index; j--) {
        arr[j + 1] = arr[j];
    }
    arr[index] = num;
    // 更新元素数量
    size++;
}

/* 删除元素 */
public int remove(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("索引越界");
    int num = arr[index];
    // 将将索引 index 之后的元素都向前移动一位
    for (int j = index; j < size - 1; j++) {
        arr[j] = arr[j + 1];
    }
    // 更新元素数量
    size--;
    // 返回被删除的元素
    return num;
}

/* 列表扩容 */
public void extendCapacity() {
    // 新建一个长度为原数组 extendRatio 倍的新数组，并将原数组复制到新数组
    arr = Arrays.copyOf(arr, capacity() * extendRatio);
    // 更新列表容量
    capacity = arr.length;
}

/* 将列表转换为数组 */
public int[] toArray() {
    int size = size();
    // 仅转换有效长度范围内的列表元素
    int[] arr = new int[size];
    for (int i = 0; i < size; i++) {
        arr[i] = get(i);
    }
    return arr;
}
```

}

image-20260312210011015

image-20260312210521720

在做算法题时，我们会倾向于选择基于数组实现的栈，因为它提供了更高的操作效率和随机访问的能力，代价仅是需要预先为数组分配一定的内存空间。

如果数据量非常大、动态性很高、栈的预期大小难以估计，那么基于链表实现的栈更加合适。链表能够将大量数据分散存储于内存的不同部分，并且避免了数组扩容产生的额外开销。

为什么数组要求相同类型的元素，而在链表中却没有强调相同类型呢？

链表由节点组成，节点之间通过引用（指针）连接，各个节点可以存储不同类型的数据，例如 int、double、string、object 等。

相对地，数组元素则必须是相同类型的，这样才能通过计算偏移量来获取对应元素位置。例如，数组同时包含 int 和 long 两种类型，单个元素分别占用 4 字节和 8 字节 ，此时就不能用以下公式计算偏移量了，因为数组中包含了两种“元素长度”。

1
# 元素内存地址 = 数组内存地址（首元素内存地址） + 元素长度 * 元素索引

4.栈

栈（stack）是一种遵循先入后出逻辑的线性数据结构。栈可以基于链表实现,也可以基于数组实现;

我们可以将栈类比为桌面上的一摞盘子，规定每次只能移动一个盘子，那么想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构

常用方法 push() pop() peek()查看栈顶元素 size() isEmpty()

5.队列

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开;

常用方法和栈类似; peek() 查看队首的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 初始化队列 */
Queue<Integer> queue = new LinkedList<>();

/* 元素入队 */
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);

/* 访问队首元素 */
int peek = queue.peek();

/* 元素出队 */
int pop = queue.poll();

/* 获取队列的长度 */
int size = queue.size();

/* 判断队列是否为空 */
boolean isEmpty = queue.isEmpty();

6.双向队列

在队列中，我们仅能删除头部元素或在尾部添加元素。如图 5-7 所示，双向队列（double-ended queue）提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作

基于双向链表实现或者环形数组实现

image-20260317142908730 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 初始化双向队列 */
Deque<Integer> deque = new LinkedList<>();

/* 元素入队 */
deque.offerLast(2);   // 添加至队尾
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3);  // 添加至队首
deque.offerFirst(1);

/* 访问元素 */
int peekFirst = deque.peekFirst();  // 队首元素
int peekLast = deque.peekLast();    // 队尾元素

/* 元素出队 */
int popFirst = deque.pollFirst();  // 队首元素出队
int popLast = deque.pollLast();    // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
boolean isEmpty = deque.isEmpty();

7.哈希表