Singly Linked List in Data Structure

• A linear collection of data objects is called a singly linked list, or just a linked list.
• With POINTERS, the linear order is provided. Linear-linked lists are a common term used to describe these kinds of lists.
• A node is any element in the list.

There are two fields on each node in the singly linked list in data structure:

1. Information: includes the item that is being kept in the list.
2. Next address: This is the address of the item in the list that comes after it.

The final node of the list has a NULL pointer to indicate that it is the last item.

Singly Linked List Operations:

Types of Singly Linked List in Data Structure Operation are:

1. Insertion Operation.
2. Deletion Operation.

Insertion Operation:

Three scenarios exist for an element to be added to the list:

1. At the start 
2. At the end of the list
3. At a specific location

1. At the Start

• The address of the first node is stored in the head pointer variable, while the address of the next node to be inserted is stored in the temp variable. Sample code is
  • temp->link=head; 
  • head=temp; 

After Insertion:

Logic Code for Insertion of a Node at the Start Location of the List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def insert_at_beginning(self, new_data):
        """Inserts a new node with 'new_data' at the beginning of the linked list.
        Args:
            new_data: The data to be stored in the new node.
        """
        # 1. Allocate memory for the new node
        new_node = Node(new_data)
        # 2. Make next of the new node as the current head
        new_node.next = self.head
        # 3. Update the head of the linked list to the new node
        self.head = new_node

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to insert a new node at the beginning
    void insertAtBeginning(int newData) {
        // 1. Allocate memory for the new node
        Node* newNode = new Node; 
        // 2. Put in the data
        newNode->data = newData;
        // 3. Make next of the new node as the current head
        newNode->next = head;
        // 4. Update the head of the linked list
        head = newNode; 
    }
};

class LinkedList {
    Node head; // head of the linked list
    // Linked list node 
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Function to insert a new node at the beginning
    public void insertAtBeginning(int newData) {
        // 1. Allocate memory for the new node
        Node newNode = new Node(newData);
        // 2. Make next of the new node as the current head
        newNode.next = head;
        // 3. Update the head of the linked list
        head = newNode;
    }
}

#include <stdio.h>
#include <stdlib.h>
// Linked List node
struct Node {
    int data;
    struct Node* next;
};
// Function to insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
    // 1. Allocate memory for the new node
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    // 2. Put in the data
    new_node->data = new_data;
    // 3. Make next of the new node as the current head
    new_node->next = (*head_ref);
    // 4. Move the head to point to the new node
    (*head_ref) = new_node;
}

2. At the end of the list

• The address of the first node is stored in the head pointer variable, while the address of the next node to be inserted is stored in the temp variable. Sample code is

t=head;
while(t->link!=NULL)
{
    t=t->link;
}
t->link=temp;

After Insertion the linked list is

Logic Code for Insertion of a Node at the End of the List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def insert_at_end(self, new_data):
        # 1. Create a new node
        new_node = Node(new_data)
        # 2. If the linked list is empty, make the new node the head
        if self.head is None:
            self.head = new_node
            return
        # 3. Traverse to the last node
        last = self.head
        while last.next:
            last = last.next
        # 4. Change the next of the last node
        last.next = new_node

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to insert a new node at the end
    void insertAtEnd(int newData) {
        // 1. Allocate memory for the new node
        Node* newNode = new Node;
        // 2. Put in the data
        newNode->data = newData;
        // 3. This new node is going to be the last node, so make next of it as NULL
        newNode->next = nullptr;
        // 4. If the Linked List is empty, then make the new node as head
        if (head == nullptr) {
            head = newNode;
            return;
        }
        // 5. Else traverse till the last node
        Node* last = head;
        while (last->next != nullptr) {
            last = last->next;
        }
        // 6. Change the next of last node
        last->next = newNode;
    }
};

class LinkedList {
    Node head; // head of the linked list
    // Linked list node 
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Function to insert a new node at the end
    public void insertAtEnd(int newData) {
        // 1. Allocate the Node & put in the data
        Node newNode = new Node(newData);
        // 2. If the Linked List is empty, then make the new node as head
        if (head == null) {
            head = newNode;
            return;
        }
        // 3. This new node is going to be the last node, so make next of it as null
        newNode.next = null;
        // 4. Else traverse till the last node
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        // 5. Change the next of last node
        last.next = newNode;
    }
}

