Is it possible to build a linked list without the help of self referential structure?

Question

Is it possible to build a linked list without the help of self referential structure? I.e. like this just using a pointer:

struct list{
    int data;
    int *nxt;
};

instead of

struct list{
    int data;
    struct list *nxt;
};

Answer 1

Sure. You could use void * instead of struct list * as your nxt member. For example:

struct list {
    int data;
    void *nxt;
};

Alternatively, if you're prepared to build in a guarantee that the nodes of the list will be stored into an array (which is great for cache locality and insertion speed), you could use a size_t.

struct list {
     int data;
     size_t nxt;
};

If your implementation provides uintptr_t (from <stdint.h>), you could merge these two types into one:

struct list {
    int data;
    uintptr_t nxt;
};

Answer 2

Another approach is to use parallel arrays as your "heap"¹, with one array containing your data (whether a scalar or a struct) and another to store the index of the next "node" in the list, like:

int data[N];
int next[N];

You'll need two "pointers" - one to point to the first element in the list, and one to point to the first available "node" in your "heap".

int head;
int free;

You'll initialize all the elements in the "next" array to "point" to the next element, except for the last element which points to "null":

for ( int i = 1; i < N-1; i++ )
  next[i-1] = i;
next[N-1] = -1;
free = 0;  // first available "node" in the heap
head = -1; // list is empty, head is "null" 

Inserting a new element in the list looks something like this (assuming an ordered list):

if ( free != -1 )
{
  int idx = free;    // get next available "node" index;
  free = next[free]; // update the free pointer 
  data[idx] = newValue;
  next[idx] = -1;

  if ( head == -1 )
  {
    head = idx;
  }
  else if ( data[idx] < data[head] )
  {
    next[idx] = head;
    head = idx;
  }
  else
  {
    int cur = head;    
    while ( next[cur] != -1 && data[idx] >= data[next[cur]] )
      cur = next[cur];
    next[idx] = next[cur];
    next[cur] = idx;
  }
}

Deleting an element at idx is pretty straightforward:

int cur = head;
while ( next[cur] != idx && next[cur] != -1 )
  cur = next[cur];

if ( next[cur] == idx )
{
  next[cur] = next[idx];  // point to the element following idx
  next[idx] = free;       // add idx to the head of the free list
  free = idx;             
}

Advantages of this approach:

1. No dynamic memory management;
2. No self-referential structures;
3. Data items are stored contiguously in memory, which may lead to better caching performance.

Disadvantages:

1. In this simple approach, list sizes are fixed;
2. Any usefully large arrays will have to be declared static, meaning your binary may have a large footprint;
3. The convention of using -1 as "null" means you have to use a signed type for your indices, which reduces the number of available elements for a given array type.

You could certainly use 0 as "null" and count all your indices from 1; this allows you to use unsigned types like size_t for your indices, meaning you can make your arrays pretty much as big as the system will allow. It's just that 0 is a valid array index whereas -1 (usually) isn't, which is why I chose it for this example.

---

^{1. Welcome to my Data Structures class, ca. 1987, which was taught using Fortran 77. Parallel arrays were pretty much the answer for everything (lists, trees, queues, etc.)}

Answer 3

You might have a look at how linked lists are implemented in the Linux kernel.

Compared to the classical linked lists:

struct my_list{
    void *myitem;
    struct my_list *next;
    struct my_list *prev;
};

using a linked list in the linux kernel looks like:

struct my_cool_list{
    struct list_head list; /* kernel's list structure */
    int my_cool_data;
};

Source

Answer 4

Yes, it's possible.

What you're proposing is type punning, and you'll probably get away with it with most compilers on most platforms, but there's not a single good reason to do it in the first place and many good reasons not to.