数组和链表

一、计算机内存的工作原理

为了更好的理解数组和链表，先来简单介绍一下计算机内存的工作原理。简单来说：计算机像是很多抽屉的集合体，每个抽屉都有地址。如下图： fe0ffeeb是一个内存单元的地址（细抠起来，这个图形有问题：实际上，计算机的内存是一维的，而图形是二维的）。

需要将数据存储到内存时，请求计算机提供存储空间，计算机给一个存储地址。需要存储多项数据时，有两种基本方式：数组和链表。

二、数组和链表

1.数组

数组中所有元素占用连续的内存，所以通过数组首元素地址，可以计算每个元素的地址。元素的位置称为索引，数组的索引从0开始，几乎所有的编程语言都从0开始对数组元素进行编号。在同一个数组中,所有元素的类型都必须相同(都为int、double等)。数组具有以下特点：

1. 知道每个元素的地址，支持随机访问方式；时间复杂度O(1)
2. 插入元素时，可能导致元素的移动，最坏情况下，会移动所有元素；由于数组需要连续的内存，当前内存可能无法满足元素的存储，需要重新分配内存空间和进行元素的拷贝；插时间复杂度O(n)
3. 删除元素后,必须将后面的元素都向前移；时间复杂度O(n)

2.链表

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。