Doubly linked list, under the hood

Question

Lets say you have 2 classes:

 - Node
 - Doubly linked list (DLL)

Your main creates a bunch of nodes, who know something about themselves, like their name for example and then calls add(Node*) method of the DLL.

In order to keep track of these Node pointers, (i would think) DLL should maintain an array of them. Is there a way to avoid it? (or any other data structure for that matter)

How is DLL implemented under the hood? Does it use arrays or something else?

Answer 1

There is a way to avoid it. You in fact don't need to keep track of all the pointers in the one spot at all, because the Nodes themselves ARE the data structure.

EDIT: Just saw your Objective-C comment.

The Node should have (Objective-C syntax):

// the actual info at this list index
@property (retain) id ptr;

@property (retain) Node *previous;
@property (retain) Node *next;

And then your DLL class is simply a class with:

@property (retain) Node *first;
@property (retain) Node *last;
@property (assign) NSUInteger count;

That's all you need. Inserting or deleting a Node involves pointer shuffling and a count adjustment, and access is sequential from either end.

add:(Node*)newNode would literally be:

[newNode setPrevious:[self last]];
[[self last] setNext:newNode];
[self setLast:newNode];
[self setCount:[self count]+1];

..whereas add:(Node*)newNode atIndex:(NSUInteger)index would be a little more complex:

if(index > self.count)
{
    // maybe throw an exception or something
} else if(index == self.count) // just do the normal add
{
    [self add:newNode];
    return;
} else if(index == 0) { // front-insert is also easier
    [newNode setNext:[self first]];
    [[self first] setPrevious:newNode];
    [self setFirst:newNode];
    [self setCount:[self count]+1];
    return;
}

// maybe do an extra check to see if it's quicker to search from the end
Node *currentLocation = [self first];
NSUInteger idx;
for(idx = 0; i < (index - 1); ++idx)
{
    currentLocation = [currentLocation next];
}

Node *previousNode = currentLocation; // store a reference to the previous node
currentLocation = [currentLocation next]; // now at the point we want to insert

[previousNode setNext:newNode];
[newNode setPrevious:previousNode];
[newNode setNext:currentLocation];
[currentLocation setPrevious:newNode];

[self setCount:[self count]+1];

Answer 2

No, no arrays. Using an array would, in general, spoil the performance guarantees of a linked list. There's no need to keep track of all the pointers; each node contains pointers to other nodes, and as long as your program keeps a pointer to just one node somewhere in the list, no nodes will get lost because it's possible to get to every other node from that one.

Answer 3

This link provides an implementation of a doubly linked list in Obj-C. In general, you don't use arrays because there's no need to track all the pointers.

//
//  LinkedList.h
//

// Structure representing a 
// doubly-linked list node.
typedef struct ListNode ListNode;
struct ListNode {
    int value;
    ListNode *next;
    ListNode *prev;
};


@interface LinkedList : NSObject {
@private 
    ListNode *head;
    ListNode *iterator;
    //bool reachedHead;
    //bool reachedTail;
}   

- (id)initWithHead: (int)value;
- (void)addToFront: (int)value;
- (int)getFirst;
- (int)getCurrent;
- (int)getNext;
- (int)getPrevious;

- (bool)atHead;
- (bool)atTail;

- (int)removeCurrent;

@end

The implementation:

//
//  LinkedList.m
//

#import "LinkedList.h"


@implementation LinkedList


/* Instantiates new linked list with a 
 * given first element. 
 */
- (id)initWithHead: (int)value 
{
    ListNode *n;
    self = [super init];
    if (self) {
        // creating head node with given value
        n = (ListNode *)malloc(sizeof(ListNode));
        n->value = value;
        n->next = NULL;
        n->prev = NULL;
        head = n;
        // initializing iterator to default
        [self getFirst];
    }
    return self;    
}


/* Adds a new element to the
 * front of the list */
- (void)addToFront: (int)value
{
    ListNode *n = (ListNode *)malloc(sizeof(ListNode));
    n->value = value;
    n->next = head;
    n->prev = NULL;
    // new element becomes the head node
    head->prev = n;
    head = n;
}


/* Sets internal iterator to
 * the head node and returns its
 * value */
- (int)getFirst {
    iterator = head;
    //reachedHead = TRUE;
    //reachedTail = FALSE;
    return (head->value);
}

/* Returns the value of the iterator node
 */
- (int)getCurrent {
    return (iterator->value);
}


/* Iterates to the next node in order and
 * returns its value */
/*
- (int)getNext
{
    // if we are finished iterating,
    // set the end-of-list flag
    if (iterator->next == NULL) {
        reachedTail = TRUE;
    } else {
        // if we're leaving the head
        // node, set the flag
        if (iterator->prev == NULL) {
            reachedHead = FALSE;
        }
        iterator = iterator->next;
    }
    return (iterator->value);
}
*/
- (int)getNext
{
     if (iterator->next != NULL) {
          iterator = iterator->next;
     }
     return (iterator->value);
}


/* Iterates to the previous node in 
 * order and returns its value */
/*
- (int)getPrevious
{
    if (iterator->prev == NULL) {
        reachedHead = TRUE;
    } else {
        if (iterator->next == NULL) {
            reachedTail = FALSE;
        }
        iterator = iterator->prev;
    }
    return (iterator->value);
}
*/
- (int)getPrevious
{
     if (iterator->prev != NULL) {
          iterator = iterator->prev;
     }
     return (iterator->value);
}


/* Indicates that iterator
 * is at the first (head) node */
- (bool)atHead 
{
    //return reachedHead;
     return (iterator->prev == NULL);
}


/* Indicates that iterator
 * is at the last (tail) node */
- (bool)atTail 
{
    //return reachedTail;
     return (iterator->next == NULL);
}


/* Removes the iterator node from
 * the list and advances iterator to the
 * next element. If there's no next element,
 * then it backs iterator up to the previous
 * element. Returns the old iterator value */
- (int)removeCurrent 
{
    int i = iterator->value;
    ListNode *l;
    // if we have only 1 item in the list...
    if ((iterator->next == NULL) && (iterator->prev == NULL)) {
        //... then we can safely delete it and set head to null
        free(iterator);
        iterator = NULL;
        head = NULL;
    } else {
        // sawing the gap between nodes
        l = iterator;
        if (iterator->next != NULL) {
            iterator->next->prev = iterator->prev;
        }
        if (iterator->prev != NULL) {
            iterator->prev->next = iterator->next;
        }
        // finally setting new iterator
        iterator = (iterator->next != NULL) ? iterator->next : iterator->prev;
        free(l);
    }
    // returning old value
    return i;
}

@end

Answer 4

If you would use an array you would get rid of all the performance advantages of using lists. Under the hood a linked list contains the value of the "Node" and pointers to the next and previous Nodes. Iterator incrementing/decrementing accesses the next/prev pointers of the nodes.