Double linked list in C [part 2]

In the first part of this blog entry we discussed the basics of the linked lists and showed a simple implementation in C. Let’s try and extend the previous implementation and make this into a Double linked list. A double linked list is very similar to a single linked list, the major difference is the way the “nodes” are linked together, each node in this instance knows also about the “previous” node, remember single linked lists only know about the “next” node.
Let’s start with the simple node definition, note the the extra “prev” property.
[code language=”c”]
/* Basic student definition */
typedef struct Student {
unsigned int age;
char name[20];
struct Student *next;
struct Student *prev;
} Student;
[/code]
We will still keep the same notion of head and tail.
[code language=”c”]
/* points to the first Student */
static Student *head = NULL;
/* points to the last Student */
static Student *tail = NULL;
[/code]
Now let’s modify the insert function which will allow us to use the “prev” property. Our new implementation is very similar to the single linked list implementation, the major difference is the way we track the “prev” item.
The new implementation should look like this:
[code language=”c”]
/* Create a new Student and attach to the last one. */
Student *insert(int age, char *name){
if(!head){
/*
* We do not have any Student created yet
*/
head = (Student *)malloc(sizeof(Student));
head->age = age;
strncpy(head->name, name, 20);
head->next = NULL;
head->prev = NULL;
/* at this stage the First and Last element are the same */
tail = head;
return head;
}else{
/*
* We already have a Student, link it
*/
tail->next = (Student *)malloc(sizeof(Student));
tail->next->age = age;
strncpy(tail->next->name, name, 20);
tail->next->next = NULL;
tail->next->prev = tail;
/* Last element is the newly created element */
tail = tail->next;
return tail;
}
}
[/code]
You would be probably asking, that is all nice and cool but what if we want to remove an element from the double linked list? Remember it is all about how the nodes are connected together, each node now knows about the “next” and also the “prev” node. We will also make sure that the head and tail are synced when removing an element from the list.
[code language=”c”]
void unlink(Student *student){
// any "prev" node for the given student need’s to be linked to "next"
if(head == student){
head = student->next;
}
if(tail == student){
tail = student->prev;
}
if(student->next != NULL){
student->next->prev = student->prev;
}
if(student->prev != NULL){
student->prev->next = student->next;
}
// free the memory
free(student);
}
[/code]
Now let’s implement a simple debug function which will simply print all the nodes and their data, including “next” and “prev” nodes.
[code language=”c”]
void dump(){
/* Start with the first element and loop till we reach a dead end. */
Student *s = head;
printf("rn———–rn");
while(s != NULL){
printf("Student: %s, Age:%d", s->name, s->age);
if(s->prev){
printf("tprev: %s, Age:%d", s->prev->name, s->prev->age);
}
if(s->next){
printf("tnext: %s, Age:%d", s->next->name, s->next->age);
}
printf("rn");
s = s->next;
}
printf("rn");
if(head){
printf("Head: %s, Age:%drn", head->name, head->age);
}
if(tail){
printf("Tail: %s, Age:%drn", tail->name, tail->age);
}
}
[/code]
The main program will look like this:
[code language=”c”]
int main(int argc, char **argv){
/* Insert three elements */
Student *john_doe = insert(24, "John Doe");
Student *jean_luc = insert(22, "Jean Luc");
Student *alex_rim = insert(31, "Alex Rim");
dump();
// now let’s have some fun and delete a student.
unlink(jean_luc);
dump();
return 0;
}
[/code]
…and have the following output…
[code language=”bash”]
———–
Student: John Doe, Age:24       next: Jean Luc, Age:22
Student: Jean Luc, Age:22       prev: John Doe, Age:24  next: Alex Rim, Age:31
Student: Alex Rim, Age:31       prev: Jean Luc, Age:22
Head: John Doe, Age:24
Tail: Alex Rim, Age:31
———–
Student: John Doe, Age:24       next: Alex Rim, Age:31
Student: Alex Rim, Age:31       prev: John Doe, Age:24
Head: John Doe, Age:24
Tail: Alex Rim, Age:31
[/code]
As always you can find the full source code here.