UNIT V: LINKED LIST — Complete Exam Notes

Course: Data Structures and Algorithms Duration: 5 Hours Language used in examples: Java Document Type: Exam-Ready Theory + Programs + Q/A + Lab Report

TABLE OF CONTENTS

  1. Introduction
  2. Linked List — Advantages and Disadvantages
  3. Key Terms (Data Field, Linked Field)
  4. Representation of a Linear Linked List
  5. Operations on Linked List
  6. Types of Linked List
  7. Create Single Linked List
  8. Insertion in Single Linked List at Specific Position
  9. Deletion in Single Linked List at Specific Position
  10. Application: Addition of Two Polynomials
  11. Chapter Summary
  12. Most Important Exam Questions with Answers
  13. Lab Report Question (Practical)

5.1 INTRODUCTION

A Linked List is a linear data structure in which elements (called nodes) are stored at non-contiguous memory locations and connected together using pointers (references). Unlike arrays, the size of a linked list is dynamic — it can grow or shrink during program execution.

Each node contains two parts:

  1. Data part — stores the actual value/information.
  2. Link part (next reference) — stores the address/reference of the next node in the list.

The first node is pointed to by a special reference called HEAD. The last node's link part is set to null, marking the end of the list.

Logical view of a Singly Linked List:

HEAD → [ 10 | • ] → [ 20 | • ] → [ 30 | • ] → [ 40 | null ]

Linked lists are widely used because they overcome the fixed-size and shifting limitations of arrays.

5.2 LINKED LIST — ADVANTAGES AND DISADVANTAGES

✅ Advantages

# Advantage Explanation
1 Dynamic size Memory is allocated at runtime. The list grows or shrinks as needed.
2 Efficient insertion/deletion No shifting required. Insertion/deletion takes O(1) time if the position is known.
3 No memory wastage Memory is allocated per node, only when needed.
4 Easy implementation of other structures Stacks, Queues, Graphs, Trees, Hash tables can be built using linked lists.
5 No need for contiguous memory Useful when large contiguous blocks are unavailable.

❌ Disadvantages

# Disadvantage Explanation
1 Extra memory for pointers Every node stores a reference, increasing memory overhead.
2 No random access Accessing the n-th element requires traversal from head — O(n).
3 Sequential traversal only Cannot jump directly to a position like in arrays.
4 Reverse traversal is hard Especially in singly linked lists.
5 More complex code Pointer/reference manipulation is error-prone.

5.3 KEY TERMS

🔹 Data Field

The portion of a node that holds the actual information (the value being stored). For example, in a node storing 45, the data field is 45.

🔹 Link Field (Pointer / Next Field)

The portion of a node that holds the reference (address) of the next node. It "links" one node to the next, forming the chain.

Node structure in Java:

class Node {
    int data;       // Data field
    Node next;      // Link field — reference to the next node

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Other important terms

Term Meaning
HEAD Reference variable that points to the first node of the list.
NULL link The link field of the last node, indicating end of list.
Traversal Visiting each node of the list one by one.
Empty list A list where HEAD == null.

5.4 REPRESENTATION OF LINEAR LINKED LIST

A linear linked list (singly linked list) is represented as a sequence of nodes where each node points to the next node, and the last node points to null.

   ┌──────┬──────┐    ┌──────┬──────┐    ┌──────┬──────┐
HEAD →│ 10  │  •──┼──→ │ 20  │  •──┼──→ │ 30  │ null │
   └──────┴──────┘    └──────┴──────┘    └──────┴──────┘
       Node1               Node2              Node3

Properties of a Linear Linked List

  • Has exactly one HEAD node.
  • Each node has one link field.
  • The last node points to null.
  • Traversal is only in one direction (forward).

Java Representation

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; this.next = null; }
}

class LinearLinkedList {
    Node head;          // entry point
    LinearLinkedList() { head = null; }
}

5.5 OPERATIONS ON LINKED LIST

The fundamental operations that can be performed on a linked list are listed below.

1️⃣ Creation

Creating an empty list (head = null) and then inserting nodes one by one.

Algorithm CREATE_LIST

2. Repeat until user wants to stop:
      a. Create a new node NEW
      b. Input data into NEW
      c. NEW.next = NULL
      d. If HEAD = NULL
            HEAD = NEW
         Else
            Traverse to last node
            LAST.next = NEW
3. End

2️⃣ Insertion

Adding a new node into the list. It can be done in three ways:

  • Insertion at the beginning
  • Insertion at the end
  • Insertion at a specific position

A. Insertion at Beginning

    Algorithm INSERT_BEGIN(ITEM)

    1. Create a new node NEW
    2. NEW.data = ITEM
    3. NEW.next = HEAD
    4. HEAD = NEW
    5. End

B. Insertion at End

Algorithm INSERT_END(ITEM)

    1. Create a new node NEW
    2. NEW.data = ITEM
    3. NEW.next = NULL
    4. If HEAD = NULL
          HEAD = NEW
          Stop
    5. TEMP = HEAD
    6. While TEMP.next ≠ NULL
          TEMP = TEMP.next
    7. TEMP.next = NEW
    8. End

C. Insertion at Specific Position

