**

线性表的顺序存储（顺序表）和链式存储（链表）

**

一、顺序表（SeqList)使用一维数组一次存放书元素。一维数组占用一块内存空间，每个存储单元的地址是连续的，通过下标识别元素，它的下标就代表了他的存储单元序号，也就表示了它的位置。

查找顺序表中的元素是方便的，根据下标就可以取出要取的元素。

当顺序表的容量不够时，顺序表不能就地扩容，要申请另一个更大容量的数组进行数组元素复制。Java源代码中的ArrayList类扩容实现过程是：先申请增加的容量是原本容量的二分之一，生成一个原本容量的二分之三的内存地址，再将所有元素进行复制过去。

对于插入、删除元素：先根据下标找到相应位置，若插入元素，将新插入插入位置后，将被加入位置的旧元素及之后的元素向后移动，移动次序是由后向前。若删除元素，将要删除的元素删除，其后的元素向前移动。插入和删除的操作时间主要用于移动元素。

二、线性表的链式存储结构(链表LinkedList)是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。存储一个数据元素的存储单元成为结点Node，单链表的表示方式：结点（数据域，地址域）。

对于单链表的操作：遍历操作是从第0个结点开始，沿着结点的Next链，依次访问单链表中的每个结点，并且每个节点只访问一次。插入（删除）操作：根据要插入（删除）的结点数，从第0个结点遍历找到要插入（删除）的位置，将要插入的数据元素插入（将要删除的元素删除），改变原来结点间的链接关系，不用移动数据元素。而操作所花的时间都在查找上面。

三、特殊的线性表（栈和队列）

（一）特殊之处在于插入和删除操作的位置受到限制：

若插入和删除的操作只允许在线性表的一端进行，则为栈(stack)，特点是先进后出；

若插入和删除操作分别在线性表的两端进行，则为队列(queue)，特点是先进先出。

（ps. 栈和线性表是不同的抽象数据类型，栈的概念不依赖于线性表而存在。）

（二）应用

栈是嵌套调用机制的实现基础：由于函数返回次序与调用次序正好相反，借助栈来实现记忆函数的路径，就能获得函数返回的路径，当函数被调用时，操作系统将该函数的有关信息（地址、参数、局部变量值等）入栈，称为保护现场；一个函数执行完返回时，出栈，获得调用函数信息，称为恢复现场，程序返回调用函数继续运行。

使用栈以非递归方式实现递归算法（存在直接或间接调用自身的算法称为递归算法）；

队列用于处理排队等待问题。（优先队列）

存储体  到  存储单元（地址访问）  到  存储原件（字节）


地址总线


如果一个电脑的中央处理器有二十根地址总线，那么它的最大的内存容量是1MB。
在存储器中含有大量的基本单元，每个存储单元可以存放八个二进制位，即一个零到二百五十五之间的整数、一个字母或一个标点符号等，叫做一个字节。存储器的容量就是以字节为基本单位的，每个单元都有唯一的序号，叫做地址。中央处理器凭借地址，准确地操纵着每个单元，处理数据。由于字节这个单位太小了，我们定义了几个更大的单位，这些单位是以2的十次幂做进位，单位有KB、MB、GB、TB等。

电脑的最大内存容量（字节数）等于2^地址总线的根数，所以，一个电脑的中央处理器有二十根地址总线，那么它的内存容量为2^20=1048576B，即1MB。


总线：地址总线，数据总线和控制总线（32位与64位的计算机差别会像想象那么大吗）


简单理解，就是说32位还是64位，或者是其它位。是指总线，不是指CPU。

　　32位的总线，只能识别到4G内存，再大的内存，因为没有编址空间了，所以不能使用。而64位理论上可以使用16EB的内存，但实际上支持不了，因为受总线限制。


　　虽然说我们在理想之中对于64机器内存的设想是2的64次方字节，具体的大小应该是在16EB（这是一个十分大的寻址范围，如果用GB表示的话，大约就是160亿GB），但是我们在现实之中是见不到这样大的存储器的，更令人可悲的是就算是64的CPU其寻址范围也不是我们在上文之中提到的那个天文数字。目前PC之上的64位机器的寻址范围是32GB，这就意味着就算是我们在64为机器之上就算是安装了Windows 64位旗舰版也不能操作32GB的内存。这是为什么呢？


