What is a Linked List?

Linked List consists of a sequence of nodes. These nodes are made-up of the following:

• A Data Field for housing the data item

• One or Two Reference/s for pointing at other node/s i.e. pointing to the next/previous node/s.

In this data structure, the nodes are allowed to be inserted and removed at any point in the list in constant time, however random access in not possible.

Related posts:

• Algorithm that returns the middle element of a double linked list
• Operation time complexity for a LINKED LIST

Operation time complexity for a LINKED LIST

The time complexity of handling the operations in a data structure like a LINKED LIST are as follows:

i. Most of the operations are O(n) [i.e. omega times n]
ii. Remove/Insert operations that handles element between elements require O(1) [i.e. omega times one] this is due to references/pointers on both the ends of the list, hence the elements don't require to be shifted. However, due to the references/pointers this data structure requires additional memory!