链表的数组实现令链表的所有元素在数组中保持紧凑《算法导论》10.34

• 让长度为m的链表的所有元素占用数组的前m个位置。


• 假设数组总长度为SIZE，用一个变量freeHead记录空闲表的起始下标, 则[freeHead, SIZE)的范围内的对象全部属于自由表。用一个Object对象list表示链表头。


• 当从链表的任意位置删除元素时，比如下标为pos的元素，那么就让下标为pos和freeHead-1的元素互换在链表中的位置，然后删除互换后下标为freeHead-1的元素，也就相当于删除了互换前下标为pos的元素，这样一来，就可以保证所删除元素的位置始终是自由表头freeHead的前一个位置，于是保持了自由表中元素下标的连续性。freeHead将数组元素分为前半部分的链表元素和后半部分的自由元素。

#include
#include
using namespace std;
struct Object
{
int prev;
int key;
int next;
};
constexpr int SIZE = 10;
Object array[SIZE];
int freeHead = 0;
Object list;
void Init()
{
list.prev = -1;
list.next = -1;
}
int AllocateObject()
{
if(freeHead == SIZE)
return -1;
array[freeHead].prev = array[list.next].prev;
array[freeHead].next = array[list.prev].next;
array[list.next].prev = freeHead;
array[list.prev].next = freeHead;
return freeHead++;
}
void FreeObject(int pos)
{
assert(pos >= 0 && pos int listTail = --freeHead;
//delete array[pos] from list
array[array[pos].prev].next = array[pos].next;
array[array[pos].next].prev = array[pos].prev;
//move array[listTail] to array[pos]
array[pos] = array[listTail];
int listTailPrev = array[listTail].prev;
int listTailNext = array[listTail].next;
array[listTailPrev].next = pos;
array[listTailNext].prev = pos;
}
void Test()
{
Init();
for(int i = 0; i != SIZE; ++i)
cout < cout < cout < for(int i = 0; i != SIZE/2; ++i)
FreeObject(i); //释放下标为0 1 2 3 4的5个元素
for(int i = 0; i != SIZE/2; ++i)
cout < cout <}
//运行结果为
0 1 2 3 4 5 6 7 8 9
-1
5 6 7 8 9