Linked-List

A linked-list is a type of collection where elements are stored in random memory.

How is it different from the other collections like arrays? To understand, let us look into what the stack and heap are.

The Stack

A stack is a data structure where each element is stacked on top of the previous element. The last element pushed is the first element accessed. Unlike arrays, you cannot access the rest of the stack.

What does this stack have to do with our collections?

All statically allocated variables are stored in the program's stack. If you have encountered errors when programming, you would have come across what is called the call stack. This stack keeps track of all function calls. Whenever a function is called, all parameters and local variables are pushed onto the stack. Once the function is complete, these values are popped from the stack.

What if the size of data is dynamic? What if you have an array of 100 integers and the user wants 101? The stack can only accomodate data whose size is known at compile-time. If the size itself is dynamic, the data is allocated into the heap instead.

The Heap

The heap is a tree-like data structure. In this case, the heap keeps track of dynamically allocated memory.

In other words, when you want to dynamically allocate memory for something at run time, you request a certain amount of space in the memory. The allocator looks for a spot in the heap that is big enough to hold your value, stores your data there, and returns a pointer. The pointer is just the address of that particular location in memory.

So now that we know how the heap works, let's move on to why all of this matters.

In programming languages like C, C++, and Rust which deal with system concepts a lot, the stack and heap matter a lot. In order to create a dynamic collection of elements, we need to be familiar with the stack and the heap.

Linked-List structure

A linked-list is made up of a number of nodes, each node typically having two parts:

• The data part that stores the actual data.
• The link part that stores the address of the previous or next node in the linked-list.

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

In this example, our data is a normal C integer. However, your linked-list can store whatever type of data you want, depending on your implementation.

The next field stores a pointer that points to another struct Node. Referencing Node within Node is a concept called self-referencing.

Now that we have our struct ready, let's initialize the head of the linked-list, a pointer that points to the first element in the linked-list.

struct Node *HEAD;

Cool. Now let's move on to the next part. That is, adding an item to our linked-list. Let us first try inserting an element in the linked-list.

Insertion

Insert At Beginning

void insert_at_beginning(int item) {}

We have named our function insert_at_beginning(). Pretty descriptive. We will pass the value to insert via the item parameter.

Now comes the cool part. To allocate data in the heap, we need a function called malloc() that can be found in <stdlib.h>.

// Insert this at the top of your file#include <stdlib.h>

Moving on to seeing our malloc() function in action,

void insert_at_beginning(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));}

Translating the above code to something humane,

• Give me the pointer of new_item (struct Node *new_item).
• Allocate enough memory to house data as big as a Node (malloc(sizeof(struct Node))).
• Cast it to the struct Node * type ((struct Node *)).

It's okay now. We are moving to more casual stuff.

void insert_at_beginning(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item;    new_item->next = NULL;}

If you are new to the pointer concept, the -> symbol may be new to you.

The -> operator does the same thing as the . operator -- Accessing the children of an element. However, unlike the . operator, we use the -> to work with pointers. As you can see, our new_item is a pointer to an actual node.

NULL is a special, void-ish value provided by <stdlib.h>. We are setting new_item->next to NULL since there is no next element in the chain.

We have two cases when it comes to insertion at the beginning:

1. The list is empty. In this case, we just place the element there and... the end.

if (HEAD == NULL) {    HEAD = new_item;}

2. There is at least one element in the list. In this case, we are assigning our existing first item to a temporary variable and inserting our new item in that position instead.

if (HEAD == NULL) {    HEAD = new_item;} else {    struct Element *temp = HEAD;    HEAD = new_item;    HEAD->next = temp;}

It goes like

HEAD = - -> A -> B -> C -> D ->

When we insert E in this list,

HEAD = - ->temp = - -> A -> B -> C -> D ->HEAD = - -> E ->temp = - -> A -> B -> C -> D ->HEAD = - -> E -> A -> B -> C -> D ->temp = -

Our complete function looks like this:

void insert_at_beginning(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Element *temp = HEAD;        HEAD = new_item;        HEAD->next = temp;    }}

And that's it, for our insert_at_beginning().

Insert At End

Insertion at the end (or tail) of the linked-list has one extra step. It looks the same as our insert_at_beginning() for the first part:

void insert_at_end(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    }}

But when our linked-list already has an element, we cannot follow the same process as the insert_at_beginning(). Instead, we are just going to place our new node after the last node in the list.

    struct Node *temp = HEAD;    while (temp->next != NULL) {        temp = temp->next;    }    temp->next = new_item;

With this, we are iterating through the list till we reach the last node (that is, a node without a next node assuming nothing went wrong till now).

Our complete function looks like this:

