Creating a Singly Linked List from Scratch in DSA C - Visual Walkthrough

Concept Flow - Creating a Singly Linked List from Scratch

Start

↓

Create head node with data

↓

Set head.next = NULL

↓

For each new data item

↓

Create new node

↓

Traverse list to last node

↓

Set last_node.next = new_node

↓

Set new_node.next = NULL

↓

Repeat or End

We start by creating the first node as head. For each new item, we create a node, find the last node, and link the new node at the end.

Execution Sample

DSA C

#include <stdlib.h>

struct Node {
  int data;
  struct Node* next;
};

struct Node *head;

// Create head node
head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = NULL;

This code creates the first node of the singly linked list with data 10 and sets its next pointer to NULL.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create head node with data=10	10	head -> Node(10)	10 -> NULL
2	Create new node with data=20	10, 20	new_node -> Node(20)	10 -> NULL, 20 -> NULL
3	Traverse to last node (10)	10, 20	current -> Node(10)	10 -> NULL, 20 -> NULL
4	Link last node next to new_node	10, 20	10.next -> 20	10 -> 20 -> NULL
5	Create new node with data=30	10, 20, 30	new_node -> Node(30)	10 -> 20 -> NULL, 30 -> NULL
6	Traverse to last node (20)	10, 20, 30	current -> Node(20)	10 -> 20 -> NULL, 30 -> NULL
7	Link last node next to new_node	10, 20, 30	20.next -> 30	10 -> 20 -> 30 -> NULL
8	End of insertions	10, 20, 30	No pointer changes	10 -> 20 -> 30 -> NULL

💡 All nodes inserted; last node's next pointer is NULL indicating end of list.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	After Step 7	Final
head	NULL	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
new_node	NULL	NULL	Node(20)	Node(20)	Node(30)	Node(30)	NULL
current	NULL	NULL	NULL	Node(10)	Node(10)	Node(20)	NULL
List Size	0	1	1	2	2	3	3

Key Moments - 3 Insights

Why do we set the new node's next pointer to NULL?

Because the new node is the last node in the list, its next pointer must be NULL to mark the end. See steps 1, 2, 5 in execution_table where new nodes are created with next = NULL.

Why do we traverse to the last node before linking the new node?

We must find the current last node to link its next pointer to the new node. This is shown in steps 3 and 6 where current points to the last node before linking.

What happens if the list is empty when inserting the first node?

If the list is empty, head is NULL. We create the first node and assign it to head, as in step 1. No traversal is needed.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of the list?

A 10 -> 20 -> NULL

B 10 -> NULL, 20 -> NULL

C 20 -> 10 -> NULL

D 10 -> 20 -> 30 -> NULL

💡 Hint

Check the Visual State column at step 4 in execution_table.

At which step does the list size become 3 according to variable_tracker?

A After Step 4

B After Step 5

C After Step 7

D After Step 2

💡 Hint

Look at the List Size row in variable_tracker and find when it reaches 3.

If we forget to set new_node->next = NULL when creating a new node, what will happen to the list?

A The list will end correctly with NULL.

B The list may have a cycle or undefined end.

C The head pointer will be lost.

D The new node will not be linked.

💡 Hint

Think about the importance of NULL in marking the end of the list as shown in key_moments.

Concept Snapshot

Creating a Singly Linked List:
- Define Node with data and next pointer
- Create head node with data and next = NULL
- For each new data:
  - Create new node with next = NULL
  - Traverse to last node
  - Link last node's next to new node
- Last node's next always NULL to mark list end

Full Transcript

To create a singly linked list from scratch, start by defining a node structure with data and a next pointer. Create the head node with the first data value and set its next pointer to NULL, indicating the end of the list. For each new data item, create a new node with next set to NULL. Then, traverse the list from head to find the last node whose next pointer is NULL. Link this last node's next pointer to the new node. Repeat this process for all new data items. The last node's next pointer always remains NULL to mark the end of the list. This process ensures a chain of nodes connected by next pointers, forming the singly linked list.

Practice

1. What is the main purpose of a singly linked list in data structures?

easy

A. To store elements with direct access by index like an array

B. To store elements in a sequence where each element points to the next

C. To store elements in a sorted order automatically

D. To store elements with multiple pointers to previous nodes

Solution

1. Step 1: Understand singly linked list structure

   A singly linked list stores elements where each node points only to the next node, forming a chain.

2. Step 2: Compare with other data structures

   Unlike arrays, singly linked lists do not provide direct index access, and unlike doubly linked lists, nodes have only one pointer.

