Linked list

 

 

What is linked list?

One disadvantage of using array to store data is that array are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertion and deletion of elements to avoid this we will learn new data structure called Linked List.

A linked list is a data structure used for storing collections of data.

A linked list has the following properties.
·      Successive elements are connected by pointers
·      The last element points to NULL
·      Can grow or shrink in size during execution of a program
·      Can be made just as long as required
·      Does not waste memory space (but takes some extra memory for pointers). It allocates memory as list grows.

Representation of Linked List

Let's see how each node of the linked list is represented.

Each node in linked list consists of:

•    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;

};

 

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;

 

The linked list will look like this:

Types of linked list

There are three common types of Linked List.

1. Singly linked List
2. Doubly linked list 
3. Circular linked list

Singly linked list

In singly linked list is a data structure that contains two parts, out of them one is the data part, and the other one is the address part. The address part contains the address of the next or the successor node. The address part in a node is also known as a pointer.

The node in singly linked list is represented as:

Struct Node {

  int data;

  struct node *next;

}

 

The singly linked list looks like this:

 

Doubly linked list

a doubly linked list is a list that has three parts in a single node, where one is data part and other two are address part. In the two address part one is pointer to previous node means it stores the address of previous node , and a pointer to the next node which stores the address of next node.

The node of doubly linked list is represented as:

Struct Node {

  Struct node *prev;

  int data;

  struct node *next;

}

 

The doubly linked list looks like this:

Circular linked list

Circular linked list is similar to singly linked list the only difference is the last node in circular linked list is linked to the first node.

The node of singly linked list and circular linked list are same.

The circular linked list looks like this:

Linked list Operations

The operations in linked list are as follows:

• Traversal - access each element of the linked list.
• Insertion - adds a new element to the linked list.
• Deletion - removes the existing elements,
• Search - find a node in the linked list.

Transversal

In transversal, we have to display all the elements in linked list.                               Firstly, we create a temporary node and point it to head node and move temp node to next node until it becomes null and display the temp->data one by one during transversal.

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

The code for transversal is:

struct node *temp = head;

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

while(temp != NULL) {

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

  temp = temp->next;

}

 

Insertion

In insertion we add new element to the linked list.

The are three types of insertions in linked list as follows:

• At beginning.
• At  end 
• At specific position.

At beginning

Here we insert element before first node.

Firstly, we create new node and allocate memory to it, then we store data in new node and point the next of new node to head.

Code for inserting element at beginning is as follows:

struct node *newNode;

newNode = malloc(sizeof(struct node));

newNode->data = 4;

newNode->next = head;

head = newNode;

At end

Here we add element to the end of linked list.

Firstly, we create new node and allocate memory to it, then we store data in new node and store the address of new node in the next pointer of last node and make new node as last node.

Code for inserting element at end is as follows:

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;

 

At specific position

Here we add element at the position we want in linked list.

Firstly, we create new node and allocate memory to it, then we store data in new node and transverse the node just before the required position of new node and change the next pointers to include new node in between.

Code for inserting element at specific position is as follows:

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;

 

Deletion

In deletion we delete element from the linked list.

There are three types of deletion in linked list as follows:

•         From beginning. 
•       From end. 
•       From specific position.

From beginning

Here we delete the first node only.                                                                                        In deletion at beginning, we just have to point the head to its next node.

head = head->next;

 

From end

Here we delete the last element of linked list.

Firstly, we take a temporary pointer and transverse it throughout the linked until we reach the second last element and then we make the next pointer of that second last element to NULL.

Code for deleting element from end of linked list is as follows:

struct node* temp = head;

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

  temp = temp->next;

}

temp->next = NULL;

 

From specific position

Here, we delete the element from the specific position.

Firstly, we take a temporary pointer and transverse it throughout the linked until we reach the position before we the element to be deleted, and we assign the next of temp to the next of element to be deleted.

Code for deleting element from specific position of linked list is as follows:

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

  if(temp->next!=NULL) {

    temp = temp->next;

  }

}

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

 

Search

To search element from the linked list firstly, will take a temporary pointer and point it to head and create a loop and transverse through the loop until the pointers next becomes NULL and while traversing will compare the element to be searched with the temp pointers data as soon as we get the element will return that element and stop traversing.

The code for searching element in linked list is as follows;

// Search a node

bool searchNode(struct Node** head_ref, int key) {

  struct Node* current = *head_ref;

  while (current != NULL) {

    if (current->data == key) return true;

      current = current->next;

  }

  return false;

}