Aim

To demonstrate the working of a Singly Linked List (SLL), which includes its creation, traversal , insertion of elements, deletion of elements, and search for elements through visualization.

Theory & Applications

A Singly Linked List (SLL) is a linear data structure consisting of nodes in which each node is accessible through pointer stored in its immediate predecessor. Single linked list is traversed from first node to the last node using pointers in the forward direction only. It is not feasible to randomly access any element in the list. The first node is pointed by head node which contains the address of first node. Initially, head is Null (∅) indicating empty linked list.

In a Singly Linked List, each node contains two components:

Data :

This stores the actual value or information (e.g., an integer, string, object, etc.).

Example: 5, "Hello", {name: "Alice", age: 30}, etc.

Pointer (or Next):

The pointer stores the address of the subsequent node. It is set to NULL (None in Python) for the last node indicating the end of the linked list.

Applications of Singly Linked List:

Resource management in Operating systems

Use-case :

Memory management.

Explanation :

Singly linked lists are used to identify free and allocated memory blocks in heap management. Each memory block contains a pointer to the next block

Application :

Faster insertion and deletion of memory blocks.

Undo Functionality in Applications

Use-case :

Text editors like Microsoft Word, Google Docs.

Explanation :

Each action (e.g., typing a letter) is stored as a node. Operation "undo" traverses back through the actions using the links.

Application :

Enables rollback to previous state.

Web browsers Forward Navigation

Use-case :

Forward Navigation in Web browsers.

Explanation :

While back navigation uses a stack, forward navigation (redo pages) can be managed using a singly linked list.

Application :

Allows forward traversal through visited pages.

Polynomial Arithmetic

Use-case :

Scientific and Engineering computations.

Explanation :

Polynomials can be represented as a linked list where each node holds a coefficient and exponent.

Application :

Enables polynomial addition, subtraction, and multiplication without memory waste.

Real-time Task Scheduling

Use-case :

Embedded systems and OS kernels.

Explanation :

A task queue can be implemented using a singly linked list where each task is a node.

Application :

Easy insertion of new tasks and deletion of completed ones in linear time.

Key Operations On SLL

This section illustrates key operations on a singly linked list, including insertions, deletions and searching of elements across different positions. The operations are demonstrated using an initial linked list with three nodes: value 6 (Position 1), value 3 (Position 2) , and value 12 (Position 3).

Insertion

Insertion in a singly linked list involves creating a new node (say with value 9) and adjusting pointers to place it at the desired position without disrupting the structure of the list.

Insertion at Position 1 i.e. as the first node

Start at the Head pointer → it points to the first node (value 6).
Create a new node (value 9) and have its pointer point to the current first node (value 6).
Change the Head pointer to point to the new node (value 9).
The new node is now the first node in the list.

Result:

Time Complexity:

O(1) – Direct pointer reassignment makes this a constant-time operation.

Insertion at Position 3

Start at the Head pointer → it points to the first node (value 6).
Move to the next node (value 3)..
Create a new node (value 9) and have its pointer point to the node at position 3 (value 12).
Change the pointer of the node at position 2 (value 3) to point to the new node (value 9).
The new node is now correctly inserted at position 3.

Result:

Time Complexity:

O(n) – Requires traversal to the desired position.

Insertion at Position 4 i.e. at the end of the list

Start at the Head pointer → it points to the first node (value 6).
Traverse the list till the end of list i.e. Node with pointer as Null is found. In the given illustrations, it is a node with value 12.
Change the pointer of the node at position 3 (value 12) to point to the new node (value 9).
The new node is now at the end of the list, which is position 4.

Result:

Time Complexity:

O(n) – Entire list traversal is needed to reach the last node.

Deletion

Deletion in a singly linked list involves removing a node from the desired position by adjusting the pointers of the preceding node, ensuring the continuity of the list structure.

Deletion at Position 1 i.e. as the first node

Start at the Head pointer → it points to the first node (value 6).
Delete the node at this position.
Change the Head pointer to point to the next node (value 3).
The node with the value 6 is now disconnected from the list and can be removed.

Result:

Time Complexity:

O(1) – Only the head pointer is changed.

Deletion at Position 2

