顺序存储和链式存储-数据结构与算法教程

1. 再谈数组—顺序存储

我们在开始计算机课程没多久后就已经知晓了数组的概念，数组作为一个顺序储存方式数据结构为我们的程序设计带来了大量的便利，几乎任何的高级程序设计，算法设计都离不开数组的灵活使用，但是，数组最大的缺点就是我们的插入和删除时需要移动大量的元素，显然这需要消耗大量的时间。

以C语言数组插入一个元素为例，当我们需要在一个数组{1,2,3,4,5,6,7}的第1个元素后（即第2个元素）的位置插入一个’A’时

我们需要做的有，将第1个元素后的整体元素后移，形成新的数组{1,2,2,3,4,5,6,7}，再将第2个元素位置的元素替换为我们所需要的元素’A’,最终形成我们的预期，一个简单的插入操作要进行那么多的步骤，显然不是很核算。

由示意图的操作，我们可以看出这样做的弊端有二

其一：所需要移动的元素很多，浪费算力。

其二：必须为数组开足够多的空间，否则有溢出风险。

2. 链表—链式存储

C语言使用中，由于以上出现的这些问题，我们链表的概念就应运而生，链表通过不连续的储存方式，以及指针的灵活使用，巧妙的简化了上诉的内容，同时链表是自适应内存大小的，也就是说无论我们设多大的数据，理论上都可以实现（当然不能超过你的机器承载），注意，有许多较晚的语言通过底层的方式解决了数组插入和删除时的时间浪费，如PYTHON。

链表的基本思维是，利用结构体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互练习，串联，这就形成了我们的链表。

（图为单链表的一个结点结构）

其中DATA为自定义的数据类型，可以是简单的int型，也可以是复杂的struct结构体类型，而NEXT为指向下一个链表结点的指针，通过访问NEXT，可以引导我们去访问链表的下一个结点。

对于一连串的结点而言，就形成了我们的链表：

我们要进行上文所说的插入删除操作也就相当简单，只需要修改指针所指向的区域就可以了，不需要进行大量的数据移动操作。

相比起数组，链表解决了数组不方便移动，插入，删除元素的弊端，但相应的，链表付出了更加大的内存牺牲换来的这些功能的实现。

上文介绍的是单链表，接下来的本章节会依次给各位介绍：单链表，双链表，循环单链表，其功能不同但实现方式均大同小异。

（图示为接下来学习的几种链表的区别）