Linked List

Knowledge Summary

Definition of a Linked List

A linked list is a linear data structure made up of a sequence of nodes. Each node contains:

• A data field: stores data
• A pointer field: stores the address of the next node

Linked Lists vs Arrays

Types of Linked Lists

1. Singly linked list: each node has only one next pointer
2. Doubly linked list: each node has both prev and next pointers
3. Circular linked list: the next pointer of the tail points to the head

Basic Operations on a Linked List

1struct Node {
2    int data;
3    Node* next;
4};
5
6// Head insertion
7void insertHead(Node*& head, int val) {
8    Node* newNode = new Node{val, head};
9    head = newNode;
10}
11
12// Delete a node
13void deleteNode(Node*& head, int val) {
14    if (!head) return;
15    if (head->data == val) {
16        Node* temp = head;
17        head = head->next;
18        delete temp;
19        return;
20    }
21    Node* cur = head;
22    while (cur->next && cur->next->data != val)
23        cur = cur->next;
24    if (cur->next) {
25        Node* temp = cur->next;
26        cur->next = temp->next;
27        delete temp;
28    }
29}

Common Preliminary-Round Question Types

• How pointers change after insertion or deletion in a linked list
• Given a sequence of operations, determine the final state of the linked list
• Analyze the steps for reversing a singly linked list