Unit 05

Introduction to Linked List

A linked list is a linear data structure in which elements are stored in the form of nodes connected through links (pointers). It allows dynamic memory allocation and efficient insertion and deletion.

Definition: A linked list is a sequence of nodes where each node contains data and a reference (link) to the next node in the sequence.

Basic Components of a Linked List

Singly Linked List

A singly linked list is a type of linked list where each node contains a data field and one pointer (next) pointing to the next node. Traversal is possible only in the forward direction.

Structure of a Singly Linked List

• Each node has the form: [data | next]
• The first node is accessed using head.
• The last node points to NULL indicating end of list.

Basic Operations

Example — Java Representation

class Node {
    int data;
    Node next;
}

class LinkedList {
    Node head;

    void insert(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        head = newNode;
    }
}

Explanation

• Node class holds the data value and a next reference to the next node.
• LinkedList class maintains the head pointer to the first node.
• insert() adds a new node at the beginning by pointing the new node's next to the current head, then updating head.

Advantages & Disadvantages