　　要说明白这个问题我们首先应当是知道什么是地址总线，在PC机内部有着3大总线，这三大总线分别就是地址总线，数据总线和控制总线。而地址总线就是我们的CPU和内存通信的时候确定具体位置的通道。


　　虽然说目前64位的CPU一次性数据吞吐量是8字节，但是其与外界连接的地址总线并没有64位而仅仅是有35位，这我们就容易理解了。在32位的情况之下我们的寻址范围是4GB，而现在线路拓展了3个，那么就是需要乘以二的三次方，也就是4GB*8=32GB。正是如此64位机器最大也就是支持32GB的内存。

 

数组是由类型相同的数据元素构成的有序集合,每个数据元素称为一个数组元素,每个元素受(n>=1)个线性关系的的约束,每个元素在n个线性关系中的序号i1,i2...in称为该元素的下标,并称该数组为n维数组.

数组的存储结构与寻址
由于数组一般要求实现随机存取,所以一般采用顺序存储结构.由于内存单元是一维,而多维数组是多维的结构，所以采用顺序存储结构存储数组首先需要将多维结构映射到一维结构中.二维数组的每个元素含有两个下标,需要将其映射为一维关系。通常有两种映射方式:按行存储和按列存储.
C++是按行优先存储的.
设二维数组行下标和列下标分别为闭区间[L1, H1],[L2,H2];则按行优先存储的任意一元素Aij的地址可以用以下公式计算:LOC(Aij) = LOC(aL1L2) + ((i-L1)*(H2-L2+1) + (J-L2))*c

行下标[0,2] 列下标[0,3]

根据上述公式a[2][3] = a + 2*4 + 3 

按行存储的基本思想是,最右边的下标最先变化.
二维数组用寻址方式展示:

	int a[][4] = {{1,2,3,4},{5,6,7,8},{4,5,6,7}};
	for (int i = 0; i<3; i++) // 行下标
	{ 
		for (int j = 0; j<4; j++) // 列下标
		{
			printf("%d ",  *((int*)a + i*4 + j));
		}
		printf("\r\n");
	}
特殊矩阵的压缩存储:

1.对称矩阵:在一个n阶方阵中,有Aij = Aji(i>=0, j<=n-1)

{ 3 6 4 7 8

  6 2 8 4 2

  4 8 1 6 9

  7 4 6 0 5

  8 2 9 5 7

}

对称矩阵关于主对角线对称,因此只需要存储下三角(或上三角)部分即可.原来需要n*n个存储单元,

现在仅需要n*(n+1)/2个存储单元，一个S[n(n+1)/2]个元素的一维数组存储,aij存储在S[K]中,对于

下三角元素,i>=j有如下对应关系k = i*(i+1)/2+j;对于上三角元素,有如下对应关系:k = j*(j+1)/2+i

可以想象成求aij元素在下三角中的第几个元素,先求i*(i+1)/2(三角形面积),然后加上j.
压缩:

// 将一个对称矩阵压缩存储,并输出存储后的数组
// 入参:int** array 要压缩的对称矩阵
// n 对称矩阵阶数
// Compress 压缩后的数组
void CompressSymMatrix(int** array, int n, int Compress[])
{
	int k = 0;
	for(int i = 0; i<n; i++)
	{
		for (int j = 0; j<n; j++)
		{
			if (j<=i) // 存储下三角元素
			{
				Compress[k++] =  *((int*)array + i*n + j);
			}
		}
	}
}
解压:


// 将一个压缩矩阵解压成对称矩阵
// 入参:Compress[] 压缩的矩阵
// n n阶对称阵
// int** array 解压后的二维数组
void DeCompressSymMatrix(int Compress[], int n, int** array)
{
	for (int i = 0; i<n; i++)
	{
		for (int j = 0; j<n; j++)
		{
			int k = 0;
			// 压缩数组下标k与二维数组下标的对应关系
			if (i>j)
			{
				k = (i*(i+1))/2 + j;
			}else
			{
				k = (j*(j+1))/2 + i;
			}
		      *((int*)array + i*n + j) = Compress[k]; 
		}
	}
}
测试例子:


