|
《Windows游戏编程大师技巧》（第二版）第11章(2) 警告
不要沉迷于静态数组！例如，假如你有一个大小为4KB的结构，而且可能有1到256个该结构类型的数组。为防止某些时候数组元素的个数达到256而产生溢出错误，采用静态分配内存方法时必须为之分配1MB的内存。这时，你显然需要更好的方法——采用链表或动态分配的数组来分配内存，以避免浪费。 链表
对于那些在程序启动或编译时可以预估的、简单的数据结构，数组是最合适的处理方法。但对于那些在运行时可能增大或缩小的数据结构而言，应当使用链表（linked list）这类形式的数据结构处理方法。图11-1表示了一个标准的、抽象的链表结构。一个链表由许多节点构成。每个节点都包含信息和指向表中下一个节点的指针。 图11-1：一条链表
链表用起来很酷，因为你可以将一个节点插入到链表的任意位置，同样也可以删除任意位置的节点。图11-2示意了节点插入链表的情形。由于在运行时可以插入或删除带有信息的节点，使得作为游戏程序的数据结构，链表很具吸引力。 图11-2：往链表中插入节点
链表惟一的缺点是你必须一个接一个地遍历节点来寻找你的目标节点（除非创建第二个数据结构来帮助查询）。例如，假定你要定位一个数组中的第15个元素，你只需这样便可以访问它：
players[15]
但对于链表，你需要一个遍历算法以访问链表的节点来定位目标节点。这意味着在最坏的情况下，查询的重复次数与链表的长度相等。这就是O(n)。O记号说明在有n个元素的情况下要进行与n同阶次数的操作。当然，我们可以采用优化算法和附加的包含排序索引表的数据结构，来达到与访问数组几乎同样快的速度。 创建链表
现在来看一看如何创建一个简单的链表、增加一个节点、删除一个节点，以及搜索带有给定关键字的数据项。下面是一个基本节点的定义：
typedef struct NODE_TYP
{
int id; // id number of this object
int age; // age of person
char name[32]; // name of person
NODE_TYP *next; // this is the link to the next node
// more fields go here
} NODE, *NODE_PTR;
为了访问一个链表，需要一个head指针和一个tail指针分别指向链表的头节点和尾节点。开始时链表是空的，因而头尾指针均指向NULL：
NODE_PTR head = NULL,
tail = NULL;
注意
Some programmers like to start off a linked list with a dummy node that's always empty. This is mostly a choice of taste. However, this changes some of the initial conditions of the creation, insertion, and deletion algorithms, so you might want to try it.
有些程序员喜欢以一个总是为空的哑元节点（即不表示实际数据的节点）作为一个链表的开始节点。这通常是个人习惯问题。但这会影响链表节点创建、插入和删除的算法中的初始条件，你不妨试一试。
遍历链表
出人意料的是，遍历链表是所有链表操作中最容易实现的。
1. 从head指针处开始。
2. 访问节点。
3. 链接到下一节点。
4. 如果指针非NULL，则重复第2、3步。
| 