void insert_at_end(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        while (temp->next != NULL) {            temp = temp->next;        }        temp->next = new_item;    }}

Insert At Custom Position

Inserting a node at a custom position is not really hard. In fact, it would be a faster operation than inserting at the tail. For such an insertion, we need two parameters.

void insert_at_custom(int item, int position) {}

The rest of the function is, of course the same as our insert_at_end() for most part.

Look at this part from our insert_at_end().

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

We are just going to tweak it so that it stops iterating when it reaches the required position.

int i = 0; while (i < position && temp->next != NULL) {    temp = temp->next;    i += 1;}

That's it. But one tiny issue. Since our insertion probably happens at the middle of the linked-list, inserting this node directly would severe the link to the rest of the linked-list.

Let's just fix this.

new_item->next = temp->next;

Now our link is complete.

Our complete function looks like this:

void insert_at_custom(int item, int position) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->value = item;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        int i = 0;         while (i < position && temp->next != NULL) {            temp = temp->next;            i += 1;        }        new_item->next = temp->next;        temp->next = new_item;    }}

Deletion

Deletion of a node from the linked-list means completely erasing that node from memory. However, randomly deleting the node from memory would leave us with pointers pointing to invalid memory. Such a pointer is called a dangling pointer.

Let's go through different cases we could have for deletion.

Deletion From End

The first case we'd have for any deletion would be that the linked-list just does not exist.

That is, the list has no elements in it.

void delete_from_end() {    if (HEAD == NULL)        return;}

Simple, right? Now let's move on to a case where we actually have something to delete.

struct Node *temp = HEAD;while (temp->next->next != NULL) {    temp = temp->next;}

Remember doing this for our insert_at_end()? Except, we are looking for the second-last node instead of the last node. Why? Because we are gonna remove the last node.

struct Node *last = temp->next;temp->next = NULL;

In the above code, we are storing the last node's pointer in a different variable and removing the link from our linked-list.

Now the element is no longer inside the linked-list. But it still stays in the heap. How do we fix that?

free(last);

free() is another function from <stdlib> that allows us to free the memory to which our pointer is pointing.

Our complete function looks like this:

void delete_from_end() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        while (temp->next->next != NULL) {            temp = temp->next;        }        struct Node *last = temp->next;        temp->next = NULL;        free(last);    }}

Deletion From Beginning

Deletion from the beginning is much simpler.

void delete_from_beginning() {    if (HEAD == NULL)        return;}

It is the same upto this point.

But if the linked-list already has at least one element, we are modifying the connection as we want.

else {    struct Node *temp = HEAD;    HEAD = HEAD->next;}

And of course, a free() call.

Our complete function looks like this:

void delete_from_beginning() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        HEAD = HEAD->next;        free(temp);    }}

Deletion From Custom Position

Assume that our linked-list is a stack of ten legos stacked on top of each other.

Suppose you want to remove the third block, what do you do?

• Remove the fourth and above blocks from the stack.
• Remove the third block.
• Connect the fourth and above blocks with the second block.

In essence, it follows our insert_at_custom() and delete_from_end().

Our complete function looks like this:

void delete_from_custom(int position) {    if (HEAD == NULL)        return;    struct Node *temp = HEAD;    int i = 0;    while (i < position - 1 && temp->next->next != NULL) {            temp = temp->next;            i += 1;    }    struct Node *last = temp->next;    temp->next = last->next;    free(last);}

The working is the same as delete_from_end() except that we modify the connections in a different way.

What We Have Now

#include <stdlib.h>struct Node {    int data;    struct Node *next;};struct Node *HEAD;void insert_at_beginning(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Element *temp = HEAD;        HEAD = new_item;        HEAD->next = temp;    }}void insert_at_end(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        while (temp->next != NULL) {            temp = temp->next;        }        temp->next = new_item;    }}void insert_at_custom(int item, int position) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->value = item;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        int i = 0;         while (i < position && temp->next != NULL) {            temp = temp->next;            i += 1;        }        new_item->next = temp->next;        temp->next = new_item;    }}void delete_from_end() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        while (temp->next->next != NULL) {            temp = temp->next;        }        struct Node *last = temp->next;        temp->next = NULL;        free(last);    }}void delete_from_beginning() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        HEAD = HEAD->next;        free(temp);    }}void delete_from_custom(int position) {    if (HEAD == NULL)        return;    struct Node *temp = HEAD;    int i = 0;    while (i < position - 1 && temp->next->next != NULL) {            temp = temp->next;            i += 1;    }    struct Node *last = temp->next;    temp->next = last->next;    free(last);}

See Also

• Doubly Linked-List
• Stack
• Queue