<span style="white-space:pre">	</span>int SymArray[5][5] = {{3,6,4,7,8},{6,2,8,4,2},{4,8,1,6,9},{7,4,6,0,5},{8,2,9,5,7}};
<span style="white-space:pre">	</span>printf("对称矩阵:\r\n");
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<5; j++)
		{
			printf("%d ", SymArray[i][j]);
		}
		printf("\r\n");
	}
	printf("将其压缩后:\r\n");
	int Compress[15] = {0};
	CompressSymMatrix((int**)SymArray, 5, Compress);
	for (int i = 0; i<15; i++)
	{
		printf("%d ", Compress[i]);
	}
	printf("将其解压后:\r\n");
	int DeArray[5][5] = {0};
	DeCompressSymMatrix(Compress, 5, (int**)DeArray);
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<5; j++)
		{
			printf("%d ", DeArray[i][j]);
		}
		printf("\r\n");
<span style="white-space:pre">	</span>}
	
2.三角矩阵

{3,c,c,c,c,

 6,2,c,c,c,

 4,8,1,c,c,

 7,4,6,0,c,

 8,2,9,5,7,

}

下三角矩阵与对称矩阵存储类似,只是需要多存储一个常数.需要存储空间为n(n+1)/2 + 1

aij与k的对应关系为:

 i>=j k = i*(i+1)/2 + j;

 i<j  k = n(n+1)/2

上三角矩阵:

与下三角矩阵存储类似:

aij与k的对应关系为:

i<=j k = i*(2n-i+1)/2+j-i

 i>j k = n*(n+1)/2
void CompressTriangle(int** array, int n, int compress[], bool bUp = true)
{
	int m = 0;
	for (int i = 0; i<n; i++)
	{
		for (int j = 0; j<n; j++)
		{
			if (bUp && (i >= j) )
			{
				compress[m++] = *((int*)array + i*n + j);
			}
			if ((!bUp) && (i<=j))
			{
				compress[m++] = *((int*)array + i*n + j);
			}
		}
	}
	if (bUp)
	{
			compress[(n*(n+1))/2] = *((int*)array + 1);
	}else
	{
			compress[(n*(n+1))/2] = *((int*)array + n);
	}
}
// 将压缩的下三角矩阵解压出来
// int** array 解压后的三角矩阵
// n N阶矩阵
// compress[] 压缩的一维数组
// bUp = true 上三角矩阵 bUp = false 下三角矩阵
void DeCompressTriangle(int** array, int n, int compress[], bool bUp = true)
{
	int m = (n*(n+1))/2;
	for (int i = 0; i<n; i++)
	{
		for (int j = 0; j<n; j++)
		{
			int k = 0;
			if (bUp)
			{
				if (i >= j)
				{
						k = (i*(i+1))/2 + j;
				}else
				{
						k = m;
				}
			}else
			{
				if (i<=j)
				{
					k = i*(2*n-i+1)/2 + j - i;
				}else
				{
					k = m;
				}
			}
			*((int*)array + i*n + j) = compress[k]; 
		}
	}
}
int UpTriArray[][5] = {{3,1,1,1,1}, {6,2,1,1,1},{4,8,1,1,1},{7,4,6,0,1},{8,2,9,5,7}};
int DownTriArray[][5] = {{3,4,8,1,0},{1,2,9,4,6},{1,1,1,5,7},{1,1,1,0,8},{1,1,1,1,7}};
<span style="white-space:pre">	</span>printf("下三角矩阵:\r\n");
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<5; j++)
		{
			printf("%d ", DownTriArray[i][j]);
		}
		printf("\r\n");
	}
	printf("将其压缩后:\r\n");
	int Compress[16] = {0};
	CompressTriangle((int**)DownTriArray, 5, Compress, false);
	for (int i = 0; i<16; i++)
	{
		printf("%d ", Compress[i]);
	}
	printf("将其解压后:\r\n");
	int DeArray[5][5] = {0};
	DeCompressTriangle((int**)DeArray,  5, Compress, false);
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<5; j++)
		{
			printf("%d ", DeArray[i][j]);
		}
		printf("\r\n");
	}
上三角矩阵的测试稍微改一下上面部分即可.

3.对角矩阵:

对角矩阵:在对角矩阵中,所有非0元素都集中在以主对角线为中心的带状区域中,除了主对角线和它的上下方若干条对角

线的元素外,其他元素都为0.

{2,1,0,0,0,

 9,3,4,0,0,

 0,7,5,3,0,

 0,0,5,4,2,

 0,0,0,1,1}

将一个m*n的w对角矩阵(w是占有非0元素对角线的个数,也成为带宽).压缩到m行,w列的二维数组B中.则Aij与Bts的映射关系