#include <stdio.h>
#include <stdlib.h>
// Linked List node
struct Node {
    int data;
    struct Node* next;
};
// Function to insert a new node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    // 1. Allocate memory for the new node
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    // 2. Put in the data
    new_node->data = new_data;
    // 3. This new node is going to be the last node, so make next of it as NULL
    new_node->next = NULL;
    // 4. If the Linked List is empty, then make the new node as head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    // 5. Else traverse till the last node
    struct Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    // 6. Change the next of the last node
    last->next = new_node;
}

3. At a specific location

• Insert node at position 3; temp is the location of the new node to be inserted, and head is the pointer variable that carries the address of the first node. The sample code is

c=1;
while(c<pos)
{
   prev=cur;
  cur=cur->link;
  c++;
}
prev->link=temp;
temp->link=cur;

Logic Code for Insertion of a Node at the Specific Location of the List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def insert_at_index(self, new_data, index):
        # 1. Create the new node
        new_node = Node(new_data)
        # 2. Handle case where index is 0 (insert at beginning)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        # 3. Traverse to the node before the desired index
        current = self.head
        count = 0
        while current and count < index - 1:
            current = current.next
            count += 1
        # 4. If the index is out of bounds, return
        if current is None:
            return
        # 5. Set the new node's next to the current node's next
        new_node.next = current.next
        # 6. Set the current node's next to the new node
        current.next = new_node

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to insert a new node at a given position
    void insertAtIndex(int newData, int index) {
        // 1. Allocate memory for the new node
        Node* newNode = new Node;
        // 2. Put in the data
        newNode->data = newData;
        // 3. If the linked list is empty, make the new node as head
        if (index == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }
        // 4. Else traverse till the n-1th node
        Node* temp = head;
        for (int i = 0; i < index - 1 && temp != nullptr; i++) {
            temp = temp->next;
        }
        // 5. If the position is more than the number of nodes
        if (temp == nullptr) {
            return;
        }
        // 6. Adjust the pointers to insert the new node
        newNode->next = temp->next;
        temp->next = newNode;
    }
};

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to insert a new node at a given position
    void insertAtIndex(int newData, int index) {
        // 1. Allocate memory for the new node
        Node* newNode = new Node;
        // 2. Put in the data
        newNode->data = newData;
        // 3. If the linked list is empty, make the new node as head
        if (index == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }
        // 4. Else traverse till the n-1th node
        Node* temp = head;
        for (int i = 0; i < index - 1 && temp != nullptr; i++) {
            temp = temp->next;
        }
        // 5. If the position is more than the number of nodes
        if (temp == nullptr) {
            return;
        }
        // 6. Adjust the pointers to insert the new node
        newNode->next = temp->next;
        temp->next = newNode;
    }
};

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to insert a new node at a given position
    void insertAtIndex(int newData, int index) {
        // 1. Allocate memory for the new node
        Node* newNode = new Node;
        // 2. Put in the data
        newNode->data = newData;
        // 3. If the linked list is empty, make the new node as head
        if (index == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }
        // 4. Else traverse till the n-1th node
        Node* temp = head;
        for (int i = 0; i < index - 1 && temp != nullptr; i++) {
            temp = temp->next;
        }
        // 5. If the position is more than the number of nodes
        if (temp == nullptr) {
            return;
        }
        // 6. Adjust the pointers to insert the new node
        newNode->next = temp->next;
        temp->next = newNode;
    }
};

Deletion Operation

Eliminating a component from the list without compromising the list’s integrity is called deleting the component.

Three scenarios exist for placing an element from the list:

1. Remove the first node from the list.
2. Eliminate the last node in the list.
3. Remove a node from a certain location.

Case 1: Delete a Node at the Start

The address of the first node is contained in the head pointer variable. 

Logic Code for Delete a Node at the Start of the List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def delete_at_beginning(self):
        # 1. Check if the list is empty
        if self.head is None:
            return
        # 2. Update the head to the next node
        self.head = self.head.next 

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to delete the node at the beginning
    void deleteAtBeginning() {
        // 1. If the list is empty, do nothing
        if (head == nullptr) {
            return; 
        }
        // 2. Store the head node
        Node* temp = head;
        // 3. Move the head pointer to the next node
        head = head->next;
        // 4. Free the memory occupied by the deleted node
        delete temp;
    }
};

class LinkedList {
    Node head; // head of the linked list
    // Linked list node 
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Function to delete the node at the beginning
    public void deleteAtBeginning() {
        // 1. If the list is empty, do nothing
        if (head == null) {
            return;
        }
        // 2. Move the head pointer to the next node
        head = head.next;
    }
}

