Linked List Data structure – Full Guide

What is a Linked-List

A linked list is a data structure in which each element contains a value and the address of the next element. Thus, it is not necessary to store data sequentially like in Arrays. The advantage of a linked list over an array is that linked lists do not require fixed space in memory and new elements can be added increasing its length on demand.

Applications of Linked Lists:

1. Dynamic memory allocation: Since fixed memory is not needed when initializing a linked list, the linked list can accommodate as many nodes as required on demand.
2. Stacks & Queues can be implemented with the help of linked lists
3. Arithmetic operations on long integers.
4. To represent polynomials.

Types of Linked Lists

Singly-linked list

This linked list has elements connected in one direction only.

Doubly linked list

This linked list has elements connected in both directions.

Circular Linked List

This linked list has elements connected in one direction only and the head and tail nodes are also connected forming a circular structure.

Circular Doubly-linked list

This linked list has elements connected in both directions and the head and tail nodes are also connected forming a circular structure.

Linked List Operations

• Insertion: Initialize a new node, change the address of the left node, and add the address of the right node to the new node.
• Deletion: Change the address of the left node to that of the right node. The current node will get delinked from the linked list.
• Search: Traverse the linked list in order till we find the element.
• Reversal: Start from the tail node and copy the address of the left node to the right node. Make the address of the head node null.