Linked List

In computer science, a ‘linked list’ is a data structure consisting of a group of nodes which together represent a sequence.

In the simplest form of linked list, each node consists of two elements:-
i. Data
ii. Reference to the next node in the sequence

Starting position of the linked list is called as ‘head’ and the last position of the linked list i.e. the position where the last element was added is called ‘tail’.
Following are the operations which can be done on linked list:-


Function
Complexity
Remark
Adding node at the head
O(1)
We perform action at the beginning of the linked list.
Adding node at the tail
O(1)
We perform action at the end of the linked list.
Adding node at n-th position
O(n)
We need to traverse list for ‘n’ positions.
Deleting node from the head
O(1)
We perform action at the beginning of the linked list.
Deleting node from the tail
O(n): Singly linked list
O(1): Doubly linked list
For SLL, We need to traverse list for ‘n’ positions. For DLL, we perform action at the end of the linked list.
Deleting node from n-th position
O(n)
We need to traverse list for ‘n’ positions.
Traversal
O(n)
We need to traverse list for ‘n’ positions.

Following are the types of linked lists which are widely used for implementation of various data structures:-

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

No comments :

Post a Comment