<p>A linked list is a dynamic linear structure that typically holds one or more nodes where at least one node has <strong>a value and a pointer</strong> to the address of the next existing node. Implementing a doubly linked list can be slightly more complex than a singly list because the former is <strong>bi-directional</strong> while the latter is <strong>uni-directional</strong>. This means that, in a doubly linked list, each node has two pointers; one to the address of the previous existing node and the other to the next node. There are several operations that can generally be done on a linked list but in this post, the focus will be on inserting a new node at the end of a list, deleting a node from the end of a list and traversing a list to find a node.</p>
<p>As someone who primarily writes JavaScript, I found implenting a linked list in JavaScript easier since it supports OOP -- quite useful for creating and keeping track of state during implementation.</p>
<p>Since C is a procedural oriented language and does not support OOP, replicating concepts like encapsulation and inheritance is not quite straightforward. [While C does have object-like structures, the behaviours of these structures are completely different from your standard object].</p>
<p>Let's look at an implementation of a doubly linked list in <strong>JavaScript</strong> with classes</p>
<pre><code>    // initialize a node class
    class Node {
        constructor(value) {
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    // use a class to encapsulate and keep track of various states
    class DoublyLinkedList {
        constructor() {
            this.head = null; // starting node
            this.tail = null; // end node
            this.length = 0; // initial length state
        }

        // removal from the end of list
        pop() {
            if (!this.head) return undefined;

            const nodeToBeDeleted = this.tail;

            if (this.length === 1) {
                this.head = null;
            } else {
                const prev = nodeToBeDeleted.prev;
                prev.next = null;
                this.tail = prev;
            }
            this.length--;
            return nodeToBeDeleted;
        }

        // insertion at the end
        push(val) {
            const newNode = new Node(val); // create a new node

            if (!this.head) {
                this.head = newNode;
                this.head.prev = null;
                this.head.next = null;
                this.tail = this.head;
            } else {
                const currentTail = this.tail;
                this.tail.next = newNode;
                newNode.prev = currentTail;
                newNode.next = null;
                this.tail = newNode;
            }
            this.length++;
            return this;
        }

        // traversing the list to find a specific node
        find(val) {
            if (!this.head) return undefined;

            let temp = this.head;

            while (temp.next !== null) {
                temp = temp.next;

                if (temp === val) {
                    return temp;
                }
            }

            return undefined;
        }
    }

    const newList = new DoublyLinkedList();

    newList.push(11);
    newList.push(12);
    newList.push(13);
    newList.push(14);
    newList.pop();
    newList.find(12);

    console.log({ newList });
</code></pre>
<p>Let's try to implement a doubly linked list of integers and some of its operations in C</p>
<h4>Inserting a node at the end of the list</h4>
<p>To insert a node at the end of a list in C, first, we allocate memory for a new node, then take the pointer of the last node which points to null and point it to the new node being inserted. An example code below:</p>
<pre><code>    int insertAtEnd(struct Node** head, int data) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

        newNode->value = data;
        newNode->next = NULL;

        if (*head == NULL) {
            newNode->prev = NULL;
            *head = newNode;
            return;
        } 

        struct Node* temp = *head; 

        while (temp->next != NULL) {
            temp = temp->next;
            temp->next = newNode;
            newNode->prev = temp;

            return;
        }
    }
</code></pre>
<p>A rough visual example would look like this:</p>
<pre><code>    &#x3C;!-- Before insertion -->
    &#x3C;-11 ->&#x3C;- 12 ->&#x3C;- 13 ->&#x3C;- 14 ->&#x3C;- null (tail node)

    &#x3C;!-- After insertion: node 15 -->
     &#x3C;-11 ->&#x3C;- 12 ->&#x3C;- 13 ->&#x3C;- 14 ->&#x3C;- 15 ->&#x3C;- null (tail node)
</code></pre>
<h4>Deleting a node at the end of a list</h4>
<p>Deleting a node on a doubly linked list can be done at any point on the list but in the implementation below, we're going to delete a node from the end of the list (pop)</p>
<pre><code>    int deleteFromEnd(struct Node** head, struct Node* nodeToDelete) {
        if (*head == NULL) { // list is empty
            return;
        }
  
        if (*head == nodeToDelete) { // target node is the head node
            *head = nodeToDelete->next;
            return;
        }

        if (nodeToDelete->next != NULL) {
            nodeToDelete->next->prev = nodeToDelete->prev;
        }

        if (nodeToDelete->prev != NULL) {
            nodeToDelete->prev->next = nodeToDelete->next;
        }

        // then free the memory for the node to be deleted
        free(nodeToDelete);
    }
</code></pre>
<h4>Traversing a doubly list to find a target node</h4>
<p>Since a doubly linked list contains one or more nodes linked to each other in two opposite direction, we can traverse a doubly linked list by taking the head node, assigning it to a temporary variable <strong>"temp"</strong>, then, in a loop, keep reassigning the next node as the new value of the temp variable until all nodes on the list have been visited. We know when all the nodes have been visited when the value of <strong>temp->next</strong> becomes NULL and then the loop ends.</p>
<p>Let's look at an implementation in C that traverses a list to find a target node</p>
<pre><code>    int traverseAndFind(struct Node** head, struct Node* nodeToFind) {
        if (*head == NULL) { // only one node on the list
            return;
        }

        if (*head == nodeToFind) { // target node is placed at the beginning of the list
            return nodeToFind;
        }

        struct Node* temp = *head; 

        while (temp->next != NULL) {
            temp  = temp->next;
            printf("%d --->",temp->value);

            if (temp == nodeToFind) {
                return temp.data; // return value of target node
            }

            return 0;
        }
    }
</code></pre>
<h4>Testing out the code</h4>
<p>To test out the code, we're going to initialize a node variable with <strong>struct</strong>, which is another way for us to group related information.</p>
<pre><code>    struct Node {
        int value;
        struct Node *prev; // a pointer to the previous node/address
        struct Node *next; // a pointer to the next node
    }

    void printList(struct Node* node) {
        struct Node* last;

        while (node != NULL) {
            printf("%d->", node->value);

            last = node;
            node = node->next;
        }

        if (node == NULL) {
            printf("NULL\n");
        }
    }

    int main() {
        // initialize an empty node
        struct Node* head = NULL;
        
        insertAtEnd(&#x26;head, 11);
        insertAtEnd(&#x26;head, 12);
        insertAtEnd(&#x26;head, 13);
        insertAtEnd(&#x26;head, 14);

        traverseAndFind(&#x26;head, 12);
        deleteFromEnd(&#x26;head, 12);

        printList(head);
    }
</code></pre>
<p>That's all, folks!</p>
<h3>Notes</h3>
<p>Here are some resources I found helpful on linked lists, C structs or C data types:</p>
<ol>
<li><a href="https://www.w3schools.com/c/c_structs.php">W3Schools: C Structs</a>,</li>
<li><a href="https://www.reddit.com/r/C_Programming/comments/3rxl9o/question_why_are_structs_not_objects/">Reddit: Why are structs not objects?</a>,</li>
<li><a href="https://softwareengineering.stackexchange.com/questions/113533/why-is-c-not-considered-an-object-oriented-language">Why is C not considered an 'object-oriented' language?</a></li>
</ol>


Implementing a Doubly Linked List in C