Linked Lists: Structure, Polish Notations |DSA Notes

Linked Lists: Structure, Polish Notations, and Operations

A linked list is a way to store and organize data in memory. Unlike arrays, which store data in a fixed size and continuous memory, linked lists are dynamic and can grow or shrink as needed. They are useful in many applications, like managing memory, handling large amounts of data, and solving complex problems efficiently.

In this article, we will learn about linked lists, their structure, Polish notation, and the main operations like insertion, deletion, and circular linked lists.

What is a Linked List?

A linked list is made up of small units called nodes. Each node has two parts:

1. Data – This stores the actual information.
2. Pointer (or Link) – This is a reference to the next node in the list.

Types of Linked Lists

• Singly Linked List: Each node points to the next node.
• Doubly Linked List: Each node points to both the previous and the next node.
• Circular Linked List: The last node connects back to the first node, forming a loop.

Polish Notation and Linked Lists

Polish notation (prefix notation) is a way to write mathematical expressions without brackets. In this format, the operator comes before the operands.

For example:

• Regular notation: (A + B) * C
• Polish notation: * + A B C

Reverse Polish notation (postfix notation) places the operator after the operands:

• Postfix notation: A B + C *

Linked lists help store and process expressions in Polish notation, making them useful for calculators, compilers, and expression evaluation.

Operations on a Linked List

1. Getting a Node and Freeing a Node

• Get Node: To add a new node, we allocate memory using functions like malloc() in C or new in C++.
• Free Node: When a node is no longer needed, we release the memory using free() to prevent memory wastage.

2. Basic Operations on a Linked List

The key operations we can perform on a linked list are:

• Insertion: Adding a new node.
• Deletion: Removing a node.
• Searching: Finding a node with a specific value.
• Traversal: Moving through the list to access elements.

Inserting into an Ordered Linked List

An ordered linked list keeps its elements sorted while inserting new nodes.

Steps to insert a new node:

1. Create a new node and allocate memory.
2. Find the correct position in the sorted list.
3. Update the pointers to maintain the correct order.

Example Code (C)

void insertSorted(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL || (*head)->data >= data) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* current = *head;
    while (current->next != NULL && current->next->data < data)
        current = current->next;

    newNode->next = current->next;
    current->next = newNode;
}

Deleting a Node in a Linked List

To remove a node, we:

1. Find the node to delete.
2. Update the previous node’s pointer.
3. Free the memory of the deleted node.

Example Code (C)

void deleteNode(Node** head, int key) {
    Node* temp = *head, *prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

Circular Linked List

A circular linked list is a special type of linked list where the last node links back to the first node.

Advantages of Circular Linked Lists

• You can start at any node and traverse the entire list without worrying about reaching the end.
• They are useful in applications like round-robin scheduling and buffer management.

Operations on Circular Linked List

• Insertion: Add a node while keeping the circular structure.
• Deletion: Remove a node while ensuring the list remains circular.

Example Code (C)

void insertCircular(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head;

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

        temp->next = newNode;
    }
}

Conclusion

Linked lists are an important data structure that allows efficient data storage and manipulation. They are flexible and can handle dynamic memory allocation, making them useful for various applications like stacks, queues, and graph representations.

By understanding operations like getting and freeing nodes, inserting in an ordered list, deleting nodes, and working with circular lists, students can build a strong foundation in data structures.