Doubly Linked Lists

Doubly linked lists are la type of linked lists that offer you better flexibility. They do this by providing you with the option to traverse the linked list in two ways, previous and next, unlike singly linked list that limit you to just one direction. Imagine you leaving your house to visit a friend, only to find out there's no way back home? Pretty disappointing, isn't it. It's like the path collapses as soon as you move past it and you have no choice but to keep moving forward or just remain stuck. Well that's basically the restriction singly linked lists place on us and no one really wants to be this restricted. Good thing we have doubly linked lists. With doubly linked lists, we can keep our path secure and are confident that we can always return home. One important characteristic of the double linked list tho is that the prev pointer of the first node points to NULL, just like the next pointer of the last node points to NULL Without further ado, let's dive right in. With doubly linked lists, there are three basic operations to perform. Inserting a new element to the list. Deleting an element from the list Traversing the list both ways. Inserting an element to the linked list can be done in three different ways; at the beginning; end and in a given position in between. I'll endeavor to cover the first two in this article. Also, it's worth mentioning that will be using C for every code here. They are as follows: Insertion at the beginning: This is as simple as it gets. The aim here is to insert our new node directly before the current first/head node and then update the head pointer to point to our new node. Here it is in code:

void begin_insert(**list_t head, int value)
{
    If (!head || !(*head))
        return;
    list_t *new = malloc(sizeof(list_t));
    if (!new)
        return NULL;
    new->value = value;
    new->next = *head;
    new->prev = NULL;
    *head->prev = new;
    *head = new;
}

The above code might look complex but really isn't. Given a pointer to the head pointer and the value to store in our new node as parameters, we first check if the pointer to the head pointer and the head pointer itself isn't NULL If (!head || !(*head)). If either is, we exit the function, else we proceed. The next thing to do after validating the parameters is to actually allocate space for our new node list_t *new = malloc(sizeof(list_t));, it won't exactly come from thin air, would it? We use malloc to achieve and check if our malloc succeeds, if it doesn't, we return NULL. We then store the given value; in this case an integer in the new node. Now our new node has been successfully created. All that remains is the actual insertion. Remember our goal is to insert at the beginning so the first thing we do is to make the next pointer of our new node point to the head/first nodenew->next = *head; and where do we need the prev pointer to point to? Yes NULL new->prev = NULL;, remember that the previous pointer of the first element is always NULL. This indicates that the former first element is to become the second and so our new->next points to it. But remember that this was formerly the first element and for that reason it's previous pointer pointed to NULL which is very wrong now that it's the second element. So we need to update it's previous pointer to point to the node that comes just before it in this case our new node.*head->prev = new Almost through but we can't exactly be without updating the head pointer to point to our new node right. This is exactly what registers our new node as the first/head node. We achieve this with the last line of code*head = new;.

Insertion at the end isn't exactly difficult either. The goal here is to make our new node take the place of the last element. So to do this, we need to iterate through the list till we get to the last node and then make it point to our new node. Even without writing a single line of code we already know the last node's next pointer will point to our new node but one other thing we know is that our new node's next pointer will point to NULL since las node always point to NULL. Here's the code:

void end_insert(**list_t head, int value)
{
    if (!head || !(*head))
        return;
    list_t *new = malloc(sizeof(list_t));
    if (!new)
        return NULL;
    new->value = value;
    new->next = NULL;
    list_t *last = head;
    while (last->next)
        last = last->next;
    last->next = new;
    new->prev = last;
}

As usual, the first step is to validate our parameters, allocate space for our new node, check if the allocation was successful and then store the appropriate data in the node. We then safely pointed the next pointer of the new node to NULL new->next = NULL; because we already know that the last node always points to NULL. Next, since we intend to insert our new node to the very end, we need to find this "end". To achieve this we iterate through the list from the beginning while checking if the next pointer is not NULL (Yep, using the logic that the next pointer of the last element is NULL) so as soon as our check hits NULL, we know we've reached the last element and can then add our new node after the last so it now becomes the new last element. To achieve this we simply point the last node's next pointer to our new node last->next = new; and our new node's previous pointer to the "former" last node. new->prev = last; And with that, our new node becomes the last node.

I really hope this was insightful. Please point out any errors in my code. It really was hard to squeeze out time for this.