Linked List and Its Operations

Linked List

In a game of Treasure Hunt, you start by looking for the first clue. When you find it, instead of having the treasure, it has the location of the next clue and so on. You keep following the clues until you get to the treasure.

A linked list is similar. It is a series of connected "nodes" that contains the "address" of the next node. Each node can store a data point which may be a number, a string or any other type of data.

Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work and you must also be familiar with dynamic memory allocation and structures.

Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array.

Linked lists have a few advantages over arrays:

1.    Items can be added or removed from the middle of the list

2.    There is no need to define an initial size

However, linked lists also have a few disadvantages:

1.    There is no "random" access - it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.

2.    Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.

3.    Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated (which is less efficient in memory usage) and each item in the list also must store an additional pointer.

Linked List Representation

You have to start somewhere, so we give the address of the first node a special name called HEAD.

Also, the last node in the linked list can be identified because its next portion points to NULL.

How another node is referenced?

Some pointer magic is involved. Let's think about what each node contains:

• A data item
• An address of another node

We wrap both the data item and the next node reference in a struct as:

struct node

{

  int data;

  struct node *next;

};

Understanding the structure of a linked list node is the key to having a grasp on it.

Each struct node has a data item and a pointer to another struct node. Let us create a simple Linked List with three items to understand how this works.

/* Initialize nodes */

struct node *head;

struct node *one = NULL;

struct node *two = NULL;

struct node *three = NULL;

/* Allocate memory */

one = malloc(sizeof(struct node));

two = malloc(sizeof(struct node));

three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;

two->data = 2;

three->data=3;

/* Connect nodes */

one->next = two;

two->next = three;

three->next = NULL;

/* Save address of first node in head */

head = one;

If you didn't understand any of the lines above, all you need is a refresher on pointers and structs.

In just a few steps, we have created a simple linkedlist with three nodes.

The power of linked list comes from the ability to break the chain and rejoin it. E.g. if you wanted to put an element 4 between 1 and 2, the steps would be:

Create a new struct node and allocate memory to it.

Add its data value as 4

Point its next pointer to the struct node containing 2 as data value

Change next pointer of "1" to the node we just created.

Doing something similar in an array would have required shifting the positions of all the subsequent elements.

Utility of Linked List

Lists are one of the most popular and efficient data structures, with implementation in every programming language like C, C++, Python, Java and C#.

Apart from that, linked lists are a great way to learn how pointers work. By practicing how to manipulate linked lists, you can prepare yourself to learn more advanced data structures like graphs and trees.

Types of Linked List

There are three common types of Linked List.

·         Singly Linked List

·         Doubly Linked List

·         Circular Linked List

Singly Linked List

It is the most common. Each node has data and a pointer to the next node.

Node is represented as:

struct node {

    int data;

    struct node *next;

}

A three member singly linked list can be created as:

/* Initialize nodes */

struct node *head;

struct node *one = NULL;

struct node *two = NULL;

struct node *three = NULL;

/* Allocate memory */

one = malloc(sizeof(struct node));

two = malloc(sizeof(struct node));

three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;

two->data = 2;

three->data = 3;

/* Connect nodes */

one->next = two;

two->next = three;

three->next = NULL;

/* Save address of first node in head */

head = one;

Doubly Linked List

We add a pointer to the previous node in a doubly linked list. Thus, we can go in either direction: forward or backward.

A node is represented as

struct node {

    int data;

    struct node *next;

    struct node *prev;

}

A three member doubly linked list can be created as

/* Initialize nodes */

struct node *head;

struct node *one = NULL;

struct node *two = NULL;

struct node *three = NULL;

/* Allocate memory */

one = malloc(sizeof(struct node));

two = malloc(sizeof(struct node));

three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;

two->data = 2;

three->data = 3;

/* Connect nodes */

one->next = two;

one->prev = NULL;

two->next = three;

two->prev = one;

three->next = NULL;

three->prev = two;

/* Save address of first node in head */

head = one;

Circular Linked List

A circular linked list is a variation of linked list in which the last element is linked to the first element. This forms a circular loop.

A circular linked list can be either singly linked or doubly linked.

·         for singly linked list, next pointer of last item points to the first item

·         In doubly linked list, prev pointer of first item points to last item as well.

A three member circular singly linked list can be created as:

/* Initialize nodes */

struct node *head;

struct node *one = NULL;

struct node *two = NULL;

struct node *three = NULL;

/* Allocate memory */

one = malloc(sizeof(struct node));

two = malloc(sizeof(struct node));

three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;

two->data = 2;

three->data = 3;

/* Connect nodes */

one->next = two;

two->next = three;

three->next = one;

/* Save address of first node in head */

head = one;

Linked List Operations

Now that you have got an understanding of the basic concepts behind linked list and their types, its time to dive into the common operations that can be performed.

Two important points to remember:

head points to the first node of the linked list

next pointer of last node is NULL, so if next of current node is NULL, we have reached end of linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3with node structure as below:

struct node

{

  int data;

  struct node *next;

};

How to traverse a linked list

Displaying the contents of a linked list is very simple. We keep moving the temp node to the next one and display its contents.

When temp is NULL, we know that we have reached the end of linked list so we get out of the while loop.

struct node *temp = head;

printf("\n\nList elements are - \n");

while(temp != NULL)

{

     printf("%d --->",temp->data);

     temp = temp->next;

}

The output of this program will be:

List elements are -

1 --->2 --->3 --->

How to add elements to linked list

You can add elements to beginning, middle or end of linked list.

Add to beginning

·         Allocate memory for new node

·         Store data

·         Change next of new node to point to head

·         Change head to point to recently created node

struct node *newNode;

newNode = malloc(sizeof(struct node));

newNode->data = 4;

newNode->next = head;

head = newNode;

Add to end

·         Allocate memory for new node

·         Store data

·         Traverse to last node

·         Change next of last node to recently created node

struct node *newNode;

newNode = malloc(sizeof(struct node));

newNode->data = 4;

newNode->next = NULL;

struct node *temp = head;

while(temp->next != NULL){

  temp = temp->next;

}

temp->next = newNode;

Add to middle

·         Allocate memory and store data for new node

·         Traverse to node just before the required position of new node

·         Change next pointers to include new node in between

struct node *newNode;

newNode = malloc(sizeof(struct node));

newNode->data = 4;

struct node *temp = head;

for(int i=2; i < position; i++) {

    if(temp->next != NULL) {

        temp = temp->next;

    }

}

newNode->next = temp->next;

temp->next = newNode;

How to delete from a linked list

You can delete either from beginning, end or from a particular position.

Delete from beginning

Point head to the second node

head = head->next;

Delete from end

Traverse to second last element

Change its next pointer to null

struct node* temp = head;

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

  temp = temp->next;

}

temp->next = NULL;

Delete from middle

Traverse to element before the element to be deleted

Change next pointers to exclude the node from the chain

for(int i=2; i< position; i++) {

    if(temp->next!=NULL) {

        temp = temp->next;

    }

}

temp->next = temp->next->next;