Start at the Head pointer → it points to the first node (value 6).
Move to the next node (value 3).
Change the link of the previous node (value 6) to skip over the current node (value 3) and point to the next one (value 12).
The node with the value 3 is now disconnected and can be removed.

Result:

Time Complexity:

O(n) – Traversal is needed to reach the node before the one to be deleted.

Deletion at Position 3 i.e. at the end of the list

Start at the Head pointer → it points to the first node (value 6).
Traverse the list till the end of list i.e. Node with pointer as Null is found. In the given illustrations, it is a node with value 12.
Change the link of the previous node (value 3) to point to the address 'NULL'.
The node with the value 12 is now disconnected and can be removed.

Result:

Time Complexity:

O(n) – Requires traversal to the end of the list.

Searching an Element (12 in this case)

Start traversal from the head node (Position 1).
Compare target (12) with node value (6). Not Found → move to the next node using the stored address.
Compare target (12) with node value (3). Not Found → move to the next node using the stored address.
Compare target (12) with node value (12). Found → return position 3.

Result:

Time Complexity:

O(n) - Time taken by the search operation, since the list will be traversed sequentially to reach the desired node (in this case – node 12).

Code

Example programs

C++ Python


  #C++ Code
  
#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *next;

    // this is  the constructor
    Node(int d)
    {
        this->data = d;
        this->next = NULL;
    }
};

void insertAtHead(Node *&head, int data, Node *&tail)
{
    if (head == NULL)
    {
        // this is your first node
        cout << "this is your first node " << endl;
        // new node created
        Node *temp = new Node(data);
        head = temp;
        tail = temp;
    }

    else
    {
        // inserting the node at the starting of the linked list
        cout << "creating the node" << endl;

        // here we are creating an object
        Node *temp = new Node(data);

        cout << "the new node is created " << endl;

        temp->next = head;
        head = temp;
    }
}