Algorithm INSERT_POSITION(ITEM, POS)

    1. Create a new node NEW
    2. NEW.data = ITEM
    3. If POS = 1
          NEW.next = HEAD
          HEAD = NEW
          Stop
    4. TEMP = HEAD
    5. Repeat POS-2 times
          TEMP = TEMP.next
    6. NEW.next = TEMP.next
    7. TEMP.next = NEW
    8. End

3️⃣ Deletion

Removing a node from the list:

  • Deletion from the beginning
  • Deletion from the end
  • Deletion from a specific position
  • Deletion by value

A. Deletion from Beginning

    Algorithm DELETE_BEGIN

    1. If HEAD = NULL
          Display "List Empty"
          Stop
    2. TEMP = HEAD
    3. HEAD = HEAD.next
    4. Delete TEMP
    5. End

B. Deletion from End

    Algorithm DELETE_END

    1. If HEAD = NULL
          Display "List Empty"
          Stop
    2. If HEAD.next = NULL
          Delete HEAD
          HEAD = NULL
          Stop
    3. TEMP = HEAD
    4. While TEMP.next.next ≠ NULL
          TEMP = TEMP.next
    5. Delete TEMP.next
    6. TEMP.next = NULL
    7. End

C. Deletion at Specific Position

    Algorithm DELETE_POSITION(POS)

    1. If HEAD = NULL
          Display "List Empty"
          Stop
    2. If POS = 1
          TEMP = HEAD
          HEAD = HEAD.next
          Delete TEMP
          Stop
    3. TEMP = HEAD
    4. Repeat POS-2 times
          TEMP = TEMP.next
    5. PTR = TEMP.next
    6. TEMP.next = PTR.next
    7. Delete PTR
    8. End

D. Deletion by Value

    Algorithm DELETE_VALUE(ITEM)

    1. If HEAD = NULL
          Display "List Empty"
          Stop
    2. If HEAD.data = ITEM
          TEMP = HEAD
          HEAD = HEAD.next
          Delete TEMP
          Stop
    3. TEMP = HEAD
    4. While TEMP.next ≠ NULL AND TEMP.next.data ≠ ITEM
          TEMP = TEMP.next
    5. If TEMP.next = NULL
          Display "Item Not Found"
          Stop
    6. PTR = TEMP.next
    7. TEMP.next = PTR.next
    8. Delete PTR
    9. End

4️⃣ Traversing

Visiting each node of the list to perform some operation (e.g., printing).

Algorithm: TRAVERSE

    1. If HEAD = NULL
          Display "List Empty"
          Stop
    2. TEMP = HEAD
    3. While TEMP ≠ NULL
          Display TEMP.data
          TEMP = TEMP.next
    4. End

5️⃣ Searching

Finding whether a particular element exists in the list and returning its position.

Algorithm: SEARCH(ITEM)

    1. TEMP = HEAD
    2. POS = 1
    3. While TEMP ≠ NULL
          If TEMP.data = ITEM
                Display "Found at Position", POS
                Stop
          TEMP = TEMP.next
          POS = POS + 1
    4. Display "Item Not Found"
    5. End

6️⃣ Concatenation

Joining/appending one linked list to the end of another to form a single combined list.

Algorithm: CONCATENATE(LIST1, LIST2)

    1. If LIST1 = NULL
          LIST1 = LIST2
          Stop
    2. TEMP = LIST1
    3. While TEMP.next ≠ NULL
          TEMP = TEMP.next
    4. TEMP.next = LIST2
    5. End

7️⃣ Display

Printing all the elements of the list in sequence.

Algorithm: DISPLAY

```text
1. If HEAD = NULL
      Display "List Empty"
      Stop
2. TEMP = HEAD
3. While TEMP ≠ NULL
      Print TEMP.data
      TEMP = TEMP.next
4. End

---

### 🔧 Complete Java Implementation — All Operations

```java
class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; this.next = null; }
}

class LinkedListOps {
    Node head;

    // 1. CREATION + INSERTION AT END
    public void insertAtEnd(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) temp = temp.next;
        temp.next = newNode;
    }

    // 2. INSERTION AT BEGINNING
    public void insertAtBeginning(int value) {
        Node newNode = new Node(value);
        newNode.next = head;
        head = newNode;
    }

    // 3. INSERTION AT SPECIFIC POSITION (1-based)
    public void insertAtPosition(int value, int pos) {
        if (pos < 1) { System.out.println("Invalid position"); return; }
        if (pos == 1) { insertAtBeginning(value); return; }

        Node newNode = new Node(value);
        Node temp = head;
        for (int i = 1; i < pos - 1 && temp != null; i++) temp = temp.next;
        if (temp == null) { System.out.println("Position out of range"); return; }
        newNode.next = temp.next;
        temp.next = newNode;
    }

    // 4. DELETION FROM SPECIFIC POSITION
    public void deleteAtPosition(int pos) {
        if (head == null) { System.out.println("List is empty"); return; }
        if (pos == 1) { head = head.next; return; }

        Node temp = head;
        for (int i = 1; i < pos - 1 && temp != null; i++) temp = temp.next;
        if (temp == null || temp.next == null) {
            System.out.println("Position out of range"); return;
        }
        temp.next = temp.next.next;
    }

    // 5. TRAVERSING / DISPLAY
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " → ");
            temp = temp.next;
        }
        System.out.println("null");
    }

    // 6. SEARCHING
    public int search(int key) {
        Node temp = head;
        int pos = 1;
        while (temp != null) {
            if (temp.data == key) return pos;
            temp = temp.next;
            pos++;
        }
        return -1;     // not found
    }

    // 7. CONCATENATION
    public void concatenate(LinkedListOps second) {
        if (head == null) { head = second.head; return; }
        Node temp = head;
        while (temp.next != null) temp = temp.next;
        temp.next = second.head;
    }

    public static void main(String[] args) {
        LinkedListOps list = new LinkedListOps();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtBeginning(5);
        list.insertAtPosition(15, 3);
        list.display();                       // 5 → 10 → 15 → 20 → 30 → null
        System.out.println("Search 20 at pos: " + list.search(20));
        list.deleteAtPosition(2);
        list.display();                       // 5 → 15 → 20 → 30 → null
    }
}

