6

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?

1
  • 2
    What about redefining the node in a linked list by replacing the reference to next node with the index of next node?
    – Terry Li
    Oct 6, 2011 at 21:31

5 Answers 5

7

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.

2
  • if I implement a linked list as an array will it lead to better utilization of cache lines ?
    – gansub
    Oct 13, 2018 at 10:11
  • Yes, it will. This is perhaps one of the greatest advantages. Apr 9, 2020 at 10:14
1

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.

6
  • Yes, the type issue seems like a restriction. Also - how to efficiently find free space in the array when elements are removed?
    – Joel
    Oct 5, 2011 at 18:45
  • 2
    Store objects/structs (I don't know if Java has structs) containing the value and the index as two fields. And to store free space, simply keep two linked lists in the same array, one of all the free elements and one with all the in-use elements. Oct 5, 2011 at 18:50
  • 3
    You'd typically want to track free space with a linked list of free nodes. So, you have (at least) one "pointer" (index) to the beginning of the in-use elements, and another to the free elements. When you free an element, you add it to the free list. When you need an element, you unlink it from the free list. Oct 5, 2011 at 18:50
  • @LasseV.Karlsen: Yes, if you have structs -- but almost inevitably, if you have structs, you have better alternatives to this in general. Real use would be with something like Fortran 77 that had neither structs nor pointers. Oct 5, 2011 at 18:52
  • @Jerry Coffin - so two arrays are required (one with values, one to track free space) for reasonable performance?
    – Joel
    Oct 5, 2011 at 18:58
1

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.

0

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
4
  • My C++ isn't great, but assuming you had a java style "int[] array" how does this work: "Each index in the array contains a doubly linked list." ?
    – Joel
    Oct 5, 2011 at 18:43
  • 1
    This answer hasn't implemented a linked list using an array, he has just stored ordinary linked lists in the array. Oct 5, 2011 at 18:45
  • @LasseV.Karlsen I'd argue that the definition of "implement" is a grey line. I didn't implement it from the ground up, my implementation uses a pre-built linked list instead. But I see now that you're right and the OP was looking for something from the ground up. @Joel My Java isn't great, but I think you can also create arrays as int array[] just as how I did in my example. In my example, I have an array of linked lists of type int (i.e. linked lists within an array).
    – Dennis
    Oct 6, 2011 at 4:34
  • @Dennis the OP asks for implementing a linked list by using array as an underlying data structure, i.e. storing the nodes within the array. Each node has (array) indexes instead of pointers. Please consider modifying your answer or deleting it altogether as it is not providing any valuable information.
    – Ziezi
    Jun 14, 2017 at 9:57
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.