Linked Lists

What is a linked list?

The Linked Lists is another data structure and is also a common data structure that includes a group of nodes in a sequence that is divided into 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 linked 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 a 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 that use the 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.

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 is maintained instead of one as like in the 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 to 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?

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

Circular Linked List

The Circular Linked List is a 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 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.

Linear Linked Lists

In the 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( ).