Linked Lists

Linked lists are data structures that store data in such a way that each element has a reference to another element in the list.

A linked list showing head and tail pointers.

A linked list showing head and tail pointers.

Operations

Any linked list invariant must support some basic operations:

  • Insertion
  • Search (find)
  • Deletion

Invariants

There are numerous linked lists invariants. We will take a look at two of the most used ones: Singly Linked List and Doubly Linked List.

Singly Linked List

This is the most basic invariant of linked lists.

Keep track of the first node (head) and last node (tail).
Each node points to the next nod in the list.

Before diving into details, let’s define class Node that will hold elements of our list.

We want our node class to be flexible enough to store data of any type, so we use class template.

template 
class Node
{
public:
    Node(const T &value) :  data(value), next(NULL){}
    ~Node(void){}

    T data;
    Node *next;
};

This class has two members: data to store our data, and next which is a pointer to the next node in the list, if any. The constructor initializes data with the value parameter and sets next to NULL.

Let’s think about the linked list class we’re about to write. We need to keep track of our head node; so we’ll do so using a pointer. We’ll create a member pointer and call it head. Also, let’s create another pointer while we’re at it to keep track of the tail. Now, we need methods to add nodes to our list. Let’s create a method to add nodes at the head. Let’s call it addToHead(). Also, we’d want to add another method to delete or remove items from head and it shall be called… deleteFromHead(). Since we have a tail, let’s create addToTail() and deleteFromTail().

Do Not Lose The List

As you might have thought, we’ll be moving next and head or tail to add or delete new nodes to the list. The key guideline here is: Not to lose the list! We have to make sure that our pointers are in check and valid.

Now, let’s take a look at the class.

template 
class List
{
public:
    List(void){ head = tail = NULL;}
    ~List(void){}

    bool isEmpty() { return head == NULL; }

    void addToHead(T value);
    T deleteFromHead();

    void addToTail(T value);
    T deleteFromTail();

    bool find(T value);
    bool deleteNode(T value);

private:
    Node *head, *tail;
};
Insertion

Let’s implement void addToHead():

template 
void List::addToHead(T value)
{
    Node *node = new Node(value);

    if (head) 
        node->next = head;

    head = node;

    if (!tail)
        tail = head;
}

Let’s walk through the code above. First, we created a Node object using the value passed into addToHead() method. Then we check to see if head is NULL. So, if exists a head then make our new node->next point to the current head. Then we make our head point to the new node. So we added the new node in front of the old head.
Finally, if the tail pointer is null, we make point to the new head. That means we only have one item in the list.

There is no dependency in this method on the size of the list. So, the time complexity for this method is O(1) or it runs in constant time.

Now let’s take a look at deleteFromHead().

template 
T List::deleteFromHead()
{
    T value = head->data;
    Node *temp = head;

    if (head == tail) // One node in list
        head = tail = NULL;
    else
        head = head->next;

    delete temp;

    return value;
}

In the code above, we extract the information from the head node in value. Then, we create a temporary pointer to point to point to the head node. If we have only one node in the list, we nullify head and tail pointers. If we have more than one node in the list, we make the head pointer points to the next node. Then we delete the temporary pointer to free up memory, otherwise we’ll have a memory leak. Finally, we return value to caller.

Like addToHead(), there is no dependency in this method on the size of the list. So, it runs in constant time O(1);

Similar to addToHead(), we implement addToTail().

template 
void List::addToTail(T value)
{
    Node *node = new Node(value);

    if (tail) 
        tail->next = node;

    tail = node;

    if (!head)
        head = tail;
}

Here, the tail pointer is key, obviously. First we create a new Node to store our value. Then if tail is not null, we make tail->next point to the new node. Now we can have tail point to node, which is now the last node in the list. If head is null then our list has only one node, so make head point to tail.

Again, since there is no dependency on the size of the list, this method runs in constant time O(n).

deleteFromTail() will be a little different. Let’s take a look.

template 
T List::deleteFromTail()
{
    T value = tail->data;

    if (head == tail)
    {
        delete head;
        head = tail = NULL;
    }
    else
    {
        Node *temp;
        // loop to the node before last
        for (temp = head; temp->next != tail; temp = temp->next); 
        delete tail;
        tail = temp; // node previous to tail is now tail
        tail->next = NULL;
    }

    return value;
}

Firstly, we make record of the data we want to return in value. Here, we have two main branches:

    1. There is only one node in the list, then delete that node and nullify head and tail

pointers.

  1. There are several nodes in the list. Then we’ll create a pointer temp to point at head then loop over all the nodes in the list until we reach the node before last, in other words, until we reach the node that will become the new tail. At this point it is safe to free memory occupied by the last node. Since temp is now pointing to the new tail node, we make tail point to this node. Finally, we make sure to nullify tail->next.

In the above method, since we loop from head to tail, there is a dependency on the size of the list. Our time complexity here is linear or O(N).

Find

Now let’s implement find().

template 
Node  List::find(T value)
{
    for (Node *i = head; i != NULL; i = i->next)
        if (i->data == value) return true;

    return false;
}

As you see above, there is no fast way to find items in a linked list. We have to loop over items in list until we find what we’re looking for. The find() method returns true if the item is found and false otherwise.

Time complexity of find() is proportional to the size of the list n, or it is O(n).

Deletion By Value

In order to delete a node by its value (could be somewhere between head and tail), we need to know the previous node so we keep track of the two parts of the list after deleting our node. But, we have a couple of special cases:

  1. If head is to be deleted.
  2. If head is to be deleted and it is the only node in the list.

So, here is the code:

template 
bool List::deleteNode(T value)
{

    if (head->data == value)
    {
        if (head == tail)
        {
            delete head;
            return true;
        }
        else
        {
            Node *temp = head;
            head = head->next;
            delete temp;
            return true;
        }
    }
    else
    {
        if (head == tail) return false;

        for (
            Node *prev = head, Node *i = head->next;
            i->next != NULL;
            prev = prev->next, i = i->next;
            )
            {
                if (i->data == value)
                {
                    prev->next = i->next;
                    if (i == tail)
                        tail = prev;
                    delete i;
                    return true;
                }
            }
    }

    return false;
}

As you can tell, the time complexity is linear for deleteNode() or we can say it is O(n).

Conclusion

Operations on a linked lists are best done at head and tail are done in constant time. Other operations performed on other nodes in the middle of the list depend on the size of the list n. Other algorithms are developed to improve search operations on the list.

Notes

Linked Lists Vs. Arrays
  • Linked lists dynamically allocate memory as needed for new items (nodes), and free memory as nodes are removed from the list.
  • Arrays are statically allocated on the stack if the array is declared locally or on the Data Segment if declared globally. Arrays cannot be resized once declared.
  • Linked lists items are not randomly accessed. An iterative process is required to access items in a list without having a direct reference to each item.
  • Array items can be access randomly giving that we know the index of the item we want (i.e. arr[4] = 2;).

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>