#include <stdio.h>
#include <stdlib.h>
// Linked List node
struct Node {
    int data;
    struct Node* next;
};
// Function to delete a node at the beginning of the linked list.
void deleteAtBeginning(struct Node** head_ref) {
    // 1. If the linked list is empty, return
    if (*head_ref == NULL) {
        return;
    }
    // 2. Store the head node
    struct Node* temp = *head_ref;
    // 3. Move the head pointer to the next node
    *head_ref = (*head_ref)->next;
    // 4. Free the memory of the deleted node
    free(temp); 
}

Case 2: Delete a node at the end of the list

Logic Code for Delete a Node at the End of the List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def delete_at_end(self):
        # 1. If the list is empty, do nothing
        if self.head is None:
            return
        # 2. If the list has only one node, delete the head node and set head to None
        if self.head.next is None:
            self.head = None
            return
        # 3. Traverse to the second-to-last node
        second_last = self.head
        while second_last.next.next:
            second_last = second_last.next
        # 4. Set the next of the second-to-last node to None, effectively deleting the last node
        second_last.next = None

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to delete the node at the end
    void deleteAtEnd() {
        // 1. If the list is empty, do nothing
        if (head == nullptr) {
            return;
        }
        // 2. If the list has only one node, delete the head node
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
            return;
        }
        // 3. Traverse to the second-to-last node
        Node* secondLast = head;
        while (secondLast->next->next != nullptr) {
            secondLast = secondLast->next;
        }
        // 4. Delete the last node
        delete secondLast->next;
        // 5. Set the next of the second-to-last node to nullptr
        secondLast->next = nullptr;
    }
};

class LinkedList {
    Node head; // head of the linked list
    // Linked list node 
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Function to delete the node at the end
    public void deleteAtEnd() {
        // 1. If the list is empty, do nothing
        if (head == null) {
            return;
        }
        // 2. If the list has only one node, delete the head node
        if (head.next == null) {
            head = null;
            return;
        }
        // 3. Traverse to the second-to-last node
        Node secondLast = head;
        while (secondLast.next.next != null) {
            secondLast = secondLast.next;
        }
        // 4. Set the next of the second-to-last node to null
        secondLast.next = null;
    }
}

#include <stdio.h>
#include <stdlib.h>
// Linked List node
struct Node {
    int data;
    struct Node* next;
};
// Function to delete a node at the end of the linked list
void deleteAtEnd(struct Node** head_ref) {
    // 1. If the linked list is empty, return
    if (*head_ref == NULL) {
        return;
    }
    // 2. If the list has only one node, delete the head node
    if ((*head_ref)->next == NULL) {
        free(*head_ref);
        *head_ref = NULL;
        return;
    }
    // 3. Find the second last node
    struct Node* second_last = *head_ref;
    while (second_last->next->next != NULL) {
        second_last = second_last->next;
    }
    // 4. Free the last node
    free(second_last->next);
    // 5. Change the next of the second last node to NULL
    second_last->next = NULL;
}

Case 3: Delete a node at a Specific location

• The pointer variable, which provides the location of the first node, is the deleted node at position 3. The node with value 30 needs to be removed.

Logic Code for Delete a Node at a Specific Location in the List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def delete_at_index(self, index):
        # 1. If the list is empty, do nothing
        if self.head is None:
            return
        # 2. If the index is 0, delete the head node
        if index == 0:
            self.head = self.head.next
            return
        # 3. Traverse to the node before the node to be deleted
        temp = self.head
        for i in range(index - 1):
            if temp is None or temp.next is None:  
                return
            temp = temp.next
        # 4. If the node to be deleted is not found, return
        if temp is None or temp.next is None:
            return
        # 5. Store the node to be deleted
        node_to_delete = temp.next
        # 6. Update the next pointer of the previous node
        temp.next = node_to_delete.next
        # 7. Delete the node
        del node_to_delete

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to delete the node at a given position
    void deleteAtIndex(int index) {
        // 1. If the list is empty, do nothing
        if (head == nullptr) {
            return;
        }
        // 2. If the index is 0, delete the head node
        if (index == 0) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        // 3. Traverse to the node before the node to be deleted
        Node* temp = head;
        for (int i = 0; i < index - 1 && temp != nullptr; i++) {
            temp = temp->next;
        }
        // 4. If the position is more than the number of nodes
        if (temp == nullptr || temp->next == nullptr) {
            return;
        }
        // 5. Store the node to be deleted
        Node* toDelete = temp->next;
        // 6. Update the next pointer of the previous node
        temp->next = toDelete->next;
        // 7. Delete the node
        delete toDelete;
    }
};

