数组和链表可以说是非常常见的一种数据结构了，他们都是一种线性表数据结构（即一条线一样的结构，每个线性表上的数据最多只有前和后两个方向）。数组用一组连续的内存空间，来存储一组具有相同类型的数据，具有很好的随机访问性能。而链表通过指针来连接不同的节点，对于插入删除等操作非常方便。
## 线性表 && 非线性表
线性表是指数据元素之间存在一对一的线性关系，即除了第一个和最后一个元素，其它元素都有且只有一个直接前驱和直接后继。而非线性表则是指数据元素之间不是简单的前后关系，比如二叉树、堆、图等
数组
数组（Array）是一种线性表数据结构。它用一组连续的固定内存空间，来存储一组具有相同类型的数据。
这种数据结构我们都很熟悉，因为很多编程语言中，都会有数组这种数据类型。由于它在内存上是连续的，所以随机访问非常方便，直接通过下标即可：a[i] = base_address + i * data_type_size。因此，如果数组的下标是从1开始的话，那么在取值的时候需要：a[i] = base_address + （i-1） * data_type_size，因此下标从0开始反而可以减少一次运算。
由于它的数据类型相同，因此 data_type_size 也是一样的。到这里我产生了一个疑问：
js 的数组可以不停的push和没有类型限制，还是真正意义上的数组吗？
然后chatGPT告诉我：
在 JavaScript 中，数组不是基本类型，而是具有以下核心特征的 Array 对象：JavaScript 数组是可调整大小的，并且可以包含不同的数据类型。因此，JavaScript 中的数组不是真正意义上的数组，但是它们仍然可以像数组一样使用。
然后我又问：那么golang的数组是真正意义上的数组吗？
chatGPT答：
在 Golang 中，数组是一种长度固定的数据类型，它由相同类型的元素组成。数组中的元素可以是任何类型，包括基本类型和自定义类型。数组在内存中是连续的，因此可以通过索引访问数组中的元素，这使得访问数组元素的速度非常快。
因此，我想你心中已经有答案了。
根据下标随机访问的时间复杂度为 O(1)，同时数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效,如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。因此，当你的数据不需要排序的时候，如果往第k个下标插入元素，可以选择将之前k位的元素追加到末尾，然后将新元素直接放在k下标，这样就可以避免大规模的数据搬移。
链表
链表是由一系列节点组成的，每个节点包含两部分内容：数据以及一个指向下一个节点的指针。常用的链表有单链表、双向链表和循环链表。
- 单链表：有一个指向下一个节点的指针
- 循环链表：在单链表的基础上将最后一个节点的下一个节点指针指向第一个
- 双向链表：不仅有一个指向下一个节点的指针，还有一个指向上一节点的指针
- 双向循环链表：在双向链表的基础上将最后一个节点的下一个节点指针指向第一个，将第一个节点的上一个节点指针指向最后一个节点。
单项链表示例
type Node struct {
Value int
Next *Node
}
type LinkedList struct {
Head *Node
}
func (l *LinkedList) Add(value int) {
node := &Node{Value: value}
if l.Head == nil {
l.Head = node
} else {
current := l.Head
for current.Next != nil {
current = current.Next
}
current.Next = node
}
}
这段代码定义了一个 Node 结构体，它包含一个整数类型的 Value 和一个指向下一个节点的指针 Next。LinkedList 结构体包含一个指向头节点的指针 Head。Add 方法用于在链表末尾添加新节点。如果链表为空，则将新节点设置为头节点；否则，遍历链表直到找到最后一个节点，然后将新节点添加到最后一个节点的 Next 指针上。
删除和插入节点也非常方便，我们只需要改变相应的指针指向就行了。
链表具有动态性、高效的插入和删除等特点，常被应用于大量数据的存储和操作场景
总结
数组和链表都是数据结构中的线性结构，但是它们的实现方式不同。数组是一种静态数据结构，它在内存中分配一段连续的空间来存储元素，而链表则是一种动态数据结构，它通过指针来连接不同的节点。这两种数据结构之间的主要区别在于以下几点：
- 数组在内存中分配一段连续的空间来存储元素，而链表则通过指针来连接不同的节点，因此链表不需要在内存中分配一段连续的空间。
- 数组的元素个数是固定的，而组成链表的节点个数可按需要增减。
- 数组元素的存储单元在数组定义时分配，链表节点的存储单元在程序执行时动态向系统申请。
- 数组中的元素顺序关系由元素在数组中的位置（即下标）确定，而链表中的元素顺序关系由节点之间的指针关系确定。
- 数组利用下标定位，时间复杂度为O(1)，而链表定位元素时间复杂度O(n)；
- 数组插入或删除元素的时间复杂度O(n)，而链表插入或删除元素的时间复杂度O(1)。
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。