// traversing a linked list
void print(Node *head)
{
    // we will traverse the list
    if (head == NULL)
    {
        cout << "the linked list is empty " << endl;
        cout << "please add some elements " << endl;
    }

    else
    {
        Node *temp = head;
        while (temp != NULL)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
}


void insertAtTail(int data,Node*&head,Node*&tail){
    if(tail==NULL){
        // it means that the list is empty
        // new node first
        Node*temp = new Node(data);
        head = temp;
        tail = temp;
    }

    else{
        // creating a new node
        Node* temp = new Node(data);
        tail->next = temp;
        tail = temp;
    }
}


void insert(int data,int pos,Node*&head,Node*&tail){
    if(pos == 1){
        // insertion is at tail
        insertAtHead(head,data,tail);
        return;
    }

    else{
        int cnt = 1;
        Node*temp = head;
        while(cntnext;
            cnt++;
        }

        // we reached that position
        if(temp == tail){
            // insrtion is at tail
            insertAtTail(data,head,tail);
            return;
        }

        else{
            // insertion i sin between the list
            // craete new node 
            Node*new_Node = new Node(data);
            new_Node->next = temp->next;
            temp->next = new_Node;
            cout<<"Node got inserted at the position "<next;
            temp->next = NULL;
            delete temp;
        }
        else{
            Node*curr = head;
            Node*prev = NULL;
            int cnt = 1;
            while(cntnext;
                cnt++;
            }

            if(curr == tail){
                // deleting the tail node
                tail = prev;
                prev->next=NULL;
                delete curr;
            }

            else{
                // deleting the middle node
                prev->next = curr->next;
                curr->next = NULL;
                delete curr;
            }

        }
    }
}


int main()
{
    Node*head = NULL;
    Node*tail = NULL;
    insertAtHead(head,34,tail);
    print(head);
    insertAtHead(head,40,tail);
    print(head);
    insertAtHead(head,50,tail);
    print(head);
    insertAtTail(20,head,tail);
    print(head);
    DeleteNode(2,head,tail);
    print(head);
    DeleteNode(3,head,tail);
    print(head);
    return 0;
}


# Python
 class Node:
    """A class representing a node in a singly linked list."""
    def __init__(self, data):
        self.data = data
        self.next = None


class SinglyLinkedList:
    """A class representing a singly linked list."""
    def __init__(self):
        self.head = None

    def insert_at_start(self, data):
        """Insert a new node at the start of the list."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        """Insert a new node at the end of the list."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def insert_after(self, target, data):
        """Insert a new node after a specific node value."""
        current = self.head
        while current and current.data != target:
            current = current.next
        if current:
            new_node = Node(data)
            new_node.next = current.next
            current.next = new_node
        else:
            print("Target value not found!")

    def delete_at_start(self):
        """Delete the node at the start of the list."""
        if not self.head:
            print("List is empty!")
            return
        self.head = self.head.next

    def delete_at_end(self):
        """Delete the node at the end of the list."""
        if not self.head:
            print("List is empty!")
            return
        if not self.head.next:
            self.head = None
            return
        current = self.head
        while current.next and current.next.next:
            current = current.next
        current.next = None

    def delete_value(self, value):
        """Delete the first node with the given value."""
        if not self.head:
            print("List is empty!")
            return
        if self.head.data == value:
            self.head = self.head.next
            return
        current = self.head
        while current.next and current.next.data != value:
            current = current.next
        if current.next:
            current.next = current.next.next
        else:
            print("Value not found!")

    def search(self, value):
        """Search for a node with the given value."""
        current = self.head
        while current:
            if current.data == value:
                return True
            current = current.next
        return False

    def display(self):
        """Display the linked list."""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("NULL")


# Example usage
if __name__ == "__main__":
    linked_list = SinglyLinkedList()

    # Test insertion
    linked_list.insert_at_start(10)
    linked_list.insert_at_start(20)
    linked_list.insert_at_end(30)
    linked_list.insert_after(10, 25)

    print("List after insertions:")
    linked_list.display()

    # Test deletion
    linked_list.delete_at_start()
    print("List after deleting at start:")
    linked_list.display()

    linked_list.delete_at_end()
    print("List after deleting at end:")
    linked_list.display()

    linked_list.delete_value(25)
    print("List after deleting value 25:")
    linked_list.display()

    # Test search
    print("Searching for 10:", "Found" if linked_list.search(10) else "Not Found")
    print("Searching for 40:", "Found" if linked_list.search(40) else "Not Found")

Practice

This section explains the basic operations - insert, delete, and search - using visual simulations. Follow the given steps for practicing:

Enter comma-separated values (up to maximum 8 values) and click on "Create List" to generate the linked list.
Choose an operation—Insert, Delete, or Search—and provide the necessary input (like value and position).
Click "Run Simulation" to see the animated visuals, preforming the desired operation step- by-step

Singly Linked List Visualization

Result

The virtual lab (VLab) demonstrated a singly linked list with up to eight elements in an interactive format. It enabled users to perform insertion, deletion, and search operations, while visually showing pointer adjustments and list traversal, reinforcing the logic of linked list operations.

Quiz

Instructions

The quiz consists of multiple-choice questions on Singly Linked List.
You will earn 1 point for every correct answer.
There is No negative marking for the wrong answer
Select a particular option and click "Next".
Select "Back" to correct the previous option selected.
Results will be display at the end of the quiz.

Question

📜Summary

References

Team & Tools

Students

Mentors

Ms. Priyanka Sharma
Prof. Sharanjit Kaur

Tools Used

HTML(v5.2), CSS Snapshot 2023, JavaScript (ES 6)
Figma(v124.4.7), Canva

V-Lab@ANDC

SINGLY LINKED LIST

In a Singly Linked List, each node contains two components:

Applications of Singly Linked List:

Insertion

Insertion at Position 1 i.e. as the first node

Result:

Time Complexity:

Insertion at Position 3

Result:

Time Complexity:

Insertion at Position 4 i.e. at the end of the list

Result:

Time Complexity:

Deletion

Deletion at Position 1 i.e. as the first node

Result:

Time Complexity:

Deletion at Position 2

Result:

Time Complexity:

Deletion at Position 3 i.e. at the end of the list

Result:

Time Complexity:

Searching an Element (12 in this case)

Result:

Time Complexity:

This section explains the basic operations - insert, delete, and search - using visual simulations. Follow the given steps for practicing:

Singly Linked List Visualization

Quiz

Instructions

Question

📜Summary

Students

Mentors

Tools Used