Array implementation of Doubly Linked List

Question

I need a way to implement a doubly linked list using only an array and no pointers in C. There's is a mention of this in Thomas Cormen but I can't think of a way to actually implement it.

You need an array of structs with two ints that are the prev and next indexes. — Paul Ogilvie
– Paul Ogilvie, Commented Jan 31, 2019 at 15:09

JeremyP · Accepted Answer · 2019-01-31 15:15:12Z

1

Instead of using pointers which, in C, are usually numbers that index into the address space, use integer indexes into your array as references to the previous and next members e.g.

struct Element 
{
    int next;
    int prev;
    // Any data you want for this element in the list 
};

struct Element array[MAX_ELEMENTS];

Then for the element at index i in the array, the next element in the list is

array[array[i].next]

and the previous element is

array[array[i].prev]

Instead of using NULL to mean a null pointer, use -1 to mean a "null" index.

answered Jan 31, 2019 at 15:15

JeremyP

87.4k15 gold badges129 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Paul Ogilvie Over a year ago

(or, for efficiency reasons, do not use array entry 0 so zero means "no next" or "no prev".)

JeremyP Over a year ago

@PaulOgilvie I thought of that, but it wastes an entry for probably marginal or zero gains in speed.

Collectives™ on Stack Overflow

Array implementation of Doubly Linked List

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related