Question 5 of 7: Double Linked List

Question 5: Double Linked List (20 marks: ADT 10, functions 5 each)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

1. ADT definition — 10 marks

A doubly-linked node holds an integer, a pointer to the previous node, and a pointer to the next node; the list itself is described by head (first node, or NULL if empty) and tail (last node, or NULL if empty), which together give O(1) access to both ends.

typedef struct dnode {
    int val;
    struct dnode* prev;
    struct dnode* next;
} DNode;

typedef struct {
    DNode* head;   /* NULL if the list is empty */
    DNode* tail;   /* NULL if the list is empty */
} DList;
/* Interface: void  add_front(DList* L, int data);
              int   delete_end(DList* L);   -- returns the removed value
              int   is_empty(DList* L); */

2. add_front — 5 marks

A new node is created, linked ahead of the current head, and the list's head pointer is updated to it; if the list was empty, the new node becomes both head and tail.

void add_front(DList* L, int data) {
    DNode* n = (DNode*) malloc(sizeof(DNode));
    n->val = data;
    n->prev = NULL;
    n->next = L->head;
    if (L->head != NULL) L->head->prev = n;   /* old head now points back to n */
    L->head = n;
    if (L->tail == NULL) L->tail = n;          /* list was empty: n is also the tail */
}

3. delete_end — 5 marks

The current tail's value is saved, the list's tail pointer is moved back one node via the removed node's prev link, the new tail's next is cleared, and the old tail is freed; if that was the only node, both head and tail become NULL.

int delete_end(DList* L) {
    DNode* n = L->tail;                        /* precondition: list not empty */
    int val = n->val;
    L->tail = n->prev;
    if (L->tail != NULL) L->tail->next = NULL;
    else L->head = NULL;                        /* removed the only node */
    free(n);
    return val;
}

Maintaining both ends explicitly, rather than only head as a singly-linked list would, is what makes both operations cheap: add_front already only touches the head in a singly-linked list, but delete_end in a singly-linked list has no way to find the second-to-last node except by walking the whole list from the head, an $O(n)$ operation. Paying for the extra prev pointer per node and a dedicated tail field turns that walk into a single pointer read, which is the entire point of choosing a doubly- over a singly-linked structure whenever both ends of the list are accessed often.