在动手之前我一直以为静态链表和动态链表没有什么差别，细细一想才发现，原来静态链表之中隐藏着一个非常值得讨论的话题——内存管理。
静态链表的“静态”二字是指内存的来源为静态内存（通常用全局数组）。与动态链表不同，在静态链表中节点内存的申请与释放都需要自行维护，由于这里是链表，也很容易想到将空余的节点链接起来形成一个free_list，每次需要时从free_list头部取出一个节点，释放时再将节点加到头部，这样就能够非常容易的实现链表的其他操作。
代码如下:
// 静态链表 的实现
#include
#define MAXN 16 // capacity of list.
typedef int element; // element type.
// define boolean type:
typedef int bool;
#define true -1
#define false 0
#define NPTR -1 // null pointer definition. can not between 0 to MAXN-1.
typedef int pointer;
#define DEBUGVAL(x) printf("%s: %dn", #x, (x)); // a macro for debug.
struct __node
{
element data;
pointer next;
}SLList[MAXN];
pointer ifree, idata;
#define nextof(p) SLList[p].next
#define dataof(p) SLList[p].data
#define _alloc(d) ifree; dataof(ifree)=(d); ifree != NPTR ? ifree=nextof(ifree) : NPTR
#define _free(p) nextof(p)=ifree; ifree = p
void init()
{
int i;
ifree = 0;
idata = NPTR;
for( i=0; i < MAXN-1; i++)
nextof(i) = i+1;
nextof(i) = NPTR;
}
// clear all nodes.
void clear() { init(); }
// push val to front.
bool push_front(element val)
{
pointer tmp, np;
if( ifree != NPTR ) {
np = _alloc(val);
nextof(np) = idata;
idata = np;
return true;
}
return false;
}
// push val to end of list.
bool push_back(element val)
{
if( idata == NPTR ) { // 空表，直接写入
idata = _alloc(val);
nextof(idata) = NPTR;
return true;
}
if( ifree != NPTR ) { // 非空，先找到最后一个节点
pointer last = idata, np;
while( nextof(last) != NPTR ) last = nextof(last);
np = _alloc(val);
nextof(np) = NPTR;
nextof(last) = np;
return true;
}
return false;
}
// insert val to after p pointed node.
bool insert_after(pointer p, element val)
{
if( ifree != NPTR && p != NPTR ) {
pointer pn = _alloc(val);
nextof(pn) = nextof(p);
nextof(p) = pn;
return true;
}
return false;
}
// insert to the position in front of p.
bool insert(pointer ptr, element val)
{
if( ifree == NPTR ) return false; // 没有结点，直接返回
if( ptr == idata ) { // 有一个节点
pointer np = _alloc(val);
nextof(np) = idata;
idata = np;
return true;
}
else { // 其他情况，先找 ptr 的前驱，再插入
pointer p = idata;
while( p != NPTR ) {
if( nextof(p) == ptr ) { // find p -- the prev node of ptr.
return insert_after(p, val); // insert val after p.
}
p = nextof(p);
}
}
return false;
}
// find element, return the prev node pointer.
pointer find_prev(element val)
{
pointer p = idata;
while( p != NPTR ) {
if( dataof( nextof(p) ) == val )
return p;
p = nextof(p);
}
return NPTR;
}
// find element, return the node pointer.
pointer find(element val)
{
pointer p = idata;
while( p != NPTR ) {
if( dataof(p) == val ) return p;
p = nextof(p);
}
return NPTR;
}
// pop front element.
void pop_front()
{
if( idata != NPTR ) { // 将 data list 最前面的节点 移到 free list 上
#if 0
pointer p = idata;
idata = nextof(idata); // idata = nextof(idata);
nextof(p) = ifree; // SLList[p].next = ifree;
ifree = p;
#else
pointer p = idata;
idata = nextof(idata);
_free(p);
#endif
}
}
// pop back element.
void pop_back()
{
if( idata == NPTR ) return;
if( nextof(idata) == NPTR ) { // only 1 node.
nextof(idata) = ifree;
ifree = idata;
idata = NPTR;
}
else { // 找到最后一个节点 p，以及它的前驱 q.
// TODO: find the last node p, and it's perv node q.
pointer p = idata, q;
while( nextof(p) != NPTR ) {
q = p;
p = nextof( p );
}
// remove *p to free list, update nextof(q) to NPTR.
nextof(p) = ifree;
ifree = p;
nextof(q) = NPTR;
}
}
void show()
{
pointer p = idata;
for( ; p != NPTR; p = nextof(p) ) {
printf(" %3d ", dataof(p) );
}
printf("n");
}
#define INFOSHOW
void info()
{
#ifdef INFOSHOW
int i;
DEBUGVAL(ifree);
DEBUGVAL(idata);
puts("====================n"
"indextdatatnextn"
"--------------------");
for(i=0; i