5.6 TYPES OF LINKED LIST

There are four major types of linked lists:

(a) Singly Linked List (SLL)

Each node has one link pointing to the next node only. Traversal is one-directional. Last node points to null.

Characteristics

  • Each node contains one pointer (next).
  • Traversal is unidirectional (forward only).
  • Last node points to null.
  • Requires less memory compared to other linked lists.
HEAD → [10|•] → [20|•] → [30|null]

Advantages

  • Simple implementation.
  • Efficient memory usage.
  • Easy insertion and deletion at the beginning.

Disadvantages

  • Cannot traverse backward.
  • Searching for previous nodes is difficult.

Applications

  • Implementing stacks.
  • Implementing queues.
  • Dynamic memory allocation.

(b) Doubly Linked List (DLL)

Each node has two links — prev (previous node) and next (next node). Traversal is bidirectional.

null ← [•|10|•] ⇄ [•|20|•] ⇄ [•|30|•] → null

Characteristics

  • Each node contains two pointers.
  • Supports bidirectional traversal.
  • Easier insertion and deletion operations.

Java Node:

class DNode {
    int data;
    DNode prev, next;
    DNode(int data) { this.data = data; }
}

Advantages

  • Can traverse in both directions.
  • Deletion is more efficient.
  • Easier implementation of navigation systems.

Disadvantages

  • Requires extra memory for the prev pointer.
  • More complex implementation.

Applications

  • Browser forward/backward navigation.
  • Undo and redo operations.
  • Music and video playlists.

(c) Circular Linked List (CLL)

A singly linked list where the last node's next points back to the first node (instead of null), forming a circle.

Characteristics

  • No node contains null in the next field.
  • Traversal can start from any node.
  • Suitable for cyclic processes.
HEAD → [10|•] → [20|•] → [30|•] ─┐
        ↑─────────────────────────┘

Advantages

  • Continuous traversal is possible.
  • Efficient for round-robin scheduling.
  • No need to maintain a separate tail node.

Disadvantages

  • More difficult to detect the end of the list.
  • Infinite loops may occur if not handled properly.

Applications

  • CPU scheduling.
  • Multiplayer games.
  • Circular queues.
  • Round-robin task scheduling.

(d) Circular Doubly Linked List (CDLL)

A doubly linked list in which the last node's next points to the first node, and the first node's prev points to the last node — forming a circle in both directions.

In this structure:
  • The last node's next points to the first node.
  • The first node's prev points to the last node.
  • Traversal is possible in both forward and backward directions.

Characteristics

  • Contains both prev and next pointers.
  • Forms a complete circular structure.
  • Supports bidirectional traversal.

Representation

        ┌─────────────────────────────┐
        │                             ▼
[•|10|•] ⇄ [•|20|•] ⇄ [•|30|•]
   ▲                             │
   └─────────────────────────────┘

Detailed Structure

        prev ←───────────────┐
                             │
HEAD → [•|10|•] ⇄ [•|20|•] ⇄ [•|30|•]
  ▲                          │
  │                          ▼
  └──────────── next ────────┘

Advantages

  • Traversal in both directions.
  • No NULL pointers.
  • Efficient insertion and deletion from both ends.
  • Suitable for cyclic navigation.

Disadvantages

  • Uses more memory.
  • More complex implementation.
  • Pointer management is difficult.

Applications

  • Image viewers (Next/Previous image).
  • Music players with repeat mode.
  • Browser tab navigation.
  • Operating system process scheduling.
  • Game development loops.

📊 Comparison Table

Feature Singly LL Doubly LL Circular LL Circular Doubly LL
Links per node 1 2 1 2
Traversal direction One-way Two-way One-way (loops) Two-way (loops)
Last node points to null null HEAD HEAD
First node prev points to — null — Last node
Memory used Least More Least More
Use cases Simple lists, stacks, queues Browsers, music players Round-robin scheduling Advanced caching, MRU lists

5.7 CREATE A SINGLE LINKED LIST

Steps:

  1. Define the Node class with a data field and a next reference.
  2. Create an empty list by setting head = null.
  3. Read the number of nodes n from the user.
  4. For each of the n values, create a new node and link it to the end of the list.
  5. Mark the last node's next as null.

Java Program

import java.util.Scanner;

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; this.next = null; }
}

public class CreateSLL {
    Node head;

