Some linked list routines need to modify the head node (first node) of the list, if for example the head node is a new node, or the head node needs to be removed. This means that these routines need to modify the pointer to the head node, to point to a different node. In this cases, these routines can either return the new head node pointer, so that the function calling can update it, or get a pointer to the head node pointer, so that they can modify the head node pointer without any problems.
A different approach for this is to use a dummy head, which next pointer points to the head node. In this way the list functions can just pass a pointer to the dummy head, instead of a pointer to the head node pointer.
The following program illustrates both approaches:
#include <stdio.h>
#include <stdlib.h>
struct node {
struct node *next;
int value;
};
typedef struct node node_t;
void insert_ordered_dummy(node_t * dummy, int value) {
node_t * newnode = malloc(sizeof(node_t));
newnode->value = value;
newnode->next = NULL;
if (dummy->next == NULL) {
dummy->next = newnode;
return;
}
node_t * current = dummy->next;
node_t * prev = dummy;
while (current != NULL && current->value < value) {
prev = current;
current = current->next;
}
prev->next = newnode;
newnode->next = current;
}
void insert_ordered_nodummy(node_t ** list, int value) {
node_t * newnode = malloc(sizeof(node_t));
newnode->next = NULL;
newnode->value = value;
// *list->value is equivalent to *(list->value)
if (*list == NULL || (*list)->value > value) {
newnode->next = *list;
*list = newnode;
return;
}
node_t * prev = *list;
node_t * current = (*list)->next;
while (current != NULL && current->value < value) {
prev = current;
current = current->next;
}
prev->next = newnode;
newnode->next = current;
}
void insertend_nodummy(node_t **head, int value) {
node_t *newnode = malloc(sizeof(node_t));
newnode-&gt;value = value;
newnode-&gt;next = NULL;
if (*head == NULL) {
*head = newnode; // if list empty, newnode is head
return;
}
node_t *ptr = *head;
while (ptr-&gt;next != NULL) { // move ptr to last node
ptr = ptr-&gt;next;
}
ptr-&gt;next = newnode; // insert after last node
}
void insertbeginning_withdummy(node_t *dummyhead, int value) {
node_t * newnode = malloc(sizeof(node_t));
newnode-&gt;value = value;
newnode-&gt;next = dummyhead-&gt;next;
dummyhead-&gt;next = newnode; // now dummy head points to new node
}
void insertend_withdummy(node_t *dummyhead, int value) {
node_t *newnode = malloc(sizeof(node_t));
newnode-&gt;value = value;
newnode-&gt;next = NULL;
if (dummyhead-&gt;next == NULL) {
dummyhead-&gt;next = newnode;
return;
}
node_t *ptr = head;
while (ptr-&gt;next != NULL) { // move ptr to last node
ptr = ptr-&gt;next;
}
ptr-&gt;next = newnode; // insert after last node
}
void printlist(node_t *head) {
node_t *ptr = head;
while (ptr != NULL) {
printf(&quot;%d, &quot;, ptr-&gt;value);
ptr = ptr-&gt;next;
}
printf(&quot;\n&quot;);
}
int main() {
/* without dummy node: the first node is the head. main keeps a pointer
to the first node (head). If a function needs to modify the head of
the list (say a new node replaces the head node), then the head pointer
needs to be modified, which means that a pointer to the head pointer needs
to be passed to the function. Or otherwise the function could return the
new head pointer */
node_t * headptr = NULL; // dont forget NULL!!
int numbs[] = {1,2,3,4,5};
int i;
for (i = 0; i &lt; 5; i++) {
insertbeginning_nodummy(&amp;headptr, numbs[i]);
printlist(headptr);
}
for (i = 0; i &lt; 5; i++) {
insertend_nodummy(&amp;headptr, numbs[i]);
printlist(headptr);
}
/* with dummy node: in this case you can just pass pointer to
dummy head to any function, and the function will be able to
modify the next pointer in the dummy head. So no need for
double pointers */
node_t dummy_head;
dummy_head.next = NULL;
dummy_head.value = -1;
for (i = 0; i &lt; 5; i++) {
insertbeginning_withdummy(&amp;dummy_head, numbs[i]); // pass ptr to dummy head
printlist(dummy_head.next);
}
for (i = 0; i &lt; 5; i++) {
insertend_withdummy(&amp;dummy_head, numbs[i]);
printlist(dummy_head.next);
}
return 0;
}
&gt; gcc linkedlist.c -g
&gt; ./a.out
1,
2, 1,
3, 2, 1,
4, 3, 2, 1,
5, 4, 3, 2, 1,
5, 4, 3, 2, 1, 1,
5, 4, 3, 2, 1, 1, 2,
5, 4, 3, 2, 1, 1, 2, 3,
5, 4, 3, 2, 1, 1, 2, 3, 4,
5, 4, 3, 2, 1, 1, 2, 3, 4, 5,
1,
2, 1,
3, 2, 1,
4, 3, 2, 1,
5, 4, 3, 2, 1,
5, 4, 3, 2, 1, 1,
5, 4, 3, 2, 1, 1, 2,
5, 4, 3, 2, 1, 1, 2, 3,
5, 4, 3, 2, 1, 1, 2, 3, 4,
5, 4, 3, 2, 1, 1, 2, 3, 4, 5,
Learning C by example 