Singly Linked List

A singly linked list is the simplest type of linked list, where each node contains data and a pointer to the next node of the same data type. The general syntax of singly linked list is given below

Singly link list - Syntax

where,

  • Head: Points to the first node in the list.
  • Data: Stores the value or content of the node.
  • Next pointer: Points to the next node in the list.

In C programming: Code

#include <stdio.h>
#include <stdlib.h>struct Node {
int data; // Data part
struct Node *next; // Pointer to the next node
};

Node Structure of the Singly Liked list

Address Offset Data Next Pointer
350 +0 Data (10)
358 +8 Next (pointer) 380 (address of Node 2)
380 +0 Data (20)
388 +8 Next (pointer) 700(address of Node 3)
700 +0 Data (30)
708 +8 Next (pointer) NULL (end of list)

Single Node Explaination in Singly Liked list

Memory Layout - Singly Linked List

For each node in memory, two parts are allocated:

  1. Data Field:
    • Stores the actual data (e.g., an integer).
    • The size depends on the data type. For an integer (int), it typically requires 4 bytes (depending on the system architecture).
  2. Pointer Field (next):
    • Stores the address of the next node.
    • Since this is a pointer to a struct Node, it typically requires 4 bytes on a 32-bit system or 8 bytes on a 64-bit system.
  3. Ofsets field:  offset indicates the relative position of a particular field within the node’s memory block.
    • When accessing the data of a node, the program uses current->data, which internally means accessing the base address plus an offset of 0.
    • When accessing the next pointer, the program uses current->next, which means accessing the base address plus an offset of 4 bytes.
  4. Node Size:  Each node typically occupies (size of data) + (size of "Next" pointer) bytes in memory.

 Byte by Byte Memory layout

Here is the updated table with an additional column that assigns nodes based on the address range for 32 bit system where the address is 4 byte in size

Updated Byte-by-Byte Memory Layout Table (32-bit Addresses)

Address in Decimal Address in Binary (32-bit) Data in Binary (Byte by byte) Description Node
350 00000000 00000000 00000001 01011110 00001010 First byte of data (10) Node 1
351 00000000 00000000 00000001 01011111 00000000 Second byte of data (10) Node 1
352 00000000 00000000 00000001 01100000 00000000 Third byte of data (10) Node 1
353 00000000 00000000 00000001 01100001 00000000 Fourth byte of data (10) Node 1
354 00000000 00000000 00000001 01100010 10111100 First byte of pointer (380) Node 1
355 00000000 00000000 00000001 01100011 00010111 Second byte of pointer (380) Node 1
356 00000000 00000000 00000001 01100100 00000000 Third byte of pointer (380) Node 1
357 00000000 00000000 00000001 01100101 00000000 Fourth byte of pointer (380) Node 1
380 00000000 00000000 00000001 01111000 00010100 First byte of data (20) Node 2
381 00000000 00000000 00000001 01111001 00000000 Second byte of data (20) Node 2
382 00000000 00000000 00000001 01111010 00000000 Third byte of data (20) Node 2
383 00000000 00000000 00000001 01111011 00000000 Fourth byte of data (20) Node 2
384 00000000 00000000 00000001 10000000 00000010 First byte of pointer (700) Node 2
385 00000000 00000000 00000001 10000001 10111000 Second byte of pointer (700) Node 2
386 00000000 00000000 00000001 10000010 00000000 Third byte of pointer (700) Node 2
387 00000000 00000000 00000001 10000011 00000000 Fourth byte of pointer (700) Node 2
700 00000000 00000000 00000010 10111000 00011110 First byte of data (30) Node 3
701 00000000 00000000 00000010 10111001 00000000 Second byte of data (30) Node 3
702 00000000 00000000 00000010 10111010 00000000 Third byte of data (30) Node 3
703 00000000 00000000 00000010 10111011 00000000 Fourth byte of data (30) Node 3
704 00000000 00000000 00000010 11000000 00000000 NULL pointer (first bytes) Node 3
705 00000000 00000000 00000010 11000001 00000000 NULL pointer (all 2nd bytes) Node 3
706 00000000 00000000 00000010 11000010 00000000 NULL pointer (all 3rd bytes) Node 3
707 00000000 00000000 00000010 11000011 00000000 NULL pointer (all 4th bytes) Node 3

