Linked Lists

What is a linked list?

The Linked Lists is another data structure and is also a common data structure which includes a group of nodes in a sequence which is divided in two parts and each node consists of data and the address part of the next node and forms a chain. It is used to create a tree and graph.

Merits

  • It is dynamic in nature and it allocates the memory as and when required.
  • There are two operations which can be implemented easily in linked lists i.e. Insertion and Deletion.
  • It reduces the access time.

Demerits

  • The memory is wasted as pointers require extra memory for storage.
  • The element cannot be accessed randomly, it can be accessed sequentially.
  • In linked list reverse traversing is difficult.

 

Where the linked list is used?

 

1. They are used to implement stacks, queues, graphs, etc.

2. They let you insert elements at the beginning and the end of the list.

3. In this it does not require knowing the size in advance.

Types of Linked Lists

Singly Linked List-

This type of list contains nodes which have a data part as well as an address part, i.e. next, and it points to the next node in the given sequence of nodes. The operations we can perform on singly linked lists are inserted, deletion and traversal
.

 

Doubly Linked List-

In this type of list, each node contains the two links, the first link will point to the previous node and the next link will point to the next node in the sequence.

  • Circular Linked List- In this type of list, the last node of the list contains the address of the first node and will form a circular chain.

Singly Linked List

The singly linked list is that in which each node contains only one link field which points to the next node. In this the node is divided into two parts the first part is the data part and the other is the link part which contains the address of the next node. The first node is the header node which contains the data and the address of the next node and so on. The singly linked list is also known as one way list because it can be traversed only from left to right, the other way is not possible.




Where the singly linked list is used?

The singly linked list can be used in stacks which uses last in, first out concept. This list maintains a link with the head node in the list and each node points to the next node in the list. It can be also used in queues which follow first in, first out.

Implementation of singly linked list in C

 

Doubly Linked List

The doubly linked list is also known as two way lists or two way chains. In the doubly linked list the two link field are maintained instead of one as like in singly linked list. The doubly linked list is a linear data structure in which each node has two links where the first link is used to point the previous node and the next link points to the next node. The operations performed on the doubly linked list are insertion, deletion, search and traversal.


Where the doubly linked list is used?

  1. It is used to represent the deck of cards in game.
  2. It is used in applications that have Most Recently Used list.
  3. It is used as an undo function in Word or Photoshop.
  4. It is used in browser cache which allows us to hit the BACK button.

Implementation of doubly linked list using C

Circular Linked List

The Circular Linked List is little bit complicated linked data structure. In this list we can insert elements anywhere within the list whereas in the array we cannot insert elements anywhere in the list because it is in the contiguous memory. In this list the previous element stores the address of the next element and the last element stores the address of the first element. The elements in the list point to each other in a circular way which forms a circular chain. This list has a dynamic size which means the memory can be allocated as and when it is required.

Where the circular linked list is used?

The real life application where this list is used is the PC where multiple applications run on it. The circular linked list is common in the operating system as it puts the running applications on the list and it is easy for the operating system to use the circular linked list as when the list is going to reach to its end the operating system can cycle around to the front of the list. The time slot is given to each of the applications in the list.

Implementation of circular linked list in C

Linear Linked Lists

In linked list we can insert elements in three ways:

  • Insertion at beginning of the list.
  • Insertion at middle of the list.
  • Insertion at the end of the list.

Before inserting the node in the list we will create a structure using the keyword struct. For example:

And after defining the structure the function definition or function prototype is given of the particular, while inserting or deleting a node from the list. For example:

The function definition given above are defined before the main function i.e. void main ( ) or int main( ).

Inserting element at the beginning

Steps to insert a node at beginning:

  1. Create a new node.
  2. Enter the data in the data part.
  3. Make the address part or the next part as NULL.
  4. Now attach this new created node to START or HEAD.
  5. Now make this starting node as the starting node or the header node.

Implementation

Inserting element at the middle

Steps to insert node at middle:

  1. Write the data of a NEW node to be added in the list and its position.
  2. Create a NEW empty node by calling malloc( ).
  3. Insert the data inside the NEW node’s data part.
  4. Add this NEW node at the desired position in the list.
  5. Go to step-1 till you have added all the values in the list.

Implementation

Inserting element at last of the list:


Steps to insert node at last:

  1. Create new node.
  2. Enter data into data part of the node.
  3. Make the next part of the node as NULL.
  4. Node is to be inserted at last position so we have to traverse till last node.
  5. Make a link between last node and new node.

Implementation

Deletion

The element can be deleted in three ways:

  • Deletion from the beginning of the list.
  • Deletion from the middle of the list.
  • Deletion from the end of the list.

Deleting element from the beginning

Deleting element from the middle

Implementation

Deleting element from the last

Implementation

Display

To display the elements of the list after any operation performed.

Leave A Comment

Your email address will not be published. Required fields are marked *