class LinkedList {
    Node head; // head of the linked list
    // Linked list node 
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Function to delete the node at a given position
    public void deleteAtIndex(int index) {
        // 1. If the list is empty, do nothing
        if (head == null) {
            return;
        }
        // 2. If the index is 0, delete the head node
        if (index == 0) {
            head = head.next;
            return;
        }
        // 3. Find the node before the node to be deleted
        Node temp = head;
        for (int i = 0; temp != null && i < index - 1; i++) {
            temp = temp.next;
        }
        // 4. If the position is more than the number of nodes
        if (temp == null || temp.next == null) {
            return;
        }
        // 5. Update the next pointer of the previous node
        temp.next = temp.next.next;
    }
}

#include <stdio.h>
#include <stdlib.h>
// Linked List node
struct Node {
    int data;
    struct Node* next;
};
// Function to delete a node at a given position
void deleteAtIndex(struct Node** head_ref, int index) {
    // 1. If the linked list is empty, return
    if (*head_ref == NULL) {
        return;
    }
    // 2. If the index is 0, delete the head node
    if (index == 0) {
        struct Node* temp = *head_ref;
        *head_ref = (*head_ref)->next;
        free(temp);
        return;
    }
    // 3. Find the node before the node to be deleted
    struct Node* temp = *head_ref;
    for (int i = 0; temp != NULL && i < index - 1; i++) {
        temp = temp->next;
    }
    // 4. If the position is more than the number of nodes
    if (temp == NULL || temp->next == NULL) {
        return;
    }
    // 5. Store the node to be deleted
    struct Node* next = temp->next->next;
    // 6. Free memory of the node to be deleted
    free(temp->next); 
    // 7. Update the next pointer of the previous node
    temp->next = next;
}

Program Implementation of a Singly Linked List in Data Structure

class Node:
    def __init__(self, data):
        self.data = data  
        self.next = None  
class LinkedList:
    def __init__(self):
        self.head = None
    def print_list(self):
        # Iterate through the list and print each node's data
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
        print()  # Print a newline after the list
    def insert_at_beginning(self, new_data):
        # Create a new node and make it the head
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
    def insert_at_end(self, new_data):
        # Create a new node
        new_node = Node(new_data)
        # If the list is empty, make the new node the head
        if self.head is None:
            self.head = new_node
            return
        # Traverse to the end of the list
        last = self.head
        while last.next:
            last = last.next
        # Append the new node at the end
        last.next = new_node
    def delete_node(self, key):
        # Handle case where the head node itself holds the key
        if self.head is not None:
            if self.head.data == key:
                self.head = self.head.next
                return
        # Traverse the list, looking for the key to delete
        temp = self.head
        while temp is not None:
            if temp.data == key:
                break
            prev = temp
            temp = temp.next
        # If the key wasn't found, do nothing
        if temp is None:
            return
        # Unlink the node containing the key
        prev.next = temp.next
# Example usage:
llist = LinkedList()
llist.insert_at_end(1)
llist.insert_at_beginning(2)
llist.insert_at_end(3)
llist.print_list()  # Output: 2 1 3
llist.delete_node(1)
llist.print_list()  # Output: 2 3 

#include <iostream>
using namespace std;
// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {} // Constructor
    // Function to print the linked list
    void printList() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
    // Function to insert a node at the beginning
    void insertAtBeginning(int newData) {
        Node* newNode = new Node;
        newNode->data = newData;
        newNode->next = head;
        head = newNode;
    }
    // Function to insert a node at the end
    void insertAtEnd(int newData) {
        Node* newNode = new Node;
        newNode->data = newData;
        newNode->next = nullptr;
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* last = head;
        while (last->next != nullptr) {
            last = last->next;
        }
        last->next = newNode;
    }
    // Function to delete a node with a given key
    void deleteNode(int key) {
        Node* temp = head;
        Node* prev = nullptr;
        // If the head node itself holds the key
        if (temp != nullptr && temp->data == key) {
            head = temp->next;
            delete temp;
            return;
        }
        // Search for the key to be deleted
        while (temp != nullptr && temp->data != key) {
            prev = temp;
            temp = temp->next;
        }
        // If the key was not present in the linked list
        if (temp == nullptr) {
            return;
        }
        // Unlink the node from the linked list
        prev->next = temp->next;
        // Free memory occupied by the deleted node
        delete temp;
    }
};
int main() {
    LinkedList llist;
    llist.insertAtEnd(1);
    llist.insertAtBeginning(2);
    llist.insertAtEnd(3);
    llist.printList();  // Output: 2 1 3
    llist.deleteNode(1);
    llist.printList();  // Output: 2 3
    return 0;
}