Characteristics of Singly linked list 

Here are the key characteristics of a singly linked list:

  • Sequential Access: Nodes are connected in sequence, with each node pointing to the next.
  • Unidirectional: Traversal is only possible from the head to the end; there’s no backward link.
  • Dynamic Size: It can easily grow or shrink in size by adding or removing nodes.
  • Non-Contiguous Memory: Nodes are stored in non-contiguous memory locations, linked via pointers.
  • Head Pointer: The head pointer keeps track of the first node; if the head is lost, the list becomes inaccessible.
  • End Node: The last node points to null, indicating the end of the list.
  • Flexible Insertion/Deletion: Nodes can be added or removed without reorganizing the entire list, unlike arrays.

 Singly-linked list – [Create, Access, Traversal]

The linked list has a head pointer that points to the first node. This head pointer doesn’t store any actual data of the list; it just stores the memory address of the first node.

In the example you provided, the head pointer stores the address 350, which is where the first node (10) is located. So,  head pointer is simply a reference that helps us locate the start of the list. The first node itself has its own data (10 in this case) and a pointer to the next node (address 4900).

Example code:

#include <stdio.h>
#include <stdlib.h>// Define the linked list node structure
struct Node {
int data;
struct Node* next;
};// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}// Function to traverse a linked list
void traverseLinkedList(struct Node* head) {
struct Node* current = head;// Traverse until the end of the linked list
while (current != NULL) {
printf(“%d -> “, current->data);
current = current->next;
}
printf(“NULL\n”);
}

int main() {
// Create linked list nodes
struct Node *head = createNode(1);
struct Node *second = createNode(2);
struct Node *third = createNode(3);

// Link the nodes together
head->next = second;
second->next = third;

// Traverse and print the linked list
printf(“Linked List: “);
traverseLinkedList(head);

return 0;
}

Output:  1 → 2 → 3 → Null.

Key Operations in the singly linked list  

Theoretical understanding is very easy, but To understand the implementation of key operations on a singly linked list, you must understand pointers, arrays, and structures. Insertion, deletion, and traversal are the three key operations in a singly linked list

1. Insertion Operations

At the Beginning: To make the new node the first item, set its next pointer to the current head and then update head to be this new node.

Example: If the list is 20 → 30, and you add 10 at the beginning:

  • 10.next points to 20.
  • The list becomes: 10 → 20 → 30.

Steps:

  • Allocate memory for the new node.
  • Assign the desired value to the data field of the new node.
  • Update the next pointer of the new node to point to the current head of the list.
  • Move the head pointer to the newly created node, making it the first node in the list.

Implementation code

struct node *newNode;

// Allocate memory for the new node
newNode = (struct node*)malloc(sizeof(struct node));

// Assign data to the new node
newNode->data = 10;

// Point the new node to the current head of the list
newNode->next = head;

// Update head to point to the new node
head = newNode;

Important:  The operation newNode->next = head; uses the old value of head, and after head = newNode;, the pointer now refers to the new node.

II. At the End: To add a node at the end, traverse the list to find the last node (where next is Null), then set its next pointer to the new node.

Example: If the list is 10 → 20, and you add 30 at the end:

  • 20.next points to 30
  • 30.next points to Null
  • The list becomes: 10 → 20 → 30

Steps:

  • Allocate memory for a new node
  • Store the data.
  • Traverse till the last node.
  • Change next of the last node to the newly created node
// Create and allocate memory for a new node
struct node *newNode;
newNode = (struct node *)malloc(sizeof(struct node));// Store data in the newly created node and initialize next pointer to NULL
newNode->data = 4;
newNode->next = NULL;// Traverse the list to find the last node
struct node *current = head;
while (current->next != NULL) {
current = current->next;
}// Update the next pointer of the last node to point to the new node
current->next = newNode;

iii. In the Middle: To insert a node in the middle, find the nodes before and after the insertion point. Set the next pointer of the node before to the new node and the new node’s next pointer to the node after.