3. Final Answer:

   To store elements in a sequence where each element points to the next -> Option B

4. Quick Check:

   Singly linked list = sequence with next pointers [OK]

Hint: Remember: singly linked list nodes have one next pointer only [OK]

Common Mistakes:

• Thinking singly linked list allows direct index access
• Confusing singly linked list with doubly linked list
• Assuming automatic sorting in singly linked list

2. Which of the following is the correct way to define a node structure for a singly linked list in C?

easy

A. typedef struct Node { int data; struct Node* next; } Node;

B. typedef struct Node { int data; Node* next; } Node;

C. struct Node { int data; struct Node next; };

D. struct Node { int data; struct Node* prev; };

Solution

1. Step 1: Check pointer usage in struct

   The next pointer must be a pointer to struct Node, so use struct Node* next;.

2. Step 2: Verify typedef correctness

   typedef struct Node { int data; struct Node* next; } Node; correctly uses typedef and pointer syntax for next node.

3. Final Answer:

   typedef struct Node { int data; struct Node* next; } Node; -> Option A

4. Quick Check:

   Node struct uses pointer to struct Node for next [OK]

Hint: Use 'struct Node* next;' inside struct for next pointer [OK]

Common Mistakes:

• Omitting 'struct' keyword before Node* inside struct
• Using 'Node* next;' without typedef defined yet
• Using 'struct Node next;' instead of pointer
• Using 'prev' pointer instead of 'next' for singly linked list

3. What will be the output of the following C code snippet that creates a singly linked list with two nodes and prints their data?

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* head = malloc(sizeof(Node));
    head->data = 10;
    head->next = malloc(sizeof(Node));
    head->next->data = 20;
    head->next->next = NULL;

    Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    return 0;
}

medium

A. 10 20

B. 20 10

C. 10

D. Compilation error

Solution

1. Step 1: Trace node creation and data assignment

   First node data is 10, second node data is 20, linked correctly.

2. Step 2: Trace printing loop

   Loop prints data of head (10), then moves to next node (20), then stops at NULL.

3. Final Answer:

   10 20 -> Option A

4. Quick Check:

   Prints nodes in order: 10 then 20 [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Confusing order of nodes printed
• Forgetting to set next of last node to NULL
• Assuming compilation error due to missing includes (not shown)

4. Identify the error in the following code that attempts to create a singly linked list node and assign data:

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* head;
    head->data = 5;
    head->next = NULL;
    return 0;
}

medium

A. data should be a pointer, not int

B. next pointer should point to previous node

C. head is not initialized before accessing its members

D. struct Node definition is incorrect

Solution

1. Step 1: Check pointer initialization

   head is declared but not assigned memory before accessing its members.

2. Step 2: Understand consequences

   Accessing head->data without allocation causes undefined behavior or crash.

3. Final Answer:

   head is not initialized before accessing its members -> Option C

4. Quick Check:

   Pointer must be allocated before use [OK]

Hint: Always allocate memory before using pointer members [OK]

Common Mistakes:

• Assuming pointer is auto-initialized
• Confusing next pointer direction
• Thinking data must be pointer type

5. You want to create a singly linked list from scratch that stores integers 1, 2, 3 in order. Which sequence of operations correctly builds the list?

hard

A. Allocate node1, set data=1, set node1->next=NULL, allocate node2, set data=2, set node2->next=NULL, allocate node3, set data=3, set node3->next=NULL

B. Allocate node1, set data=1, allocate node2, set data=2, allocate node3, set data=3, link node3->next=node2, link node2->next=node1, set node1->next=NULL

C. Allocate node1, set data=1, link node1->next=node2, allocate node2, set data=2, link node2->next=node3, allocate node3, set data=3, set node3->next=NULL

D. Allocate node1, set data=1, allocate node2, set data=2, link node1->next=node2, allocate node3, set data=3, link node2->next=node3, set node3->next=NULL

Solution

1. Step 1: Allocate nodes and assign data in order

   Nodes must be allocated and data assigned before linking.

2. Step 2: Link nodes in correct sequence

   Link node1 to node2, node2 to node3, and node3 to NULL to end list.

3. Final Answer:

   Allocate node1, set data=1, allocate node2, set data=2, link node1->next=node2, allocate node3, set data=3, link node2->next=node3, set node3->next=NULL -> Option D

4. Quick Check:

   Correct order and linking builds list 1->2->3->NULL [OK]

Hint: Link nodes only after allocating and setting data [OK]

Common Mistakes:

• Linking nodes before allocation
• Not setting last node's next to NULL
• Linking nodes in reverse order