Topic 2

Singly Linked List

Use class Node — no struct allowed in exam

How It Works

A linear data structure where each Node contains data and a pointer to next node. Traversal is one-direction only (head → NULL).

Two classes needed:
• class Node — holds data and next pointer
• class LinkedList — holds head pointer and all operations

Singly Linked List

head

→

→NULL

🔑

Traversal: while(temp != NULL) — singly specific.

🔑

Insert beginning: O(1). Insert end: O(n) — must traverse.

🔑

Delete end: Need second-to-last → temp->next->next != NULL

🔑

Delete by position: Traverse to pos-1, then temp->next = temp->next->next

complete-singly-linked-list

#include <iostream>
using namespace std;

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

class LinkedList {
private:
    Node* head;

public:
    // Constructor
    LinkedList() {
        head = NULL;
    }

    // Insert at beginning
    void insertBeginning(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = head;
        head = newNode;
    }

    // Insert at specific position
    void insertPosition(int value, int pos) {
        Node* newNode = new Node();
        newNode->data = value;

        if (pos == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }

        Node* temp = head;
        for (int i = 0; temp != NULL && i < pos - 1; i++) {
            temp = temp->next;
        }

        if (temp == NULL) {
            cout << "Position out of bounds" << endl;
            return;
        }

        newNode->next = temp->next;
        temp->next = newNode;
    }

    // Insert at end
    void insertEnd(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = NULL;

        if (head == NULL) {
            head = newNode;
            return;
        }

        Node* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // Delete from beginning
    void deleteBeginning() {
        if (head == NULL) {
            cout << "List empty" << endl;
            return;
        }
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    // Delete from end
    void deleteEnd() {
        if (head == NULL) {
            cout << "List empty" << endl;
            return;
        }
        if (head->next == NULL) {
            delete head;
            head = NULL;
            return;
        }
        Node* temp = head;
        while (temp->next->next != NULL) {
            temp = temp->next;
        }
        delete temp->next;
        temp->next = NULL;
    }

    // Delete from specific position
    void deleteFromSpecificPosition(int position) {
        if (head == NULL) {
            cout << "List is empty." << endl;
            return;
        }

        Node* temp = head;

        if (position == 0) {
            head = temp->next;
            delete temp;
            return;
        }

        for (int i = 0; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }

        if (temp == NULL || temp->next == NULL) {
            cout << "Position out of bounds." << endl;
            return;
        }

        Node* next = temp->next->next;
        delete temp->next;
        temp->next = next;
    }

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

int main() {
    LinkedList list;

    list.insertBeginning(3);
    list.insertBeginning(1);
    list.insertBeginning(7);
    list.insertBeginning(2);
    list.display();                // 2 7 1 3

    list.insertPosition(5, 2);
    list.display();                // 2 7 5 1 3

    list.insertEnd(10);
    list.display();                // 2 7 5 1 3 10

    list.deleteBeginning();
    list.display();                // 7 5 1 3 10

    list.deleteEnd();
    list.display();                // 7 5 1 3

    return 0;
}