What are linked lists in data structures?

Linked lists are a sequence of elements where each element links to the next element and the next element links to the next element. It can contain any kinds of data like strings, characters, numbers, etc. It can be unsorted or sorted. It can also contain duplicate elements if required.

How is a linked list different from an array?

In an array, the elements are indexed. So, to access any element at position N, we can use the index N to refer to it. But in a linked list we need to start from the head and work the way through to get to the Nth element. This takes time (time complexity of O(n)) and hence the process is slower in comparison to accessing elements in arrays.

Note that there is also a doubly linked list structure (the other one is also called singly linked list). In this structure, unlike simple linked lists, each element are linked both ways (to the the previous and the next element).

What are the advantages of linked lists over arrays?

In most of the compiled programming languages, we need to allocated initial size to an array (malloc in C). This size is used to allocated data to the array. But further down the line if we need more memory for that array, then we need to reallocate the memory (realloc in C). This process can be slow. Also, we need to always use more memory (with some initial guess of the required size of the array) than the amount of data available to store. In addition to that, if we want to insert data at some point in the middle of the array, then we need to either delete the element there or copy and move the other elements. This can be an issue for a large array size.

In contrast, the linked lists allows us to quickly insert/delete element at any position in the data structure. Unlike the arrays where the elements need to be together in one block, in the linked lists structures the elements can be located anywhere in the memory.

Structure of a linked list

For adding an element in a linked list means that we need to allocate the memory for the element we add to the list and we need to give a pointer that will point to the next element in the list.

Create a linked list in C

#include <stdlib.h>
#include <stdio.h>

struct node {
    int value;
    struct node* next;
};

typedef struct node node_t;

void printlinkedlist(node_t *head) {
    node_t *temp = head; // temporary pointer
    while (temp != NULL) {
        printf("%d -> ", temp -> value);
        temp = temp -> next;
    }
    printf("\n");
}

int main() {
    node_t a, b, c; // define three nodes as local variables
    node_t *head;

    // set values for each node
    a.value = 66;
    b.value = 886;
    c.value = 89;

    //link the nodes using pointers
    // c - a - b -
    head = &c; // head is pointing at the address of c
    c.next = &a;
    a.next = &b;
    b.next = NULL; // to define the last element


    // Add another element in the middle
    // c - a - d - b -
    node_t d;
    d.value = 44;
    d.next = &b;
    a.next = &d;
    printlinkedlist(head);

    return 0;
}

>> gcc linkedlists1.c -o linkedlists1
>> ./linkedlists1
89 -> 66 -> 44 -> 886 ->

We can also move the head of the linked list to the next element by simply:

#include <stdlib.h>
#include <stdio.h>

struct node {
    int value;
    struct node* next;
};

typedef struct node node_t;

void printlinkedlist(node_t *head) {
    node_t *temp = head; // temporary pointer
    while (temp != NULL) {
        printf("%d -> ", temp -> value);
        temp = temp -> next;
    }
    printf("\n");
}

int main() {
    node_t a, b, c; // define three nodes as local variables
    node_t *head;

    // set values for each node
    a.value = 66;
    b.value = 886;
    c.value = 89;

    //link the nodes using pointers
    // c - a - b -
    head = &c; // head is pointing at the address of c
    c.next = &a;
    a.next = &b;
    b.next = NULL; // to define the last element


    // Add another element in the middle
    // c - a - d - b -
    node_t d;
    d.value = 44;
    d.next = &b;
    a.next = &d;
    head = head->next;
    
    printlinkedlist(head);


    return 0;
}

>> gcc linkedlists1.c -o linkedlists1
>> ./linkedlists1
66 -> 44 -> 886 -> 

Notice how head = head->next drops the first node (89) simply by moving the head pointer forward — no data is copied, which is the whole appeal of pointer-based structures.

This code can be well organized to do easy manipulation of the linked lists. I suggest interested readers to checkout the video by Jacob Sorber Understanding and implementing a Linked List in C and Java.

Create a linked list in Python

Tutorialspoint has a detailed tutorial on how to create a linked list in Python. They discused how to create a linked list, insert at the beginning, end and between two data nodes of the list, and how to remove an element from the list.

When not to use linked lists?

There are several benefits of using linked lists over arrays because of its flexibility such that it allows adding different kinds of data, and the memory allocation scales linearly with the amount of data, etc. However, there are times when using linked list may not be such a good choice. There are some downsides of using linked lists compared to arrays. Some of them are listed below:

1. Linked lists uses more memory compared to arrays storing the same amount of data. This is because each element in the linked list also comes with a pointer that requires some memory as well (storing pointers may require 4 bytes on a 32 bit machines and 8 bytes on a 64 bit machines). Doubly linked lists will require even more memory.
2. Linked lists causes bad memory locality. For the case of arrays, the memory required for all the elements are laid out sequentially but for the linked list, the memory can be anywhere on the heap with links that are connecting them. To access such data will be slower.

Recap

Without scrolling up — what defines a linked list, and when should you reach for one?

• A chain of nodes, each holding a value + a next pointer; head points to the first, the last points to NULL.
• Strength: insert/delete anywhere is cheap — just re-point a pointer (e.g. head = head->next).
• Weakness: O(n) access (walk from the head), extra memory for pointers, and poor cache locality vs a contiguous array.
• Choose a linked list for frequent middle insert/delete; choose an array for fast indexed access.