表（list）简介及实现

表（list）简介及实现2013-05-24表

表（list）是常见的数据结构。从数学上来说，表是一个有序的元素集合。在C语言的内存中，表储存为分散的节点（node）。每个节点包含有一个元素，以及一个指向下一个（或者上一个）元素的指针。如下图所示:

表: 橙色储存数据，蓝色储存指针

图中的表中有四个节点。第一个节点是头节点（head node），这个节点不用于储存元素，只用于标明表的起始。头节点可以让我们方便的插入或者删除表的第一个元素。整个表中包含有三个元素（5， 2， 15）。每个节点都有一个指针，指向下一个节点。最后一个节点的指针为NULL，我们用“接地”来图示该指针。

表的功能与数组（array）很类似。数组也是有序的元素集合，但数组在内存中为一段连续内存。在数组中，我们通过跳过固定的内存长度，来方便的找到某个元素。在上图表示的表中，我们则必须沿着指针联系起的长链，遍历查询相应的元素。但数组需要有固定的大小，表则可以根据运行情况插入或者删除节点。插入节点时需要从进程空间的堆中开辟内存空间，用以储存节点。删除节点可以将节点占据的内存归还给进程空间。

删除节点, free释放内存