数组

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

性质：

• 数组下标都是从0开始的；
• 数组内存空间的地址是连续的；
• 数组的元素不能删除，只能覆盖。

局限： 因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址；

注：使用C++，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组

不同编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void test_arr() {
    int array[2][3] = {
		{0, 1, 2},
		{3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

测试地址为：

1
2

0x7ffee4065820 0x7ffee4065824 0x7ffee4065828
0x7ffee406582c 0x7ffee4065830 0x7ffee4065834

链表

定义： 一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。

链表的类型：

• 单链表： 上述提及的就是单链表；单链表中的指针域只能指向节点的下一个节点。
• 双链表： 每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双链表既可以向前查询也可以向后查询。

• 循环链表： 链表首尾相连，可以用来解决约瑟夫环问题。

  

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

1
2
3
4
5
6

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

不定义构造函数也可以，C++默认生成一个构造函数，但不会初始化成员变量，不能直接给变量赋值！如：

• 自己定义构造函数初始化节点：

  1	ListNode* head = new ListNode(5);

• 使用C++默认构造函数初始化节点：

  1 2	ListNode* head = new ListNode(); head->val = 5;

链表的操作

删除节点

只要将C节点的next指针 指向E节点就可以了。

D节点依然存留在内存里，在C++里最好是再手动释放这个D节点(delete node)，释放这块内存。

其他语言例如Java、Python，有自己的内存回收机制，就不用自己手动释放了。

添加节点

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

• 数组定义时，长度固定，如果想改动数组长度，需要重新定义一个新的数组。适合数据量固定，频繁查询，较少增删 的场景。
• 链表长度可以不固定，且可以动态增删， 适合数据量不固定，频繁增删，较少查询 的场景。