class LinkedList {
    Node head; // Head of the linked list
    // Linked list node
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Constructor to initialize the linked list with head as null
    LinkedList() {
        head = null;
    }
    // Function to print the linked list
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
    // Function to insert a new node at the beginning of the linked list
    public void insertAtBeginning(int newData) {
        // Allocate the new node and put in the data
        Node newNode = new Node(newData);
        // Make next of new node as head
        newNode.next = head;
        // Move the head to point to the new node
        head = newNode;
    }
    // Function to insert a new node at the end of the linked list
    public void insertAtEnd(int newData) {
        // Allocate the new node and put in the data
        Node newNode = new Node(newData);
        // If the linked list is empty, then make the new node as head
        if (head == null) {
            head = newNode;
            return;
        }
        // This new node is going to be the last node, so make next of it as null
        newNode.next = null;
        // Else traverse till the last node
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        // Change the next of the last node
        last.next = newNode;
    }
    // Function to delete a node with the given key
    public void deleteNode(int key) {
        // Store head node
        Node temp = head, prev = null;
        // If head node itself holds the key to be deleted
        if (temp != null && temp.data == key) {
            head = temp.next; // Changed head
            return;
        }
        // Search for the key to be deleted, keep track of the
        // previous node as we need to change 'prev->next'
        while (temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }
        // If key was not present in linked list
        if (temp == null)
            return;
        // Unlink the node from linked list
        prev.next = temp.next;
    }
    public static void main(String[] args) {
        LinkedList llist = new LinkedList();
        llist.insertAtEnd(1);
        llist.insertAtBeginning(2);
        llist.insertAtEnd(3);
        llist.printList(); // Output: 2 1 3
        llist.deleteNode(1);
        llist.printList(); // Output: 2 3
    }
}

#include <stdio.h>
#include <stdlib.h>
// Structure for a linked list node
struct Node {
    int data;
    struct Node* next;
};
// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
// Function to insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
    // Allocate memory for the new node
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    // Put in the data
    new_node->data = new_data;
    // Make next of new node as head
    new_node->next = (*head_ref);
    // Move the head to point to the new node
    (*head_ref) = new_node;
}
// Function to insert a new node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    // Allocate memory for the new node
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    // Put in the data
    new_node->data = new_data;
    // This new node is going to be the last node, so make next of it as NULL
    new_node->next = NULL;
    // If the Linked List is empty, then make the new node as head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    // Else traverse till the last node
    struct Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    // Change the next of the last node
    last->next = new_node;
}
// Function to delete a node with a given key
void deleteNode(struct Node** head_ref, int key) {
    // Store head node
    struct Node *temp = *head_ref, *prev;
    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // Changed head
        free(temp); // free old head
        return;
    }
    // Search for the key to be deleted, keep track of the
    // previous node as we need to change 'prev->next'
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    // If key was not present in linked list
    if (temp == NULL)
        return;
    // Unlink the node from linked list
    prev->next = temp->next;
    free(temp); // Free memory
}
int main() {
    struct Node* head = NULL;
    insertAtEnd(&head, 1);
    insertAtBeginning(&head, 2);
    insertAtEnd(&head, 3);
    printList(head); // Output: 2 1 3
    deleteNode(&head, 1);
    printList(head); // Output: 2 3
    return 0;
}

Output:

2 1 3 
2 3

Complexity Analysis of Singly Linked List Operations

Related FAQs:

1. How Do I Traverse a Singly Linked List?

• Traversal involves starting at the head node and following the “next” pointers until you reach the end of the list (indicated by a NULL or None pointer).

2. How Do I Reverse a Singly Linked List?

• Reversing a singly linked list involves iterating through the list and changing the “next” pointers of each node to point to the previous node. As you proceed, you’ll be required to identify the preceding, current, and subsequent nodes.

3. How Do I Find the Middle Element of a Singly Linked List?

• A common technique is to use two pointers: a slow pointer that moves one node at a time and a fast pointer that moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle element.

4. How Do I Detect a Loop in a Singly Linked List?

• Floyd’s Cycle Finding Algorithm (also known as the “tortoise and hare” algorithm) is a popular method for detecting loops. It uses two pointers moving at different speeds; if they meet, there is a loop.

5. What is the Difference Between a Singly Linked List and a Doubly Linked List?

• In a doubly linked list, each node has two pointers: one pointing to the next node and one pointing to the previous node. This allows for traversal in both directions, providing more flexibility than a single linked list.