Dummy nodes in Linked List implementation

Question

I am trying to implement a Singly linked list.

Requirements are: 1. Insert in order of data 2. Remove from head

Do I need to have a dummy node in my implementation? Also should the dummy node be placed at beginning of list or end of list?

I googled for answer and found that dummy nodes are helpful during removal of last node in the list. But, I couldn't understand how. Can someone explain?

Answer 1

Linked lists look like this:

struct list_node {
    struct list_node *next;
    void *data;
};

struct list_node *head;

You never need dummy nodes in linked lists in C.

Dummy nodes are for allowing the "remove current" operation to be implemented in singly linked lists in languages that do not provide pointers to pointers. That's all.

When you have a pointer to a node, you can delete the node by moving the next node on top of it and freeing the next node. The dummy node ensures that there is always a next node to implement this operation.

However in C you are better served by keeping a pointer to the next node. At the start of iteration this is a pointer to head; after the start this is a pointer list_node::next where list_node is the previously looked-at node.

Answer 2

Dummy nodes are not needed to implement singly linked lists. They are used as an alternative to defining a list structure different from the list element structure.

Given your requirements, you should define a list structure that holds a pointer to the head of the list and a pointer to the tail of the list. This will make both operations, inserting at the end and removing from the head operate n constant time.

Care must be taken to maintain these pointers correctly when the list becomes empty.

Here is a simple example:

struct list_elem_s {
    struct list_elem_s *next;
    int data;
    //... other payload fields
};

struct list_s {
    struct list_elem_s *head;
    struct list_elem_s *tail;
};

// initialize a list as empty
void list_initialize(struct list_s *list) {
    list->head = list->tail = NULL;
}

// free all elements from a list
void list_delete(struct list_s *list,
                 void (*free_node)(struct list_elem_s *node)) {
    struct list_elem_s *node;
    while ((node = list->head) != NULL) {
        list->head = node->next;
        node->next = NULL;
        if (free_node)
            free_node(node);
    }
    list->tail = NULL;
}

// add a node at the tail
void list_push(struct list_s *list, struct list_elem *node) {
    node->next = NULL;
    if (list->tail) {
        list->tail->next = node;
    } else {
        list->head = node;
    }
    list->tail = node;
}

// remove a node at the head
struct list_elem *list_pop_head(struct list_s *list) {
    struct list_elem_s *node;
    if ((node = list->head) != NULL) {
        if ((list->head = node->next) == NULL)
            list->tail = NULL;
    }
    return node;
}