Linked Lists

For this example, the text used was:
Data Structures and Algorithms:
Annotated Reference with Examples
First Edition
Copyright Granville Barnett, and Luca Del Tongo 2008.
Available at: dotnetslackers.com

One of the more basic data structures you come across as you learn to program are linked lists. Linked lists are basically just a collection of nodes that contain a value and a reference to the next node in the list. In order to gain a better understanding of them, implementation of a singly linked list and a doubly linked list in C++ proved to be helpful. In this example I only plan to illustrate the singly linked list. The text referenced above contains explanations of doubly linked lists and more functions than I plan to explain here.

First we'll create a header file to contain the LinkedList class.
"LinkedList.h" But, anything that makes sense to you should be fine.

Since linked lists are a collection of nodes, creating a Node struct, seemed like a good first step. Initializing them to NULL should help avoid strange values being pulled.

struct Node {
    int data = NULL;
    Node *next = NULL;
};

From here we can begin to create the outline of the class:

class LinkedList{
private:
    Node *head;
    Node *tail;
public:
    LinkedList() {  //constructor
        head = NULL;
        tail = NULL;
    };
    //functions will go here.
};

The head is a pointer to the first Node in the list while the tail is pointer to the last Node.  These two pointers have been set to NULL to avoid any complications random initialization might cause. I should also note that while "int" was used as the data type, this does not have to be the case. You can set the data type differently depending on the anticipated use.

There are a few different ways I've seen this structure implemented but, continuing with the example from Data Structures and Algorithms (DSA), there are 3 main functions to create. First is insertion. We always insert at the tail, unless it is the first node, then it is both the head and the tail. Because of this, we have the constant time complexity of $O(1)$.

void Add(int value) {
    Node *n = new Node;
    n->data = value;
    if (head == NULL) {
        //There are currently no nodes in this list
        this->head = n;
        this->tail = n;
    } else {
        //Add node to the end of the list
        this->tail->next = n;
        this->tail = n;
    }
};

Next is searching, which has a worst case time complexity of $O(n)$. The method is simple, we go through each node to check for the value we're searching for.

bool Contains(int value) {
    Node *n = this->head;
    while (n != NULL and n->data != value) {
        //Search through list for value. While loop breaks when value is found or tail node is reached
        n = n->next;
    }
    if (n == NULL) {
        //Since tail node points to nothing, we know we didn't find it
        return false;
    }
    return true;
};

Finally, removal from the list, which is also $O(n)$ because we check each node until we find the one we would like to remove. There are more cases to be aware of in this function. I have briefly explained them in the comments in the code.

bool Remove (int value) {
    //Check if the list is empty
    if (this->head == NULL) {
        return false;
    }
    Node *n = this->head;
        
    if (n->data == value) {
        if (this->head == tail) {
        //Check if node to remove is the only node
            this->head = NULL;
            this->tail = NULL;
        } else {
            //We must remove the head node
            head = head->next;
        }
        return true;
    }
        
    while (n->next != NULL and n->next->data != value) {
        //Search through list for value.
        n = n->next;
    }
    if (n->next != NULL) {
        if (n->next == tail) {
            //removing the tail node
            tail = n;
        } else {
            //removing some other internal node
            n->next = n->next->next;
        }
        return true;
    }
    return false;
}; 

This will be my stopping point for this data structure. It can be tested easily by including the header file in a cpp program and creating an instance of the LinkedList. For example:

#include "LinkedList.h"

using namespace std;

int main(int argc, const char * argv[])
{
    int a = 0;
    
    LinkedList exampleList;
    exampleList.Add(a);
    if (exampleList.Contains(a)) {
        cout << "true" << endl;
    }
    // else print false
    // other function tests
    // ...
    return 0;
};

DSA, continues with traversals which can be implemented fairly simply, as with the rest of these functions. One thing to note is that the reverse traversal has a time complexity of $O(n^2)$.This is because in order to find the previous node you must set a current node and search forwards from the head until you reach the current node's predecessor, thus we have an $O(n)$ complexity for the forward traversals multiplied by $n$, each node in the list, giving us $O(n^2)$.

If I think adding more functions/examples to this is necessary I will do so in the future.

Any questions, comments and/or suggestions are appreciated.