Introduction to Linked List

In this Post we will go through Linked List Data Structure.

A Linked List is a way of storing collections of data.

Key Points:

• • Data elements stored in a Linked List are commonly called as Nodes.
• • Each Node contains two parts, data and a pointer to next Node.
• • Pointer of the Last Node in a Linked List points to null.
• • First Node of the Linked List is commonly called as Head.

Advantages:

• • Does not waste extra memory other than pointer to next node.
• • Can add or delete elements as needed.
• • Faster insertions at the beginning of the Linked List.

Disadvantages:

• • Takes extra space to store pointer to next Node.
• • Accessing/Searching an element does not take constant time.

Basic Operations:

Search: Search operation on a Linked List takes O(n) for Time Complexity and O(1) for Space Complexity.

Insertion: Each Linked List consists of two main parts of information, i.e. Data part and a pointer to next Node. So, to store a data element, an extra space is needed to store a pointer to next Node, hence Space Complexity of a Linked List is O(n).

• • At the begininning of a Linked List takes O(1) for Time Complexity and O(n) for Space Complexity.
• • From the middle of a Linked List takes O(n) for Time Complexity and O(n) for Space Complexity.
• • At the End/In the middle of a Linked List takes O(n) for Time Complexity and O(n) for Space Complexity.

Update:

• • At the beginning of a Linked List takes O(1) for Time Complexity and O(1) for Space Complexity.
• • From the middle of a Linked List takes O(n) for Time Complexity and O(1) for Space Complexity.
• • At the end of the Linked List takes O(n) for Time Complexity and O(1) for Space Complexity.

Deletion:

• • At the beginning of a Linked List takes O(1) for Time Complexity and O(1) for Space Complexity.
• • From the middle of a Linked List takes O(n) for Time Complexity and O(1) for Space Complexity.
• • At the end of the Linked List takes O(n) for Time Complexity and O(1) for Space Complexity.

Types Of Linked Lists: Below are the basic types of Linked Lists,

• • Singly Linked List
• • Doubly Linked List
• • Circular Linked List

Singly Linked List: Generally a Linked List is refered as a Singly Linked List. Accessing elements in a Singly Linked List is unidirectional.

Doubly Linked List: Each Node in Doubly Linked List contains pointers for previous and next Nodes. Accessing elements in a Doubly Linked List is bidirectional.

Circular Linked List: Unlike other Linked Lists, Circular Linked List does not have end. It is unidirectional. Last Node of the Circular Linked List points to the Head. So, need to be cautious when accessing elements in a Circular Linked List.