Introduction to Linked List

#programming #algorithms #computerscience

A Linked list is a linear data structure used for storing collections of data and which consist of a group of nodes.

Each node contains two fields:
Data: That stored at a particular address.
Pointer: Which contains the address of the next node.

Generally, we call the first node as Head node and the last node as Tail node in Linked List.

There are three main linked list operations
->Insertion
->Deletion
->Traversing

Why Linked List Over Array?
Array contains the following limitations:

->The size of an array is fixed. We must know the size of the array at the time of its creation subsequently, it is difficult to change its size at runtime.
->Inserting a new element in an array of elements is difficult because we need to shift elements to create room for new elements to insert.
->Deleting an element in an array is also difficult as it also takes shifting of elements in the array.

Advantages of Linked List:
->Insertion and deletion operations can be implemented very easily and these are not costly as they do not require shifting of elements.
->They are dynamic in nature. Hence, we can change their size whenever required.

Types Of Linked List
->Singly Linked List
->Circular Linked List
->Doubly Linked List

Singly Linked List:
A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).

Circular Linked List:
Circular Linked List is similar to singly Linked List but the last node of List has a pointer to the node which points to the head node (first node) of Linked List. We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending.

There is no null value present in the next part of any of the nodes.

Doubly Linked List:
In Doubly Linked List each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list.