为:t = i; s = j - i + 1

// 入参: int** array 要压缩的对角矩阵
// m,n,w M行N列带宽w
// outArray 压缩后的矩阵
void CompressDiagonalMartix(int** array, int m, int n, int w, int** outArray)
{
	int t = 0;
	int s = 0;
	for (int i = 0; i<m; i++)
	{
		for (int j = 0; j<n; j++)
		{
			int value = *((int*)array + i*n + j);
			if (0 != value)
			{
				t = i; // 压缩到的行号
				s = j-i+1; // 压缩到的列号
				*((int*)outArray + t*w + s) = value;
			}
		}
	}
}

// 入参:int** array 要解压的对角矩阵
// m,n,w要解压出M行N列W带宽的对角矩阵.
// outArray解压后的对角矩阵
void DeCompressDiagonalMartix(int** array, int m, int n, int w, int** outArray)
{
	int t = 0;
	int s = 0;
	for (int i = 0; i<m; i++)
	{
		for (int j = 0; j<n; j++)
		{
			t = i; // 行
			s = j-i+1; // 列
			if (i==j || (j>i) && ((j - i) < ((w-1)/2 + 1)) || (i>j) && ((i-j) < ((w-1)/2 + 1)))
			{
				 *((int*)array + i*n + j) = *((int*)outArray + t*w + s);
			}else
			{
				*((int*)array + i*n + j)  = 0;
			}
		}
	}
}
测试:

<span style="white-space:pre">	</span>int DiagonalArray[5][5] = {{1,2,0,0,0},{3,4,5,0,0},{0,6,7,8,0},{0,0,9,3,1},{0,0,0,2,3}};
<span style="white-space:pre">	</span>int CompressDiagonalArray[5][3] = {0};
<span style="white-space:pre">	</span>printf("对角矩阵:\r\n");
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<5; j++)
		{
			printf("%d ", DiagonalArray[i][j]);
		}
		printf("\r\n");
	}
	printf("将其压缩后:\r\n");
	//int Compress[16] = {0};
	CompressDiagonalMartix((int**)DiagonalArray, 5, 5, 3, (int**)CompressDiagonalArray);
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<3; j++)
		{
			printf("%d ", CompressDiagonalArray[i][j]);
		}
		printf("\r\n");
	}
	printf("将其解压后:\r\n");
	int DeArray[5][5] = {0};
	DeCompressDiagonalMartix((int**)DeArray,  5, 5, 3, (int**)CompressDiagonalArray);
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<5; j++)
		{
			printf("%d ", DeArray[i][j]);
		}
		printf("\r\n");
	}
对角矩阵另一种存储方法是压缩到一维数组中,按行存储非0元素,k = 2i+j;
4. 稀疏矩阵的压缩存储

 稀疏矩阵的压缩存储

 稀疏矩阵是0元素居多的矩阵.

 1.对于稀疏矩阵,0元素分布没有规律.仅存储非0元素是没有用的,还要存储元素的行号和列号.

 即每个非0元素可以表示成如下三元组
template <class T>
struct element
{
	int row;
	int col;
	T data;
};
三元组顺序表,为了确定一个唯一稀疏矩阵,还要存储稀疏矩阵的行数,列数和非0元素的个数
const int MaxTerm = 256;
template <class T>
struct SparseMatrix
{
	element<T> data[MaxTerm];
	int rowCount; //  行数
	int colCount; //  列数
	int notZeroCount;
};
// 稀疏矩阵压缩存储
// 入参:int** array要压缩的稀疏矩阵
// m,nM行N列
// 出参:SparseMatrix& 输出存储的结构
void CompressSpareMatrix(int** array, int m, int n, SparseMatrix<int>& spareMatrix)
{
	// 对稀疏矩阵非0元素存储
	int nCount = 0;
	for (int row = 0; row < m; row++)
	{
		for (int col = 0; col < n; col++)
		{
			int value = *((int*)array + row*n + col);
			if (value != 0)
			{
				spareMatrix.data[nCount].data = value;
				spareMatrix.data[nCount].row = row;
				spareMatrix.data[nCount].col = col;
				nCount++;
			}
		}
	}
	spareMatrix.notZeroCount = nCount;
	spareMatrix.rowCount = m;
	spareMatrix.colCount = n;
}
// 稀疏矩阵对三元组顺序表的转置
// 1)直接取,顺序存
// 描述:依次从A矩阵寻找0,1..n-1列的三元组,找到之后交换行列位置存入B中.
void Trans1(SparseMatrix<int>& sparseMatrixA, SparseMatrix<int>& sparseMatrixB)
{
	sparseMatrixB.colCount = sparseMatrixA.rowCount;
	sparseMatrixB.rowCount = sparseMatrixA.colCount;
	sparseMatrixB.notZeroCount = sparseMatrixA.notZeroCount;
	int pb = 0;
	if (sparseMatrixA.notZeroCount > 0)
	{
		for (int col = 0; col < sparseMatrixA.colCount; col++)
		{
			for (int notZero = 0; notZero<sparseMatrixA.notZeroCount; notZero++)
			{
				if (sparseMatrixA.data[notZero].col == col)
				{
					sparseMatrixB.data[pb].row = sparseMatrixA.data[notZero].col;
					sparseMatrixB.data[pb].col = sparseMatrixA.data[notZero].row;
					sparseMatrixB.data[pb].data = sparseMatrixA.data[notZero].data;
					pb++;
				}
			}
		}
	}
}
2)顺序取,直接存
稀疏矩阵十字链表实现.

