Singly Linked List – Create Operation

Linked Lists

Contents

IntroExamplePseudocodeExamplesTimeSpace

Creating a Singly Linked List

Creating a singly linked list involves building it node by node. Each node holds a value and a pointer to the next node. The last node points to null.

Unlike arrays, linked lists grow dynamically as we insert nodes — there is no need for pre-allocated size.

Visual Example

Let’s create a singly linked list by inserting these values one at a time: 10, 20, 30, 40.

Each value will be added to the end of the list, forming a chain where each node points to the next one.

Step-by-Step Construction

  1. Step 1: Create an empty list
    We start with no elements in our list. The head pointer is null, indicating the list is empty.
  2. Step 2: Insert 10 – It becomes the head.
    This is our first node. Since the list is empty, 10 is inserted and becomes the head node of the list.
  3. Step 3: Insert 20 – Append after 10.
    We create a new node with value 20. The current tail is 10, so we update its next pointer to point to 20.
  4. Step 4: Insert 30 – Append after 20.
    Again, we create a new node with value 30. We find the last node (currently 20) and update its next to point to 30.
  5. Step 5: Insert 40 – Append after 30.
    Finally, we create the node 40 and connect it to the end of the list by updating the next of 30.

Intuition Behind the Steps

  • A singly linked list is a series of nodes where each node holds a value and a reference (or pointer) to the next node.
  • We build it one node at a time by finding the last node (tail) and attaching the new node at the end.
  • The first node is special—it becomes the head of the list and serves as the entry point.

Complete Pseudocode: Create Linked List by Appending

This pseudocode builds a singly linked list by adding each new node to the end of the list.

function createLinkedList():
    head = null
    tail = null

    while input has values:
        value = next input
        node = new ListNode(value)

        if head == null:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node

    return head

Let’s walk through each part of the code to understand what it does.

function createLinkedList():
    head = null
    tail = null

Explanation: We start with an empty linked list. The head will point to the first node, and tail will point to the last node. Initially, both are set to null because the list is empty.

while input has values:
    value = next input
    node = new ListNode(value)

Explanation: We loop through the given input values (e.g., [10, 20, 30, 40]). For each value, we create a new node using new ListNode(value). This node will hold the data and a pointer to the next node (initially null).

    if head == null:
        head = node
        tail = node

Explanation: If the list is still empty (head is null), then this is the very first node we're adding. So, we set both head and tail to point to this new node. The head keeps track of where the list starts, and tail helps us keep track of the end.

    else:
        tail.next = node
        tail = node

Explanation: If the list already has at least one node, then we append the new node to the end. This is done by setting tail.next to point to the new node (i.e., connect the last node to the new one), and then updating tail to be the new node (i.e., the new node becomes the last node).

return head

Explanation: After all nodes have been added, we return head, which points to the first node in the linked list. From head, we can traverse the entire list by following the next pointers.

Linked List Creation Examples

The following examples show how nodes are added one by one to build a singly linked list dynamically.

Insert Sequence Final Linked List Explanation
[10, 20, 30] 10 → 20 → 30 → null Three nodes are inserted one after another. Each new node is linked to the previous one using the next pointer.
[5] 5 → null Only one node is inserted. It becomes both the head and the tail of the list.
[] null No values are provided, so the list remains empty with head = null.
[1, 2, 3, 4, 5] 1 → 2 → 3 → 4 → 5 → null Five nodes are inserted sequentially to build a full list. Each node points to the next until the last one, which points to null.

Time Complexity of Singly Linked List Create Operation

Creation Case Time Complexity Explanation
Creating list by appending with tail pointer O(n) Each new node is added in constant time. Creating a list of n nodes takes linear time overall.
Creating list by inserting at head O(n) Each new node is prepended in constant time. Total time grows linearly with the number of elements.

Space Complexity of Singly Linked List Create Operation

Creation Case Space Complexity Explanation
Creating a list of n nodes O(n) Each node takes space for its value and a pointer to the next node, resulting in linear space usage.

Key Takeaways

  • Singly linked lists grow dynamically by linking nodes one-by-one.
  • Use a tail pointer to insert efficiently at the end.
  • The last node always points to null.
  • Head is needed to return the complete list.

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...