为了编程的顺利进行，自然有一种控制复杂性的措施。而且复杂性的控制从编程语言一开始的时候就有了，成为所谓的内部模式：内建的数据结构，甚至是语言机制里面的内容。现在我们看一些常见的数据类型。
数组
按照Wiki的要求，应该按照数据结构和数据类型两个不同的角度讲数组array。作为数据结构的数组是由一系列元素（值或者变量）构成的，每个元素数数组由键或者索引来标识。按照要求，数组里的元素的存储应该可以按照数学公式来计算，也就是说，数组的标识不能是简单的字符串，而要使用一个域，特别是使用整数来标识。
数组在历史上出现得是非常早的，经常作为列表list以及字符串string的实现。在现代计算机当中，内存通常都是按照一维数组的方式来计算的。而现代计算机中的优化，特别是向量处理机，都是针对数组的操作而优化的。（数据结构就是数据结构，跟它们使用硬件或者软件实现并没有关系）。
数组的一个大优势在于所使用的下标可以在运行时候被计算出来。但是需要注意的是，在底层数据结构也可能非常复杂。数组可能用哈希表、链表、查找树等结构实现。总而言之，底层数据结构与顶层数据结构有很大的不同。1945年John von Neumann写了第一个数组排序的算法。
作为抽象数据类型的列表，包含的操作有：
- 创建一个空表；
- 测试当前列表是否为空；
- 添加一个元素到列表的第一个位置；
- 添加一个元素到列表的最后位置；
- 得到列表的第一个元素；
- 引用列表中除了第一个元素之外的其它元素。
对于特定类型的列表，具有如下的操作规范：
- nil: () \(\to\) L
- cons: E \(\times\) L \(\to\) L
- first: L \(\to\) E
- rest: L \(\to\) L
with the axioms
- first (cons (e, l)) = e
- rest (cons (e, l)) = l
for any element e and any list l. It is implicit that
- cons (e, l) \(\neg\) l
- cons (e, l) \(\neg\) e
- cons (e1, l1) = cons (e2, l2) if e1 = e2 and l1 = l2