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:
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
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 nth 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 nth 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