How do you implement a linked list within an array?
Here is a possible approach(using C++): your node would be consisted of indexes to the next and previous elements in the list:
struct Link
{
// additional data
int next;
int prev;
};
where next
and prev
will hold indexes of the array storing the Link
s.
Link** head; // = new Link*[initial_size];
int first; // -1 initially (analogue of nullptr)
int last; // index of the last element in the array: head
additionally, there should be a mechanism accounting for the available elements in the array, the more naive implementation could be:
bool* available; // = new bool[initial_size]; // all initialized to true
you would need functions to get you an index from bool available
(indicating no node at index, i
in head
, where the element of available
has a value true
). For example:
int get_available_index()
{
for (int i = 0; i < initial_size; ++i)
{
if (available[i] == true)
{
available[i] == false;
return i;
}
}
// indicate / throw list full / resize???
}
Here is how puch_back()
could look like:
void push_back(Link** head, Link* new_link)
{
// chech pointer validity
int index = get_available_index();
// probably using: placement new(), to construct a node in that location
// new(head + index) new_link;? or just
head[index] = new_link;
if (last != -1) // list not empty
{
head[last]->next = index;
head[index]->prev = (last - head[0]); // gives you the index of the last node
}
else
{
first = index;
head[index]->prev = -1;
}
last = index;
head[index]->next = -1;
}
Additionally there should be a function reverse to get_available_index()
in which available[i]
element is set to true
(and object is destroyed (head + i)->~Link();
?)
Can this done be efficiently considering that items will need to be removed & inserted from the list - presumably requiring identification of free elements in the array?
Is far as I can understand there will be fragmentation, reflected in the values stored in the bool
array, which will affect only the time it takes to store a new node.