    public void create(int n, Scanner sc) {
        if (n <= 0) return;
        head = new Node(sc.nextInt());           // first node
        Node tail = head;
        for (int i = 1; i < n; i++) {
            tail.next = new Node(sc.nextInt());  // link new node at the end
            tail = tail.next;
        }
    }

    public void display() {
        Node t = head;
        while (t != null) { System.out.print(t.data + " → "); t = t.next; }
        System.out.println("null");
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        CreateSLL list = new CreateSLL();
        System.out.print("How many nodes? ");
        int n = sc.nextInt();
        System.out.println("Enter " + n + " values:");
        list.create(n, sc);
        System.out.print("Linked List: ");
        list.display();
    }
}

Sample Run:

How many nodes? 4
Enter 4 values:
10 20 30 40
Linked List: 10 → 20 → 30 → 40 → null

5.8 INSERTION IN SINGLE LINKED LIST AT SPECIFIC POSITION

Algorithm: Insert a node with value X at position P (1-based).

Step 1: Create a new node NEW with data = X
Step 2: If P == 1
            NEW.next = HEAD
            HEAD = NEW
            return
Step 3: Set temp = HEAD, i = 1
Step 4: While i < P-1 and temp != null
            temp = temp.next
            i = i + 1
Step 5: If temp == null
            print "Invalid position"
            return
Step 6: NEW.next = temp.next
        temp.next = NEW
Step 7: Stop

Java Program

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class InsertAtPosition {
    Node head;

    public void insertAtPosition(int value, int pos) {
        Node newNode = new Node(value);

        // Case 1: insert at the head
        if (pos == 1) {
            newNode.next = head;
            head = newNode;
            return;
        }

        // Case 2: traverse to position pos-1
        Node temp = head;
        for (int i = 1; i < pos - 1 && temp != null; i++) temp = temp.next;

        if (temp == null) {
            System.out.println("Position out of range");
            return;
        }

        newNode.next = temp.next;
        temp.next = newNode;
    }

    public void display() {
        Node t = head;
        while (t != null) { System.out.print(t.data + " → "); t = t.next; }
        System.out.println("null");
    }

    public static void main(String[] args) {
        InsertAtPosition list = new InsertAtPosition();
        list.insertAtPosition(10, 1);   // 10
        list.insertAtPosition(20, 2);   // 10 20
        list.insertAtPosition(30, 3);   // 10 20 30
        list.insertAtPosition(15, 2);   // 10 15 20 30
        list.display();                  // 10 → 15 → 20 → 30 → null
    }
}

Visual Walkthrough — Insert 15 at position 2

Before:   HEAD → [10|•] → [20|•] → [30|null]
                  pos1     pos2     pos3

Step 1: Create new node [15|•]
Step 2: temp moves to position pos-1 = 1, so temp points to node [10]
Step 3: newNode.next = temp.next       (i.e. newNode → [20])
Step 4: temp.next = newNode            (i.e. [10] → newNode)

After:    HEAD → [10|•] → [15|•] → [20|•] → [30|null]

5.9 DELETION FROM SINGLE LINKED LIST AT SPECIFIC POSITION

Algorithm: Delete the node at position P (1-based).

Step 1: If HEAD == null  →  print "List Empty";  return
Step 2: If P == 1
            HEAD = HEAD.next
            return
Step 3: Set temp = HEAD, i = 1
Step 4: While i < P-1 and temp != null
            temp = temp.next
            i = i + 1
Step 5: If temp == null OR temp.next == null
            print "Invalid position"
            return
Step 6: temp.next = temp.next.next      // bypass the node
Step 7: Stop

Java Program

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class DeleteAtPosition {
    Node head;

    public void insertAtEnd(int v) {
        Node n = new Node(v);
        if (head == null) { head = n; return; }
        Node t = head;
        while (t.next != null) t = t.next;
        t.next = n;
    }

    public void deleteAtPosition(int pos) {
        if (head == null) { System.out.println("List is empty"); return; }

        // Case 1: delete the head
        if (pos == 1) {
            head = head.next;
            return;
        }

        // Case 2: locate position pos-1
        Node temp = head;
        for (int i = 1; i < pos - 1 && temp != null; i++) temp = temp.next;

        if (temp == null || temp.next == null) {
            System.out.println("Position out of range");
            return;
        }

        temp.next = temp.next.next;     // bypass the node to delete
    }

    public void display() {
        Node t = head;
        while (t != null) { System.out.print(t.data + " → "); t = t.next; }
        System.out.println("null");
    }

    public static void main(String[] args) {
        DeleteAtPosition list = new DeleteAtPosition();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);
        list.display();                  // 10 → 20 → 30 → 40 → null
        list.deleteAtPosition(3);
        list.display();                  // 10 → 20 → 40 → null
        list.deleteAtPosition(1);
        list.display();                  // 20 → 40 → null
    }
}

Visual Walkthrough — Delete node at position 3

Before:   HEAD → [10|•] → [20|•] → [30|•] → [40|null]
                  pos1     pos2     pos3     pos4

Step 1: temp moves to pos-1 = 2, so temp points to [20]
Step 2: temp.next = temp.next.next     // [20].next now points to [40]

After:    HEAD → [10|•] → [20|•] → [40|null]

5.10 APPLICATION: ADDITION OF TWO POLYNOMIALS

