编程时会经常使用到链表这种结构，数组与链表这两种数据结构的区别以及优点不再赘言。在链表频繁使用时，可能会遇到这种问题，那就是可能要频繁的申请和释放内存，这样可能会造成内存碎片，对于很多程序是不希望看到的。那我在这里介绍我这两天写的一种链表，它能够消除内存频繁分配和释放、使用内存不连续的特点，当然水平有限，希望各位朋友提出宝贵意见，我能把这个数据结构和算法实现的更好，可供大家参考。
（一）介绍一下普通的链表结构
//节点的数据结构
struct HNode
{
void* data; //此节点所存放的对象的地址
HNode* next;
HNode* last;
};
//链表的数据结构
struct HList
{
HNode* header;
HNode* tail;
};
int hlist_empty(HList& list);
int hlist_clear(HList& list);
int hlist_push_back(HList& list, void* data);
int hlist_push_front(HList& list, void* data);
int hlist_insert(HList& list, void* data1, void* data2);
int hlist_delete(HList& list, void* data);
简单链表算法的实现：
#pragma once
#include "stdafx.h"
#include "list.h"
//链表的初始化操作
int hlist_empty(HList& list)
{
list.header = list.tail = 0;
return 1;
}
//链表的清空操作，释放所有内存
int hlist_clear(HList& list)
{
HNode* node = list.header;
HNode* next;
while (0 != node)
{
next = node->next;
delete node;
node = next;
}
return 1;
}
int hlist_push_back(HList& list, void* data)
{
HNode* newNode = new HNode;
newNode->data = data;
newNode->next = 0;
newNode->last = list.tail;
if (0 == list.header)//空链表
{
list.header = list.tail = newNode;
}
else//非空链表
{
list.tail->next = newNode;
list.tail = newNode;
}
return 1;
}
int hlist_push_front(HList& list, void* data)
{
HNode* newNode = new HNode;
newNode->data = data;
newNode->last = 0;
newNode->next = list.header;
if (0 == list.header)//空链表
{
list.header = list.tail = newNode;
}
else
{
list.header->last = newNode;
list.header = newNode;
}
return 1;
}
int hlist_insert(HList& list, void* data1, void* data2)
{
bool find = false;
HNode* node = list.header;
HNode* next;
while (0 != node)
{
next = node->next;
if(node->data == data1)
{
HNode* newNode = new HNode;
newNode->data = data2;
newNode->last = node;
newNode->next = next;
node->next = newNode;
if (0 != next)
{
next->last = newNode;
}
else
{
list.tail = newNode;
}
find = true;
break;
}
node = next;
}
if(find)
return 1;
return 0;
}
int hlist_delete(HList& list, void* data)
{
HNode* node = list.header;
HNode* next;
bool find = false;
while (0 != node)
{
next = node->next;
if(data == node->data)
{
if (node->last == 0 && node->next == 0)
{
delete node;
list.header = list.tail = 0;
}
else if(node->last == 0 && node->next != 0)
{
delete node;
list.header = next;
}
else if(node->last != 0 && node->next == 0)
{
list.tail = node->last;
list.tail->next = 0;
delete node;
}
else
{
node->last->next = next;
node->next->last = node->last;
delete node;
}
find = true;
break;
}
node = next;
}
if (find)
{
return 1;
}
return 0;
}
（二）内存自管理的链表
上边是用C语言实现的最简单的数据结构和算法了。下面介绍避免内存碎片的链表的数据结构和使用方法。
#define Herror int
//节点
struct HNode
{
void* data;
HNode* next;
HNode* last;
};
//内容链表
typedef struct tag_HLink
{
HNode* header;
HNode* tail;
}HLink;
//删除链表
typedef struct tag_HLinkDel
{
HLink del;
HNode** buf;
unsigned int size;
int index;
int nBuf;
}HLinkDel;
//链表管理
typedef struct tag_HList
{
HLink link;
HLinkDel link_del;
}HList;
Herror hlink_empty(HLink& link);
Herror hlink_push_back(HLink& link, HNode* newNode);
Herror hlink_push_front(HLink& link, HNode* newNode);
Herror hlink_insert(HLink& link, void* data1, HNode* newNode);
Herror hlink_delete(HLink& link, void* data, HNode* &nodeDel);
Herror hlink_find(HLink& link, void* data, HNode* &nodeFind);
Herror hlinkdel_empty(HLinkDel& linkdel, unsigned int size = 1024, int nBuf = 16);
Herror hlinkdel_clear(HLinkDel& linkdel);
Herror hlinkdel_pop(HLinkDel& linkdel, HNode* &node);
Herror hlinkdel_push(HLinkDel& linkdel, HNode* node);
Herror hlinkdel_alloc(HLinkDel& linkdel);
Herror hlist_emtpy(HList& list);
Herror hlist_clear(HList& list);
Herror hlist_push_back(HList& list, void* data);
Herror hlist_push_front(HList& list, void* data);
Herror hlist_insert(HList& list, void* data1, void* data2);
Herror hlist_delete(HList& list, void* data);
上述代码中的HNode节点与（一）中的一样。HLink与（一）的HList一样。而出现了一个HLinkDel和HList结构体，它是做什么用处呢？
像（一）中的链表，在添加或者插入新节点时才分配内存，删除节点也是立即释放此节点的内存。在进行一系列操作之后，链表中的节点在内存中的位置可能会很乱。如果频繁的使用插入和删除操作，则会产生内存碎片。在上边的代码中，我们用HLinkDel这个结构体来管理所有需要的内存。在创建链表时，会预先分配1024个节点的内存，即1024 * sizeof(HNode)个字节。这个数组首尾相连构成了HLinkDel成员del链表。即一个HList对象里，里边有两个链表，一个是真正的正在使用的link对象，另一个是管理着已经分配好内存的，等待着供link使用的linkdel的del链表。
（1）创建HList对象时，link为空，linkdel按照参数或者默认的为linkdel.buf创建16个HNode*的数组，全部赋值为0，再分配1024*sizeof(HNode)大小的内存块，其内存地址赋给linkdel.buf[0]，内存块中的所有节点连接起来交给del链表。
（2）link增加或者插入节点时，从linkdel对象的del链表中取出一个节点，给link使用，当然del链表中去掉此节点。
（3）link删除一个节点时，把删除的节点交给linkdel对象，加入到它的del链表中。
（4）在使用了一段时间后，发现linkdel中的del链表已经空了，那么表明，之前分配的内存已经用完了，那么我们给linkdel.buf[1]再分配1024 * Sizeof(HNode) * 2 的内存，再给linkdel的del链表使用。
（5）在最终使用完后，直接将linkdel中的buf数组中指向的每个内存块释放，再释放buf数组，就可以了。
实现代码如下：
#pragma once
#include "stdafx.h"
#include "HList.h"
//内容链表
Herror hlink_empty(HLink& link)
{
link.header = 0;
link.tail = 0;
return 1;
}
Herror hlink_push_back(HLink& link, HNode* newNode)
{
newNode->last = link.tail;
newNode->next = 0;
if(link.tail == 0)
{
link.tail = link.header = newNode;
}
else
{
link.tail->next = newNode;
link.tail = newNode;
}
return 1;
}
Herror hlink_push_front(HLink& link, HNode* newNode)
{
newNode->last = 0;
newNode->next = link.header;
if (0 == link.header)
{
link.header = link.tail = newNode;
}
else
{
link.header->last = newNode;
link.header = newNode;
}
return 1;
}
Herror hlink_insert(HLink& link, void* data1, HNode* newNode)
{
bool find = false;
HNode* node = link.header;
HNode* next;
while (0 != node)
{
next = node->next;
if(node->data == data1)
{
find = true;
newNode->last = node;
newNode->next = node->next;
node->next = newNode;
if(0 == next)
{
link.tail = newNode;
}
else
{
node->next->last= newNode;
}
break;
}
node = next;
}
if(find)
return 1;
return 0;
}
Herror hlink_delete(HLink& link, void* data, HNode* &nodeDel)
{
HNode* node = link.header;
HNode* next;
bool find = false;
while (0 != node)
{
next = node->next;
if(data == node->data)
{
find = true;
nodeDel = node;
/*if(next == 0)
{
node->last->next = 0;
}
else
{
next->last = node->last;
node->last->next = next;
}*/
if(0 == next && 0 == node->last)
{
link.header = link.tail = 0;
}
else if (0 == next && 0 != node->last)
{
node->last->next = 0;
link.tail = node->last;
}
else if (0 != next && 0 == node->last)
{
node->next->last = 0;
link.header = node->next;
}
else
{
next->last = node->last;
node->last->next = next;
}
break;
}
node = next;
}
return 1;
}
Herror hlink_find(HLink& link, void* data, HNode* &nodeFind)
{
bool find = false;
HNode* node = link.header;
HNode* next;
while (0 != node)
{
next = node->next;
if(data == node->data)
{
nodeFind = node;
find = true;
break;
}
node = next;
}
if(find)
return 1;
return 0;
}
//删除链表
Herror hlinkdel_empty(HLinkDel& linkdel, unsigned int size, int nBuf)
{
hlink_empty(linkdel.del);
linkdel.size = size;
linkdel.nBuf = nBuf;
linkdel.index = -1;
linkdel.buf = new HNode*[nBuf];
for (int i = 0; i < nBuf; i++)
{
linkdel.buf[i] = 0;
}
hlinkdel_alloc(linkdel);
return 1;
}
Herror hlinkdel_alloc(HLinkDel& linkdel)
{
linkdel.index++;
int n = linkdel.index;
unsigned int len = linkdel.size * (1 << n);
linkdel.buf[n] = new HNode[len];
HNode* p;
for (unsigned int i = 0; i < len; i++)
{
p = linkdel.buf[n] + i;
p->data = 0;
p->next = p + 1;
p->last = p - 1;
}
p = linkdel.buf[n];
p[len-1].next = p[0].last = 0;
linkdel.del.header = p;
linkdel.del.tail = p + len - 1;
return 1;
}
Herror hlinkdel_clear(HLinkDel& linkdel)
{
for (int i = 0; i < linkdel.nBuf; i++)
{
delete []linkdel.buf[i];
}
delete []linkdel.buf;
linkdel.buf = 0;
hlink_empty(linkdel.del);
linkdel.index = -1;
linkdel.nBuf = 0;
linkdel.size = 0;
return 1;
}
Herror hlinkdel_pop(HLinkDel& linkdel, HNode* &node)
{
HLink& del = linkdel.del;
if(del.header != 0)
{
node = del.header;
if(del.tail == node)
{
hlinkdel_alloc(linkdel);
}
else
{
del.header->next->last = 0;
del.header = del.header->next;
}
}
else if(del.header == 0)
{
hlinkdel_alloc(linkdel);
hlinkdel_pop(linkdel, node);
}
return 1;
}
Herror hlinkdel_push(HLinkDel& linkdel, HNode* node)
{
node->last = linkdel.del.tail;
node->next = 0;
linkdel.del.tail->next = node;
linkdel.del.tail = node;
return 1;
}
//链表管理
Herror hlist_emtpy(HList& list)
{
hlink_empty(list.link);
hlinkdel_empty(list.link_del);
return 1;
}
Herror hlist_clear(HList& list)
{
hlinkdel_clear(list.link_del);
return 1;
}
Herror hlist_push_back(HList& list, void* data)
{
HNode* newNode;
hlinkdel_pop(list.link_del, newNode);
newNode->data = data;
hlink_push_back(list.link, newNode);
return 1;
}
Herror hlist_push_front(HList& list, void* data)
{
HNode* newNode;
hlinkdel_pop(list.link_del, newNode);
newNode->data = data;
hlink_push_front(list.link, newNode);
return 1;
}
Herror hlist_insert(HList& list, void* data1, void* data2)
{
//产生新节点
HNode* newNode;
hlinkdel_pop(list.link_del, newNode);
newNode->data = data2;
//插入新节点
hlink_insert(list.link, data1, newNode);
return 1;
}
Herror hlist_delete(HList& list, void* data)
{
//在内容链表中删除此节点
HNode* nodeDel = 0;
hlink_delete(list.link, data, nodeDel);
//在删除链表中加入此节点
if(nodeDel != 0)
{
hlinkdel_push(list.link_del, nodeDel);
}
else
{
return 0;
}
return 1;
}
这两天全部时间都在写这个链表的代码了，从各方面我也考虑了很多，但是毕竟个人水平有限，希望大家多提修改意见，能让这个算法更好用。供更多人参考和使用。
提前感谢所有的建议和批评！
