Data Structure And Algorithm - Simple Linked List

Today we are going to discuss about Linked Lists.

There are 3 kinds of linked lists.
1. Simple Linked List
2. Double Linked List
3. Circular Linked List

Why Linked List ?

Linked list are most commonly used after arrays. There are few advantages listed below over arrays.

1. Linked lists are dynamic data structures because they can grow by allocating memory and pruned by deallocating the memory dynamically.

2. Items in the linked list can be removed or added at any position of the linked list.

3. Insertion and deletion of elements are easier.


In linked list, the items are connected in a sequence via links and the basic operations are:

1. Insertion
2. Deletion
3. Display
4. Search
5. Delete

For Simple Linked list there are 3 basic operations and 2 operations are explained below
1. Insertion
2. Deletion
3. Reverse

I would like to explain Insertion here

Lets consider a Linked list with Node 1 and Node 2 as show in below figure

Now I want to insert a node in between node 1 and node 2

Now we have to attach Node1.2 next to the Node 2 as shown below

Now remove the connection between node 1 and node 2 and connect node 1 next to the node 1.2 as shown below

Finally we have inserted the node in the middle and the Linked list looks like below.

Similarly Deletion looks exactly reverse way of Insertion.

Lets consider we have node 1, node 2 and node 3. We want to remove node 2, so follow the steps below.

Step 1: Change the node1 next to node 3 from node 2

Step 2: Remove the connection of node 2 next from node 3

Step 3: Display the final list with node 1 and node 3.