1.我们为什么要用动态数据数据结构呢？

因为类型相同的数据用数组存储存在许多的问题：
(1)定义静态数组时必须指定数组的元素个数，此后无法更改数组大小，带来很多的不便，可能造成空间浪费或不足。
(2)用指针可以申请动态数组，空间不会浪费或不足，由于动态申请的空间必须是连续的区域，所以当申请“大片”的连续区域时，有可能会失败。
(3)在数组中插入或删除元素时需要大量移动元素，效率低。

所以动态数据结构就出现了！

态数据结构：
(1)可以利用动态内存分配，实现动态数组，克服数组大小固定的问题。
(2)但仍然不能解决插入、删除时移动大量元素的问题。
(3)可以使用链表克服上述问题。

2.单链表

(1) 链表是一种是最常用的动态数据结构，它是对动态获得的内存进行组织的一种结构。

(2)与数组不同，数组元素逻辑上相邻物理地址上也相邻, 而链表结构其数据元素作为一个个结点的数据域。

(3)结点中另有指针域存储逻辑上相邻的其他元素的起始地址，单链表较常用。

链表结构的优点是：

(1)系统不必为应用程序分配一组连续的空间，可以充分利用系统的零散空间,有一个元素就生成一个结点，空间不浪费。
(2)如果内存空间足够大，理论上这一批数据的容量不受限制。
(3)对于插入、删除等操作不必通过移动元素实现，效率高。

一个单链表示例：

C++ 动态数据结构（一）