Understanding insertion at beginning

Inserting at the beginning of a linked list is a fundamental and commonly used operation. It is an efficient method, especially when extending a list, and requires only a few lines of code to implement. When designing an algorithm for any data structure, it's important not to make assumptions about its underlying characteristics and to design the logic for a general case. With that in mind, there are two cases to consider when inserting at the beginning of a singly linked list.

1. The list is empty

In this scenario, if the linked list is empty, the head would be null. We need to initialize the head node of the linked list and ensure that the next pointer of this newly created head node is null, as this new node will also be the last node of the list.

Algorithm

• Step 1: Create a new node with the given data.
• Step 2: Set the new node's `next` pointer to `null` since it's the only node.
• Step 3: Return the new node, as this node is also the head node.

2. The list is not empty

In this scenario, we already have some data in the linked list, so the head is not null. Therefore, to insert a new node at the beginning of the list, we need to update the next pointer of the newly created node to store the reference of the existing head node.

Algorithm

• Step 1: Create a new node with the given data.
• Step 2: Set the new node's `next` pointer to hold the reference of the current head.
• Step 3: Return the new node, as this is the new head.

Implementation

When implementing the logic for the insert at the beginning operation, we consider both possible cases and write the code for each in conditional blocks.

Complexity Analysis

The time complexity of the above function does not depend on the list size. In all cases, we always need to insert the node at the start of the list, which takes constant time, i.e., O(1).

The space complexity of the function is also O(1) because it only creates a single new node and does not use any additional data structures.

Best Case

• Space Complexity - O(1)
• Time Complexity - O(1)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(1)