A polynomial like P(x) = 5x³ + 4x² + 2 can be represented using a linked list where each node stores one term consisting of:

  • coefficient (coeff)
  • exponent (exp)
  • next reference

Why use a Linked List for Polynomials?

  • Polynomials can have any number of terms — array size is unknown.
  • Terms with zero coefficients can simply be omitted, saving memory.
  • Insertion and addition of polynomials becomes straightforward.

Representation

P1(x) = 5x³ + 4x² + 2
HEAD1 → [5,3] → [4,2] → [2,0] → null

P2(x) = 3x³ + 2x + 1
HEAD2 → [3,3] → [2,1] → [1,0] → null

Result = 8x³ + 4x² + 2x + 3
HEAD  → [8,3] → [4,2] → [2,1] → [3,0] → null

Algorithm — Add two Polynomials

1. Initialize pointers p1 = HEAD1, p2 = HEAD2.
2. While p1 != null AND p2 != null:
       If p1.exp == p2.exp:
           append node (p1.coeff + p2.coeff, p1.exp) to result
           move p1 and p2 forward
       Else if p1.exp > p2.exp:
           append node (p1.coeff, p1.exp) to result
           move p1 forward
       Else:
           append node (p2.coeff, p2.exp) to result
           move p2 forward
3. Append remaining nodes of p1 or p2 (whichever is non-null) to result.
4. Return result.

Java Program

class Term {
    int coeff, exp;
    Term next;
    Term(int c, int e) { coeff = c; exp = e; next = null; }
}

public class PolynomialAddition {

    // Insert a term at the end of the polynomial
    static Term insert(Term head, int c, int e) {
        if (c == 0) return head;                // skip zero coefficient
        Term node = new Term(c, e);
        if (head == null) return node;
        Term t = head;
        while (t.next != null) t = t.next;
        t.next = node;
        return head;
    }

    // Add two polynomials
    static Term addPoly(Term p1, Term p2) {
        Term result = null;
        while (p1 != null && p2 != null) {
            if (p1.exp == p2.exp) {
                result = insert(result, p1.coeff + p2.coeff, p1.exp);
                p1 = p1.next; p2 = p2.next;
            } else if (p1.exp > p2.exp) {
                result = insert(result, p1.coeff, p1.exp);
                p1 = p1.next;
            } else {
                result = insert(result, p2.coeff, p2.exp);
                p2 = p2.next;
            }
        }
        while (p1 != null) { result = insert(result, p1.coeff, p1.exp); p1 = p1.next; }
        while (p2 != null) { result = insert(result, p2.coeff, p2.exp); p2 = p2.next; }
        return result;
    }

    // Display polynomial
    static void display(Term head) {
        if (head == null) { System.out.println("0"); return; }
        Term t = head;
        while (t != null) {
            System.out.print(t.coeff + "x^" + t.exp);
            if (t.next != null) System.out.print(" + ");
            t = t.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // P1 = 5x^3 + 4x^2 + 2
        Term p1 = null;
        p1 = insert(p1, 5, 3);
        p1 = insert(p1, 4, 2);
        p1 = insert(p1, 2, 0);

        // P2 = 3x^3 + 2x + 1
        Term p2 = null;
        p2 = insert(p2, 3, 3);
        p2 = insert(p2, 2, 1);
        p2 = insert(p2, 1, 0);

        System.out.print("P1(x) = "); display(p1);
        System.out.print("P2(x) = "); display(p2);

        Term sum = addPoly(p1, p2);
        System.out.print("Sum   = "); display(sum);
    }
}

Sample Output:

P1(x) = 5x^3 + 4x^2 + 2x^0
P2(x) = 3x^3 + 2x^1 + 1x^0
Sum   = 8x^3 + 4x^2 + 2x^1 + 3x^0

5.11 TIME COMPLEXITY SUMMARY

Operation Singly LL Doubly LL Array
Access by index O(n) O(n) O(1)
Search O(n) O(n) O(n)
Insert at beginning O(1) O(1) O(n)
Insert at end (with tail) O(1) O(1) O(1) amortized
Insert at end (no tail) O(n) O(n) O(1)
Insert at position O(n) O(n) O(n)
Delete at beginning O(1) O(1) O(n)
Delete at end O(n) O(1) O(1)
Delete at position O(n) O(n) O(n)

📚 CHAPTER SUMMARY

A Linked List is a dynamic, linear data structure made up of nodes, where each node contains a data field and a link field that holds the reference to the next node. The first node is identified by the HEAD reference, and the last node's link is null.

Linked lists overcome the major drawbacks of arrays — fixed size and costly insertions/deletions — by allowing dynamic memory allocation and O(1) insertion/deletion when the position is known. However, they require extra memory for pointers and offer only sequential access, making random access slow.

There are four main types of linked lists: Singly Linked List (one-direction links), Doubly Linked List (two-direction links with prev and next), Circular Linked List (last node loops back to first), and Circular Doubly Linked List (combines the features of doubly and circular). Each has its own use cases — from simple stacks/queues to browser history and round-robin scheduling.

The core operations on linked lists are creation, insertion, deletion, traversing, searching, concatenation, and display. Insertion and deletion can occur at the beginning, end, or any specific position, with careful handling of the HEAD pointer and link reassignment to avoid losing nodes.

A common practical application of linked lists is the addition of two polynomials, where each term (coefficient, exponent) is stored as a node. Polynomials are added by comparing exponents and either adding coefficients (equal exponents) or appending the term with the larger exponent. This naturally handles polynomials of arbitrary size and skips zero-coefficient terms, demonstrating the real-world power of linked lists.

In short, Linked Lists trade random access for flexibility — and they are the foundation for many higher-level data structures such as stacks, queues, graphs, and hash tables.

🎯 MOST IMPORTANT EXAM QUESTIONS WITH ANSWERS

Q1. What is a Linked List? How is it different from an Array?

Answer: A Linked List is a linear, dynamic data structure consisting of nodes where each node stores data and a reference to the next node. Memory is allocated at runtime, and nodes need not be contiguous.

Feature Array Linked List
Size Fixed at creation Dynamic
Memory Contiguous Non-contiguous
Access Random — O(1) Sequential — O(n)
Insertion/Deletion Costly — O(n) Cheap — O(1) (if position known)
Memory overhead None Extra reference per node
Memory wastage Possible (unused slots) None

Q2. State the advantages and disadvantages of Linked List.

Answer:

Advantages:

