基础数据结构

基本的数据结构类型

数组

最常用的数据结构

在内存中申请一块固定长度连续空间，可通过下标来访问

1	array = malloc(n);

因为内存需要提前申请，所以在使用上如果遇到可变长度的存储需求时，需要频繁申请新的内存块，会有严重的内存开销问题，所以引入了链表

链表

以节点为存储单元，一个节点包含值与下一个节点的地址

1
2
3

linkNode = malloc(2);
linkNode[1] = value;
linkeNode[2] = &nextNode;

可根据存储需求临时开辟存储空间。但是在访问单个节点上效率又没有数组来的快捷，需要从头节点逐个遍历至 i。
现代编程语言大多实现了 List 类型的数据结构综合两者的优缺点，实现了可变长度且可通过下标访问成员。

List

通过内部算法，动态开辟符合长度的内存空间来满足长度需求，不同编程语言的实现方法也会不一样。
一下简述一下个人对于 List 一种实现方案

设置一个合适长度的子数组 (subArray) 长度 k , 根据 List 的长度动态创建以及销毁子数组。
设置一个链表 (nodes) 存储子数组的头节点。
内置长度计数器 count
访问 List[i] = nodes[i % k][int(i / k)]

队列

先进先出，特点是优先处理最早加入的节点

广度搜索中应用此结构辅助记录每次需要搜索的节点。

栈

先进后出，特点是优先处理最近加入的节点

深度搜索中应用此结构辅助记录每次需要搜索的节点。

队列和栈是两个老生常谈的结构，实现方法有多种。在这里就不详述了,需要的可以自行查找。

hash表

给定一个 key 值，通过 hask 函数 adress = hash(key), 获得 key 对应的固定地址。如果有多个key 返回同样的hash值,通过冲突解决函数来获得偏移地址。 hash 表虽然在实现的描述上性能优越，可变长度，快速访问。但是在编程语言中的实现还是需要落在实处，需要基础的数组，链表来实现。

脚本语言中的 Dictionary 类实现

这里举例一个字典的实现。
两个链表，一个存储 hask 值一个存储 value 的引用，从图中可以看出，虽然字典获得快速访问优势，但是付出了更多的空间代价。