存储空间
上一章我们讲了冯诺依曼结构，其中很关键的一点是：存储空间分成若干存储单元，每个单元都有序号，单元内放置存储内容。
无论指令还是数据，物理上都存储在存储器里面，逻辑上都在存储空间之中。
存储单元和存储在里面的信息，可以类比成编号的货架和放置在其上的货物（见下图）：

前些章反复说过，所谓数据结构就是数据的组织方式。
现在我们已经把数据类比成了货物，那么对于数据的组织方式，自然就是存放这些货物的方式啦。
所有“货物”（数据或指令）都是在放在“仓库”（存储空间）里的“货架”（存储单元）上的，那么不同的“货物存放”方式，自然指的就是：
以何种原则对仓库中的货架进行分配；
如何将货物码放上去。
数组：一块连续的存储空间
存储空间的大小
数组在被创建的时候就分配到了一块存储空间，这块空间的大小和两个因素有关：
数组中每个元素的大小——一般情况下每个元素的大小由其数据类型决定，不同数据类型的元素占据空间可能不同。
数组的长度——这个数组最多可以容纳多少个元素。
关于数据类型是一个专门的话题，有一定的复杂度，此处暂不涉及。现在大家只需要知道：本课中我们要处理的都是整（数）型（integer）数据。
在数据结构既定的情况下，数组占据的存储空间与数组的长度成正比。
分配存储空间
我们在程序中创建一个数组的时候，需要指定它的长度。
计算机在运行程序的时候，根据数组长度计算出它所需要占用空间的大小（占用空间大小 = 单个元素大小 x 数组长度），一下子把所需要的空间全都分配出来。
在程序结束之前，这块儿空间都会属于这个数组，不会用于存储其他的数据。即使自始至终这个数组是空的，里面没有任何数据，这块空间也会空在那里，不做他用。
这就好比，我告诉仓库管理员：给我留10个（也可以是100个，10000个，或者一百万个……）架子，我要装货，于是这10个架子就归我了。

在我通知管理员不再使用它们之前，这些货架就放在那里。我可以往上面放任意我想放的货物（当然数据类型要相符），我也可以任由它一直空着，或者有一部分放货物，有一部分空着。

数组的下标
存储单元的绝对地址
地址空间中的每个存储单元都有对应的地址——在此可以简单地理解为一个序号。这个序号是固定不变的，任何时候这个单元都是这个号——这叫做存储单元的绝对地址。
也就是说，仓库中的每个货架都有自己的仓库统一编号，始终如一。
数组元素的相对位置标号
当我们创建了一个数组后，这个数组可以承载的元素个数就确定了。但是这个数组从具体那个存储单元开始位置是不确定的。
也就是说，我们申请到了一系列的货架，这些货架是一个个挨着一个的，货架的个数也是确定的，但具体从什么位置开始，却是不一定的。
在这种情况下，我们可以给数组中每一个元素一个相对位置的标号，这个标号就是每一个元素相对数组头部（数组的头部即整个数组的第1个元素所在位置）的偏差值。
一个数组：第1个元素位置与数组“头部”的偏差（相对位置）为0，那么我们就给它标号为0；第2个元素位置和头部偏差为1，那么它的标号1；……；第n个元素位置和头部的偏差为（n-1），因此第n个元素所在位置的标号为（n-1）。
假设某个数组长度为10，则最后一个元素所在位置与头部的偏差为9，于是最后一个元素所在位置的标号就是9。
所有这些相对位置，都是在数组创建时就已经确定了的。各个位置上，无论有没有元素，位置标号都是客观存在的，且在这个数组中是不变的。
数组、数组的存储和元素下标
下面这些货架，原本各有各的仓库统一编号（从90000000开始）。但是在它们被分给一个名叫arr，长度为10的整型数组之后，每一个准备放未来整型数值的位置就都有了一个新的、相对于arr头部位置的标号，这个标号从0开始，逐个递增1。


  
小贴士：大家可能注意到了，每个位置的原始编号不是递增1而是递增4，这是因为在这里我们假设每个整型值的大小为4个字节（byte）。
  