  1. Dynamic size — grows or shrinks at runtime.
  2. Efficient insertion and deletion (no shifting required).
  3. No memory wastage — memory allocated per node.
  4. Used to implement higher-level structures (stack, queue, graph).
  5. No need for contiguous memory blocks.

Disadvantages:

  1. Extra memory used by pointer/reference fields.
  2. No random/direct access — traversal is sequential.
  3. Reverse traversal is difficult in singly linked lists.
  4. Slightly complex to implement compared to arrays.
  5. Cache performance is poorer than arrays (nodes are scattered).

Q3. Explain the different types of Linked Lists with diagrams.

Answer:

1. Singly Linked List (SLL): Each node has one link pointing to the next; last node points to null.

HEAD → [10|•] → [20|•] → [30|null]

2. Doubly Linked List (DLL): Each node has two links — prev and next.

null ← [•|10|•] ⇄ [•|20|•] ⇄ [•|30|•] → null

3. Circular Linked List (CLL): Last node points back to the first node.

HEAD → [10|•] → [20|•] → [30|•] ┐
        ↑─────────────────────────┘

4. Circular Doubly Linked List (CDLL): Combines DLL and CLL — bidirectional and circular.

Q4. Write an algorithm to insert a node at a specific position in a Singly Linked List.

Answer:

INSERT_AT_POSITION(HEAD, X, P)
1.  Create newNode with data = X
2.  If P == 1 then
        newNode.next = HEAD
        HEAD = newNode
        return
3.  temp = HEAD, i = 1
4.  While i < P-1 and temp != null do
        temp = temp.next
        i = i + 1
5.  If temp == null then
        print "Position invalid"; return
6.  newNode.next = temp.next
7.  temp.next = newNode
8.  Stop

Q5. Write an algorithm to delete a node from a specific position in a Singly Linked List.

Answer:

DELETE_AT_POSITION(HEAD, P)
1.  If HEAD == null then  print "List Empty"; return
2.  If P == 1 then
        HEAD = HEAD.next
        return
3.  temp = HEAD, i = 1
4.  While i < P-1 and temp != null do
        temp = temp.next
        i = i + 1
5.  If temp == null or temp.next == null then
        print "Invalid position"; return
6.  temp.next = temp.next.next
7.  Stop

Q6. Write a Java program to create a Singly Linked List and display its contents.

Answer:

class Node {
    int data; Node next;
    Node(int d) { data = d; next = null; }
}

public class SLL {
    Node head;

    public void insertAtEnd(int v) {
        Node n = new Node(v);
        if (head == null) { head = n; return; }
        Node t = head;
        while (t.next != null) t = t.next;
        t.next = n;
    }

    public void display() {
        Node t = head;
        while (t != null) { System.out.print(t.data + " → "); t = t.next; }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SLL list = new SLL();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.display();   // 10 → 20 → 30 → null
    }
}

Q7. How are polynomials represented using a Linked List? Write a Java program to add two polynomials.

Answer: Each term (coefficient, exponent) is stored in one node. Adding compares exponents:

  • Equal exponent → add coefficients
  • Otherwise → take the larger-exponent term

(Refer to Section 5.10 above for the complete Java program.)

Q8. Differentiate Singly, Doubly, and Circular Linked Lists.

Answer:

Feature Singly LL Doubly LL Circular LL
Links per node 1 2 1
Direction One-way Two-way One-way (loops)
Last node points to null null HEAD
Memory used Least Most Least
Reverse traversal Difficult Easy Possible (loops back)

Q9. What is concatenation of two linked lists? Write its algorithm.

Answer: Concatenation joins the second linked list to the end of the first.

CONCATENATE(L1, L2)
1.  If L1.HEAD == null then L1.HEAD = L2.HEAD;  return
2.  temp = L1.HEAD
3.  While temp.next != null do
        temp = temp.next
4.  temp.next = L2.HEAD
5.  Stop

Q10. What is a Circular Linked List? Mention its applications.

Answer: A Circular Linked List is a linked list in which the last node's next points back to the first node, forming a closed loop. There is no null at the end.

Applications:

