How do you implement a linked list within an array

Question

This question mentions that it is possible to go about implementing a linked list within an array.

Whilst I can imagine how to do this with multiple arrays, how can it be done with a single array?

EDIT: 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?

Answer 1

You could use a fixed-size memory block allocator where each block has a next-pointer pointing to the next element in the linked list.

A good and simple implementation is from the Contiki operating system (BSD license), see implementation of memb and list.

You use them like this:

struct connection {
    struct connection *next;
    /* ... */
};

/* This allocates a fixed size array of 16 'struct connection' */
MEMB(connection_mem, struct connection, 16);

/* This is just a void ** keeping track of list elements in a linked list */
LIST(connection_list);

void main()
{
    /* Initialize the memory block */
    memb_init(&connection_mem);

    /* Allocate a new chunk */
    struct connection *c = memb_alloc(&connection_mem);
    if(c != NULL) {
        /* Add to list */
        list_add(connection_list, c);
    }

    for(c = list_head(connection_list); c != NULL; c = c->next) {
        /* ... */
    }
}

Edit: Sorry, you did not mention any particular programming language and I'm mostly familiar with C and C++. If you can decipher how memb and list is implemented then the basic theory should be the same: A simple block allocator keeping track of free/used blocks, and a linked list implementation that can refer to these individual blocks.

Answer 2

You could (for example) have a linked-list of integers by putting your first data item in the element of the array, and the index of the next item in the second element. This would restrict you to storing types that were compatible with/convertible to an index.

Answer 3

If it is an array of objects, then each object would store a value and a pointer to the next object.

[0] -> {"a",1}
[1] -> {"b",2}
[2] -> {"c",4}
[3] -> {"1",5}
[4] -> {"d",7}
[5] -> {"2",6}
[6] -> {"3",8}
[7] -> {"e",-1}
[8] -> {"4",-1}

So here I have 2 linked lists, the first one:

"a" -> "b" -> "c" -> "d" -> "e"

and the second one:

"1" -> "2" -> "3" -> "4"

both using an index of -1 as the end of the list.

Then you would need multiple pointers (one for each list) to determine where you are in the list.

Honestly, I'm not even sure I understand the question, but wanted to throw out ideas anyway.

Answer 4

In C++ I quickly wrote this and it works. Each index in the array contains a doubly linked list.

#include <list>
#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
  list<int> ll[10];
  for (int i = 0; i < 10; i++)
    for (int j = 100; j > 0; j-=10)
      ll[i].push_back(j);

  list<int>::iterator it;
  for (int i = 0; i < 10; i++)
  {
    for (it = ll[i].begin(); it != ll[i].end(); it++)
    {
      cout << " " << *it;
    }
    cout << endl;
  }
  return 0;
}

output:

$ g++ ll-in-array.cpp && ./a.out
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10

Answer 5

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 Links.

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.