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

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