Types of Linked Lists, Memory allocation, and cache locality

Linked lists are one of the most important data structures and these are the ones asked most in an interview. In this article, we are going to look into how types of linked lists.

Data Structure

A data structure is structuring and organizing data in a simple way so that data can be easily manipulated and managed. One example is accessing and inserting data in file systems and databases. The type of data structure to be used depends on various factors, such as the type of data, data access method e.g., serial access or random access, frequency of access, etc.

Linked List

A linked list is a type of data structure consisting of nodes. Each node consists of the 

Value – this is the actual data. This can be an integer, float, string or a custom object such as a structure or a class object

Pointer – each node points to the next node within a single linked list object. The final node points to NULL. 

A linked list is very similar to an array in the sense that it looks like a series of continuous data storage. However, there are some crucial differences between the two and each has its own advantages over the other.

Memory Allocation

Array

Arrays are allocated a series of memory. For eg., if an integer array has 10 elements and the starting address of an array is 100, then the final element will be stored at address 136. 

Linked List 

Linked lists elements may not be stored in contiguous memory. The pointer at each node helps to identify the location of the next node. 

Size

Array

Due to the contiguous memory allocation, the size of an array must be predetermined. This usually leads to memory wastage as there is an overcompensation to avoid shortage. 

Linked List 

There is no need to determine the size of a linked list. This not only avoids memory wastage but is very useful when a programmer is unaware of how large the linked list can grow. 

Insertion/Deletion

Array

Inserting or deleting an element in an array can be challenging if it is not the last element. Inserting or deleting an element in the middle of an array required moving the elements after that as well. In the worst-case scenario, if an element must be inserted at the beginning of the array then all elements must first be shifted one element to the right and only then can the new element be added. This may seem trivial for small arrays. However, if the array size is very large, this action itself will consume time and resources.

Linked List  

Inserting or deleting an element in the middle does not require modifying other elements. A new node needs to be created and the pointer of the previous element needs to be updated. This simplifies the insertion/deletion process and makes the linked list more suitable for scenarios that are frequently updated.

Random Access

Array

When the position of the element is known, a read operation can be performed in O(1) time. 

Linked List 

Random access is not possible in a linked list. Even if the position is known before-hand the linked list must be traversed until that element. This becomes an issue when the size of the linked list is huge and the element to be found is in the last. 

Cache Locality 

Array

Arrays have better cache locality since they have contiguous memory locations. Consider an array that is accessed for reading. Once the first element is accessed, the next elements of the array can be cached for future usages, thereby reducing the read time. This saves time and resources

Linked List 

Since the elements are randomly stored, it is a challenge to cache the linked list.

Table 1: Array vs Linked list

Table 1, provides a summary of the differences between array and linked list 

Types Of Linked List 

Singly Linked List 

The singly-linked list is a simple linked list, where each node points to the next node and the final node points to NULL.

Figure 2: Single Linked List

Below is the code to create a singly linked list and perform insert, delete update and print operations. 

#include<iostream>  
using namespace std;

class node {
    public:
    int value;
    node *next;

    node(int val) {
        value = val;
        next = 0;
    }
};

class singlyll {
    node *head;
    node *tail;

    public:
    singlyll() {
        head = 0;
        tail = 0;
    }

    void insert_at_head(int val) {
        if (head == 0) {
            head = tail = new node(val);
        } else {
            node *tmp = new node(val);
            tmp->next = head;
            head = tmp;
        }
    }
 
    void insert_at_tail(int val) {
        if (tail == 0) {
            head = tail = new node(val);
        } else {
            tail->next = new node(val);
            tail = tail->next;
        }
    }

    void delete_at_head() {
        if (head != 0) {
            node *tmp = head;
            if (head == tail) {
                head = tail = 0;
            } else {
                head = head->next;
            }
            delete tmp;
        }
    }
 
    void delete_at_tail() {
        node *tmp;
        for (tmp = head; tmp->next != tail; tmp = tmp->next);
        if (tmp != 0) {
            tail = tmp;
            tail->next = 0;
            tmp = tmp->next;
            delete tmp;
        }
    }

    void print() {
        for (node *tmp = head; tmp != 0; tmp = tmp->next) {
            cout<<tmp->value<<" ";
        }
    } 
};


int main() {
    singlyll sll;

    sll.insert_at_head(10);
    sll.insert_at_head(20);
    sll.insert_at_tail(30);
    sll.delete_at_head();
    sll.delete_at_tail();
    sll.print();

}

Doubly Linked List 

A doubly linked list is the linked list in which each node points to both the next element and the previous element.

Figure 3: Doubly Linked List

Note that the first element has its previous pointer to NULL and the last element has its next pointer to NULL. 

Circular Linked List 

A circular linked list can be singly or doubly linked list, depending on whether it has a previous pointer or not. But the last element points back to the first element, thereby, creating a circle.

Figure 4: Circular Linked List

If you like the article please share and subscribe. This is all for now in types of linked lists. You can also look into this.