Example: If the list is 10 → 30 and you add 20 in between:

  • 10.next points to 20.
  • 20.next points to 30.
  • The list becomes: 10 → 20 → 30.

Steps:

  • Allocate memory and store data for the new node.
  • Navigate to the node just before the position where the new node needs to be inserted.
  • Update the next pointers to insert a new node in between existing nodes.
// Create and allocate memory for a new node
struct node *newNode;
newNode = (struct node *)malloc(sizeof(struct node));// Store data in the newly created node
newNode->data = 4;// Traverse the list to the specified position
struct node *current = head;
for (int i = 2; i < position; i++) {
if (current->next != NULL) {
current = current->next;
}
}// Insert the new node at the specified position
newNode->next = current->next;
current->next = newNode;

2. Deletion Operations

Deletion at the Beginning: To delete the first node in the list, we simply need to update the head to point to the second node, and then free the memory of the original head node.

Steps:

  1. Update head to point to the next node.

Code:

head = head->next;

Deletion at the End: To delete a node at the end, we need to traverse the list to find the second-last node and update its next pointer to NULL. Then, we can free the memory of the last node.

Steps:

  1. Traverse to the second-last node in the list.
  2. Update the next pointer of the second-last node to NULL.

Code:

struct node *temp, *current;

// If the list is empty, there’s nothing to delete
if (head == NULL) {
printf(“List is already empty.\n”);
return;
}

// If the list has only one node
if (head->next == NULL) {
free(head);
head = NULL;
return;
}

// Traverse to the second-last node
current = head;
while (current->next->next != NULL) {
current = current->next;
}

// Store the last node in temp
temp = current->next;

// Update the second-last node’s next pointer to NULL
current->next = NULL;

// Free the last node
free(temp);

The while loop helps us find the second-last node to properly disconnect the last node.

Deletion in the Middle

Steps

  1. Traverse to the node just before the one to be deleted.
  2. Store the node to be deleted in a temporary pointer.
  3. Update the next pointer of the current node to skip the node being deleted.
  4. Free the memory of the node to be deleted.

Code:

struct node *temp, *current;

// If the list is empty, there’s nothing to delete
if (head == NULL) {
printf(“List is already empty.\n”);
return;
}

// Traverse to the node just before the one to be deleted
current = head;
for (int i = 1; i < position – 1; i++) {
if (current->next == NULL) {
printf(“Position out of range.\n”);
return;
}
current = current->next;
}

// Store the node to be deleted in temp
temp = current->next;

// Update current’s next to skip the deleted node
current->next = temp->next;

// Free the deleted node
free(temp);

Note: In this example, position starts from 1 (i.e., the head node is at position 1). We traverse to position - 1 to ensure we’re at the correct spot to change pointers safely.

3. Search for an element in a linked list

To search for an element in a linked list using a loop, you can follow these steps:

  1. Set the head node as the current node.
  2. Traverse the list using a loop, continuing until the current node becomes NULL (since the last node’s next pointer is NULL).
  3. During each iteration, compare the key of the current node with the target value. If they match, return true; if no match is found throughout the loop, return false.
// Function to search for a specific value in the linked list
bool searchNode(struct Node** head_ref, int key) {
// Start with the head node as the current node
struct Node* current = *head_ref;// Traverse through the linked list until the end is reached
while (current != NULL) {
// If the current node’s data matches the key, return true
if (current->data == key) {
return true;
}
// Move to the next node
current = current->next;
}// Return false if the key is not found
return false;
}

Time and space complexity in a singly linked list

Here is a table that combines both time and space complexities for the operations on a singly linked list:

Operation Time Complexity Space Complexity
Insert O(1) at head, O(n) at tail or middle O(1)
Delete O(1) at head, O(n) at tail or middle O(1)
Search O(n) O(1)
Traverse O(n) O(1)

The time complexities vary based on the position of insertion or deletion, while the space complexity for these operations is O(1), since no extra space is needed beyond a few pointers.


Note: In a Singly Linked List, each node only has a next pointer, allowing traversal in one direction (forward). This simpler structure makes insertion and deletion more straightforward than in a doubly linked list but limits backward traversal.