  • Round-robin CPU scheduling in operating systems
  • Multiplayer turn-based games (player rotation)
  • Music/video playlists that loop continuously
  • Implementation of circular buffers
  • Multi-tasking among applications in OS

🧪 LAB REPORT QUESTION (PRACTICAL — COVERS THE ENTIRE CHAPTER)

LAB EXPERIMENT — UNIT V (LINKED LIST)

Title: Implementation of a Menu-Driven Singly Linked List in Java Objective: To design and implement, in Java, a menu-driven program that performs all major operations on a Singly Linked List — covering creation, insertion (beginning, end, and specific position), deletion (beginning, end, and specific position), traversal/display, searching, concatenation with another list, and the application of adding two polynomials using a linked list.

Problem Statement

Write a single Java program with a menu-driven interface that performs the following operations on a Singly Linked List, allowing the user to choose any operation repeatedly until they exit:

  1. Create a Singly Linked List
  2. Insert a node at the Beginning
  3. Insert a node at the End
  4. Insert a node at a Specific Position
  5. Delete a node from the Beginning
  6. Delete a node from the End
  7. Delete a node from a Specific Position
  8. Search for an element
  9. Display (Traverse) the list
  10. Concatenate another linked list
  11. Add two polynomials using a linked list
  12. Exit

Algorithm (High-Level)

  1. Define a Node class with int data and Node next.
  2. Define a SinglyLinkedList class containing a head reference and all operation methods.
  3. In main(), display a menu in a loop.
  4. Based on the user's choice, invoke the corresponding method.
  5. After each operation, display the updated list.
  6. For polynomial addition, build two polynomial lists, compute the sum, and display the result.

Complete Java Source Code (Lab Submission)

import java.util.Scanner;

/* ---------------- Node for normal list ---------------- */
class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

/* ---------------- Node for polynomial ---------------- */
class Term {
    int coeff, exp;
    Term next;
    Term(int c, int e) { coeff = c; exp = e; next = null; }
}

/* ---------------- Singly Linked List class ---------------- */
class SinglyLinkedList {
    Node head;

    public void insertAtBeginning(int v) {
        Node n = new Node(v);
        n.next = head;
        head = n;
    }

    public void insertAtEnd(int v) {
        Node n = new Node(v);
        if (head == null) { head = n; return; }
        Node t = head;
        while (t.next != null) t = t.next;
        t.next = n;
    }

    public void insertAtPosition(int v, int pos) {
        if (pos < 1) { System.out.println("Invalid position"); return; }
        if (pos == 1) { insertAtBeginning(v); return; }
        Node n = new Node(v);
        Node t = head;
        for (int i = 1; i < pos - 1 && t != null; i++) t = t.next;
        if (t == null) { System.out.println("Position out of range"); return; }
        n.next = t.next;
        t.next = n;
    }

    public void deleteAtBeginning() {
        if (head == null) { System.out.println("List is empty"); return; }
        head = head.next;
    }

    public void deleteAtEnd() {
        if (head == null) { System.out.println("List is empty"); return; }
        if (head.next == null) { head = null; return; }
        Node t = head;
        while (t.next.next != null) t = t.next;
        t.next = null;
    }

    public void deleteAtPosition(int pos) {
        if (head == null) { System.out.println("List is empty"); return; }
        if (pos == 1) { head = head.next; return; }
        Node t = head;
        for (int i = 1; i < pos - 1 && t != null; i++) t = t.next;
        if (t == null || t.next == null) { System.out.println("Position out of range"); return; }
        t.next = t.next.next;
    }

    public int search(int key) {
        Node t = head; int pos = 1;
        while (t != null) {
            if (t.data == key) return pos;
            t = t.next; pos++;
        }
        return -1;
    }

    public void display() {
        if (head == null) { System.out.println("List is empty"); return; }
        Node t = head;
        while (t != null) { System.out.print(t.data + " → "); t = t.next; }
        System.out.println("null");
    }

    public void concatenate(SinglyLinkedList other) {
        if (head == null) { head = other.head; return; }
        Node t = head;
        while (t.next != null) t = t.next;
        t.next = other.head;
    }
}

/* ---------------- Polynomial class ---------------- */
class Polynomial {
    Term head;

    public void insert(int c, int e) {
        if (c == 0) return;
        Term n = new Term(c, e);
        if (head == null) { head = n; return; }
        Term t = head;
        while (t.next != null) t = t.next;
        t.next = n;
    }

    public static Polynomial add(Polynomial a, Polynomial b) {
        Polynomial res = new Polynomial();
        Term p = a.head, q = b.head;
        while (p != null && q != null) {
            if (p.exp == q.exp) {
                res.insert(p.coeff + q.coeff, p.exp);
                p = p.next; q = q.next;
            } else if (p.exp > q.exp) {
                res.insert(p.coeff, p.exp); p = p.next;
            } else {
                res.insert(q.coeff, q.exp); q = q.next;
            }
        }
        while (p != null) { res.insert(p.coeff, p.exp); p = p.next; }
        while (q != null) { res.insert(q.coeff, q.exp); q = q.next; }
        return res;
    }

