Я думаю, что лучшим подходом в этом случае является использование предварительно выделенного двусвязного списка ...
// Untested code... just to give the idea
struct Node
{
int data;
Node *prev, *next;
static Node *first, *last, *free;
// Allocates a new node before the specified node or
// at the end of the list if before is NULL
static Node *alloc(int data, Node *before)
{
// Check the free list first
Node *n = free;
if (!n)
{
// There are no free nodes... allocate a bunch of them
Node *page = new Node[1000];
for (int i=0; i<999; i++)
{
page[i].next = &page[i+1];
}
page[999].next = NULL;
n = free = &page[0];
}
// Update the free list
free = n->next;
// Link the new node to neighbors
n->next = before;
n->prev = before ? before->prev : last;
if (n->prev) n->prev->next = n; else first = n;
if (n->next) n->next->prev = n; else last = n;
// Initialize it
n->data = data;
return n;
}
// Deallocates a node, placing it in the free list for reuse
static dealloc(Node *n)
{
if (n)
{
// Remove from double chain
if (n->next) n->next->prev = n->prev; else last = n->prev;
if (n->prev) n->prev->next = n->next; else first = n->next;
// Add to free list
n->next = free; free = n;
}
}
};
Когда вам нужно выделить узел, просто позвоните Node::alloc, передавая данные и куда поместить узел. Когда вам нужно освободить его, просто вызовите узел dealloc.
Узлы размещаются в «страницах» и повторно используются после освобождения. Это сводит к минимуму количество обращений к диспетчеру памяти и может значительно ускорить процесс.
Двухсвязной структуре никогда не потребуется перемещать существующий узел, пока он находится в памяти (поэтому указатели не нужно настраивать). Также легко изменить порядок элементов, например, добавив метод Node::moveTo(Node *before).
Недостаток этого подхода заключается в том, что для доступа к n-му элементу, заданному индексу, требуется операция O (n).