TOPIC 2 LIST AND LINKED LIST (PT2)

Chapter 2: Operation on Linked List

Introduction

• Focuses on operations and manipulations occurring in linked lists, essential for data structure understanding.

Linked List (Basic)

• A linked list is a linear data structure where elements are not stored at contiguous memory locations.

• Each element, called a node, contains a data part and a pointer to the next node in the sequence.

Linked List: Structure

• Node Structure:

  • Defined in C as follows:

    struct Node {
        int data; // store information
        Node *next; // points to next element or NULL
    };

• Each node consists of:

  • An integer data to store information.

  • A pointer next that points to the next node or NULL if it is the last node.

Basic Operations on Linked List

• Key operations that can be performed:

  • Create new linked list.

  • Create new node.

  • Check if the linked list is empty.

  • Insert a node into the linked list.

  • Delete a node within the linked list.

Traversing a Linked List

• Basic Operations:

  • Search for a specific item in the list.

  • Insert an item into the list either at the front, middle, or back.

  • Delete an item from the list.

• Traversal Process:

  • Initiated from the head pointer, which points to the first node.

  • Use an additional pointer (e.g., current) of the same type to navigate through the elements.

Example of Traversing a Linked List

• Representation of nodes:

  • Initial state: head -> 2 -> 15 -> 8 -> 24

  • Traversal shows how to access each node sequentially using a pointer.

Insertion Operations

Insert at the End of Node

• To add a node at the end of the list, follow the linked list structure and establish a new node's pointer to NULL.

  • Example: Insert value 34 at the end of the linked list.

Insert at the Beginning of Node

• To add a new node at the start, adjust the head pointer and point the new node to the current head.

  • Example: Insert value 100 at the beginning.

Insert at the Middle of Node

• Insertion can also occur at any specified point within the linked list by adjusting pointers appropriately.

  • Example: Insert value 50 after the node with value 15.

Deletion Operations

Delete the First Node

• To remove the first node:

  • Create a new pointer to point at the first node.

  • Move the head pointer to the second node, effectively removing the first node from the linked list.

Delete the Last Node

• To remove the last node:

  • Traverse to the second-to-last node.

  • Adjust the next pointer of this node to NULL, removing the last node effectively.

Delete the Middle Node

• Deleting a middle node involves:

  • Traversing the list to find the node to delete.

  • Adjusting pointers to bypass the node being deleted.

  • Example: Delete node with value 8 in the list.