    public void display() {
        if (head == null) { System.out.println("0"); return; }
        Term t = head;
        while (t != null) {
            System.out.print(t.coeff + "x^" + t.exp);
            if (t.next != null) System.out.print(" + ");
            t = t.next;
        }
        System.out.println();
    }
}

/* ---------------- MAIN — Menu-driven ---------------- */
public class LinkedListLab {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        SinglyLinkedList list = new SinglyLinkedList();
        int choice;

        do {
            System.out.println("\n===== LINKED LIST MENU =====");
            System.out.println("1.  Create list (insert at end)");
            System.out.println("2.  Insert at Beginning");
            System.out.println("3.  Insert at End");
            System.out.println("4.  Insert at Specific Position");
            System.out.println("5.  Delete from Beginning");
            System.out.println("6.  Delete from End");
            System.out.println("7.  Delete from Specific Position");
            System.out.println("8.  Search an Element");
            System.out.println("9.  Display the List");
            System.out.println("10. Concatenate with another list");
            System.out.println("11. Add two Polynomials");
            System.out.println("12. Exit");
            System.out.print("Enter your choice: ");
            choice = sc.nextInt();

            switch (choice) {
                case 1:
                    System.out.print("How many nodes? ");
                    int n = sc.nextInt();
                    System.out.println("Enter " + n + " values:");
                    for (int i = 0; i < n; i++) list.insertAtEnd(sc.nextInt());
                    break;
                case 2:
                    System.out.print("Value: ");
                    list.insertAtBeginning(sc.nextInt());
                    break;
                case 3:
                    System.out.print("Value: ");
                    list.insertAtEnd(sc.nextInt());
                    break;
                case 4:
                    System.out.print("Value: "); int v = sc.nextInt();
                    System.out.print("Position: "); int p = sc.nextInt();
                    list.insertAtPosition(v, p);
                    break;
                case 5: list.deleteAtBeginning(); break;
                case 6: list.deleteAtEnd(); break;
                case 7:
                    System.out.print("Position to delete: ");
                    list.deleteAtPosition(sc.nextInt());
                    break;
                case 8:
                    System.out.print("Enter element to search: ");
                    int key = sc.nextInt();
                    int idx = list.search(key);
                    System.out.println(idx == -1 ? "Not found" : "Found at position " + idx);
                    break;
                case 9: list.display(); break;
                case 10:
                    SinglyLinkedList other = new SinglyLinkedList();
                    System.out.print("How many nodes in second list? ");
                    int m = sc.nextInt();
                    System.out.println("Enter values:");
                    for (int i = 0; i < m; i++) other.insertAtEnd(sc.nextInt());
                    list.concatenate(other);
                    System.out.println("After concatenation:");
                    list.display();
                    break;
                case 11:
                    Polynomial p1 = new Polynomial(), p2 = new Polynomial();
                    System.out.print("Terms in P1: ");
                    int t1 = sc.nextInt();
                    System.out.println("Enter coeff and exp for each term of P1:");
                    for (int i = 0; i < t1; i++) p1.insert(sc.nextInt(), sc.nextInt());
                    System.out.print("Terms in P2: ");
                    int t2 = sc.nextInt();
                    System.out.println("Enter coeff and exp for each term of P2:");
                    for (int i = 0; i < t2; i++) p2.insert(sc.nextInt(), sc.nextInt());
                    System.out.print("P1(x) = "); p1.display();
                    System.out.print("P2(x) = "); p2.display();
                    System.out.print("Sum   = "); Polynomial.add(p1, p2).display();
                    break;
                case 12:
                    System.out.println("Exiting...");
                    break;
                default:
                    System.out.println("Invalid choice");
            }
        } while (choice != 12);

        sc.close();
    }
}

Sample Input / Output

===== LINKED LIST MENU =====
Enter your choice: 1
How many nodes? 4
Enter 4 values:
10 20 30 40

Enter your choice: 9
10 → 20 → 30 → 40 → null

Enter your choice: 4
Value: 25
Position: 3

Enter your choice: 9
10 → 20 → 25 → 30 → 40 → null

Enter your choice: 7
Position to delete: 2

Enter your choice: 9
10 → 25 → 30 → 40 → null

Enter your choice: 8
Enter element to search: 30
Found at position 3

Enter your choice: 11
Terms in P1: 3
Enter coeff and exp for each term of P1:
5 3   4 2   2 0
Terms in P2: 3
Enter coeff and exp for each term of P2:
3 3   2 1   1 0
P1(x) = 5x^3 + 4x^2 + 2x^0
P2(x) = 3x^3 + 2x^1 + 1x^0
Sum   = 8x^3 + 4x^2 + 2x^1 + 3x^0

Enter your choice: 12
Exiting...

Discussion

This program demonstrates all the operations of a singly linked list discussed in Unit V — creation, insertion (beginning, end, position), deletion (beginning, end, position), traversal, searching, concatenation, and an application (polynomial addition). The use of a Node class encapsulates the data and link fields, while the SinglyLinkedList and Polynomial classes group related operations together — exhibiting the principles of object-oriented programming in Java.

Conclusion

The experiment has been successfully completed. The output verifies that all linked list operations work correctly, and the menu-driven structure provides an interactive way to test each operation. The program also demonstrates a practical application of linked lists through the addition of two polynomials.

✅ END OF UNIT V — LINKED LIST NOTES