字节是计算机领域衡量数据大小的基本单位，整型是表示整数的数据类型，同一种数据类型中每个个体的大小都是一样的，具体大小和编程语言有关系。
  
在大多数编程语言中，整型值都是4个字节。而Python的整型比较特殊，这个到后面再讲。这里我们姑且认为一个整型数值占位4个字节。

现在回顾一下数组的示意图，下图表示一个名为arr，长度为10的数组：

0-9是arr数组中各个元素的下标，根据上面的解释大家知道，下标对应的是数组中每个元素位置的标号，也就是该元素位置相对于数组头部的偏差。
数组中的元素
数组中的元素
数组被创建出来以后，我们就可以把元素放进去了，就好像用货物把货架装满一样：

假设上图对应的数组是下面这样：

现在我们来看这个数组：
数组名：arr
数组长度：10
起始元素下标：0
相邻位置下标增幅：1
数组的元素值
那么我们如何指出数组中的各个元素呢？比如，我们想要知道上面arr数组中第4个元素对应的数值是什么（在上面例子中对应的值是35），怎样告知计算机我们的想法呢？
在现在大多数的编程语言中，我们会用这个符号来指代arr数组中的第4个元素：arr[3]
具体来看就是这样：

这个组合表示的就是：


也就是说，在大多数编程语言里，我们用arr[i]来表示名为arr的数组中第（i+1）个元素的值，这里的i应该是一个大于等于0，小于数组arr长度的整数。一般情况下，如果i小于0，或者大于等于数组的长度，程序就会报错。
数组的特性
固定存储空间
综上，在最初的设计层面上，数组是依赖内存分配形成的，在使用数组前必须先为它申请空间。这使得数组这种数据结构具有了下面这样的特性：
一个数组占据的存储空间大小固定，不能改变；
所占据的存储空间是专用的，不能被其他信息占据；
所占据的存储空间是连续性的，中间不能间隔其他的信息；
数组中的各个元素可以用数组名和下标直接访问。
优点
这样的数据结构肯定是很方便的，要读要写都很直接。
无论多长的数组，要访问其中某一个元素，只要知道它的下标，就能一步到位，直接访问对应的元素。
缺点
它的弊病也非常明显：
1.太占地儿！
一开始就要把以后所有要用的存储空间都申请下来，就算很长时间里装不满，也不许存入其他信息。空置的空间是很可惜的。
现在，虽然存储设备越来越便宜了，可是大数据时代又来了，要存的数据也多。空间总不是可以随意浪费的。
2.修改困难。
理论上讲，一个数组如果没装满，那么所有的空置位置都应该在尾部，而不是到处乱空。
比如下面两图，左边是错的，右边就是对的。

这样的话，如果给数组中加入新元素，则只能加在尾部，如果要插入到中间位置，就要有一些元素被移动（如下图）:

反过来，如果删除掉一个元素，也得把后面的再往前挪一位（如下图）:

连续存储惹的祸
所有这些限制，都是因为数组是连续的一块存储空间，且各元素由下标标识引起的。如果不遵守这些限制，数组相应的好处也就得不到了。
计算机中大部分的任务主要需要读取（看看货架子上的货物是什么），需要写入（把货放到货架上去）的任务相对较少。而对于读取任务，数组还是有着它得天独厚的优势的。
不过，万一我们遇到的就是写入较多的任务，或者虽然读取比较多，但数据动态性很强（里面元素有时很多，有时很少）的任务，该怎么办呢？
这时候我们可以启用另一种数据结构：链表——请看下一章。