戳这里【总目录】回到算法系列总目录
数组和链表是每一种编程语言当中最基本的数据类型。掌握这两者的数据结构和特性，同时区分这二者的差别，是程序员的基本功。
一、数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。这里有两个关键字，第一是线性表，有前后顺序，而不是树、图等非线性结构。第二个是连续的内存空间和相同类型的数据。这两个特性决定了数组的一个最重要的特性是：随机访问。
当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式（其中 data_type_size 表示数组中每个元素的大小），计算出该元素存储的内存地址：
a[i]_address = base_address + i * data_type_size
因而这里有一个很好的问题：“数组和链表的差别”，常见的说法是：链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)。这里的说法并不完全正确，数组适合查找操作，但是查找的时间复杂度并不为 O(1)。好的排序算法用二分查找，时间复杂度也是 O(logn)。因此，正确的回答是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。如果在数组的末尾插入元素，不需要移动数据了，这时的时间复杂度为 O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。
用容器还是数组？
针对数组类型，很多语言都提供了容器类，比如Java的Collection集合，容器优势就是封装了很多数组操作的细节，比如数组插入、删除时需要搬移其他数据等。另外，最显著的一点就是支持动态扩容。比如ArrayList，当空间不够时会按照1.5倍大小进行扩容，因为扩容涉及到内存申请和数据搬迁，操作较为耗时，因此最好能在初始化的时候指定容器大小。另外如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
对于业务开发，直接使用容器足矣，省时省力。一点点性能的降低，完全不会影响到系统整体的性能。但如果做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
为什么数组要从 0 开始而不是1开始编号
如果数组从 1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为：
a[k]_address = base_address + (k-1)*type_size
从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。
二、链表
链表通过指针将一组零散的内存块串联在一起。其中，把内存块称为链表的“结点”，为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，把这个记录下个结点地址的指针叫作后继指针 next。链表可分为：单链表、双向链表和循环链表
- 针对链表的插入和删除操作，只需考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。
- 链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。
三、算法考察
数组链表领域中主要可考察的是链表，比较经典的题目如下：
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
以第一个题目为例，单链表的反转，可以参考LetCode上此题【Reverse Linked List】，本人采用了Go语言实现，通过循环节点指针来反转指向达到要求：
type Node struct {
value int
next *Node
}
func reverseList(cur *Node) *Node{
//前节点
pre:=new(Node)
pre.next = nil
//后节点
next:=new(Node)
next.next=nil
for cur!=nil {
//保存头节点的下一个节点，
next = cur.next
//将头节点指向前一个节点
cur.next =pre
//更新前一个节点
pre = cur
//更新头节点
cur = next
}
return pre
}
func printNode(head *Node) {
for head != nil {
//fmt.Print(head.value, "\t")
fmt.Println(head)
head = head.next
}
fmt.Println()
}
func main() {
node1 := new(Node)
node1.value = 1
node2 := new(Node)
node2.value = 2
node3 := new(Node)
node3.value = 3
node4 := new(Node)
node4.value = 4
node1.next = node2
node2.next = node3
node3.next = node4
printNode(node1)
head := reverseList(node1)
printNode(head)
}
结果示例：
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
网友评论