L1. Introduction to LinkedList | Traversal | Length | Search an Element

1. Why Do We Need Linked Lists? (The Problem with Arrays)

When storing collections of data, the most common beginner data structure is the Array. However, arrays come with strict limitations that make them inflexible for dynamic application environments.

Key Array Limitations:

• Fixed Size: Once an array is allocated with a specific size (e.g., size 4), you cannot add a 5th element or shrink it if elements are removed.
• Contiguous Memory Allocation: Elements in an array are stored back-to-back in RAM heap memory. If index 0 is at address 787895, index 1 is strictly at 787896, index 2 at 787897, and so on.
• Rigid Memory Dependencies: Because of contiguous allocation, finding extra adjacent space to resize or expand an array in place is often impossible.

Real-Life Analogy: The Fixed-Seat Train vs. Flexible Car Caravan

The Analogy: Think of an Array as a fixed passenger train where each carriage is welded directly behind the previous one. If you suddenly need to bring 5 extra passengers, you cannot just squeeze an extra carriage into the middle of a moving train; you would have to build an entirely new, longer train and move everyone over.

In contrast, a Linked List is like a caravan of cars driving on a highway. Each car doesn't need to be tightly coupled or parked right behind the other; car #1 can be in New York, car #2 in Chicago, and car #3 in Los Angeles. As long as each driver has the phone number (memory reference) of the next car in the convoy, the entire system functions seamlessly, and you can add or remove cars at a moment's notice.

2. Core Mental Model: How Linked Lists Work

Unlike arrays that rely on mathematical index offsets (base_address + index * data_size), a Linked List consists of independent memory blocks scattered randomly across the Heap.

To maintain order without contiguous memory, each element (commonly called a Node) stores two core components:

1. Data: The actual value being stored (e.g., integer, string, double, custom object).
2. Next Pointer: The exact memory address (reference) pointing to where the next node lives in the Heap.

Visualizing Linked List Memory Layout

• Head: The starting entry point of the Linked List. You must always preserve the head pointer. If you lose head, you lose access to the entire list.
• Tail: The final node in the list, whose next pointer evaluates to NULL (or null in Java / nullptr in C++), indicating the end of the chain.

3. Real-World Applications of Linked Lists

While fundamental data structures like Stacks and Queues are built directly on top of linked lists due to their dynamic resizing capabilities, real-world software engineering leverages them constantly.

The Browser Tab & History Navigation Example

When browsing the web, every page you visit in a single tab forms a linear history sequence:

• Going Back: Clicking the back button traverses backward through references.
• Going Forward: Clicking forward moves down the next pointers.
• Dynamic Growth: You never know beforehand how many pages a user will visit in a session. A Linked List accommodates this infinite, unpredictable expansion and contraction effortlessly without memory reallocation overhead.

4. Self-Defined Objects: Struct vs. Class in C++ and Java

Because a Linked List node holds mixed types (a primitive data value and a memory pointer), standard primitive types (int, double) are insufficient. We must create a self-defined data type (a custom object/struct).

C++ Implementation (struct)

In C++, we use struct or class to define a node.

class Node {
public:
    int data;
    Node* next;

    // Constructor with data and next pointer
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor when only data is provided (defaults next to nullptr)
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

Java Implementation (class)

Java does not have explicit pointer stars (*). References are handled under the hood, and nullptr becomes null.

class Node {
    int data;
    Node next;

    // Constructor with data and next pointer
    Node(int data1, Node next1) {
        this.data = data1;
        this.next = next1;
    }

    // Constructor when only data is provided
    Node(int data1) {
        this.data = data1;
        this.next = null;
    }
}

Language Conversion Cheat Sheet (C++ to Java)

5. Converting an Array into a Linked List

To convert an array of integers (e.g., [2, 1, 3, 8]) into a Linked List, we iterate through the array elements, wrap each element inside a newly allocated Heap node, and stitch them together using pointers.

Step-by-Step Logic

1. Create the Head node using the first array element (array[0]).
2. Establish a Mover pointer (mover) initialized to point at head.
3. Iterate from index 1 to n-1.
4. For each element, create a temporary node.
5. Link mover->next to point to this temporary node.
6. Advance mover forward to the temporary node (mover = mover->next).

Code Implementation (C++)

Node* constructLinkedList(vector<int>& arr) {
    if (arr.empty()) return nullptr;

    // 1. Create Head for the first element
    Node* head = new Node(arr[0]);
    Node* mover = head;

    // 2. Iterate through the rest of the array
    for (int i = 1; i < arr.size(); i++) {
        Node* temp = new Node(arr[i]);
        mover->next = temp; // Connect current node to new node
        mover = temp;       // Move mover forward
    }

    return head; // Always return head to preserve the list entry
}

6. Traversing a Linked List

Traversal is the foundational operation for almost all Linked List algorithms. Because we cannot jump directly to index i, we must walk through the chain node by node.

Golden Rule of Traversal: Never Tamper the Head!

If you move head while traversing, you lose the starting reference of your list forever. Always copy head into a temporary working pointer (temp).

Code Implementation (C++)

void traverseLinkedList(Node* head) {
    Node* temp = head; // Create working pointer

    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next; // Jump to the next node in Heap
    }
    cout << "null" << endl;
}

7. Finding the Length of a Linked List

To find the total number of nodes in a Linked List, we combine our traversal logic with a simple counter variable.

Code Implementation (C++)

int getLength(Node* head) {
    int count = 0;
    Node* temp = head;

    while (temp != nullptr) {
        count++;
        temp = temp->next;
    }

    return count;
}

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the number of nodes, because we must visit each node once.
• Space Complexity: $\mathcal{O}(1)$, as only a counter and pointer variable are maintained.

8. Searching for an Element in a Linked List

To check whether a specific target value exists within a Linked List, we traverse the nodes and compare their .data values against the target.

Code Implementation (C++)

bool searchElement(Node* head, int target) {
    Node* temp = head;

    while (temp != nullptr) {
        if (temp->data == target) {
            return true; // Element found!
        }
        temp = temp->next;
    }

    return false; // Traversed entire list; element not present
}

Analysis of Search Complexities:

• Best Case ($\mathcal{O}(1)$): The target element is located right at the head node.
• Worst Case ($\mathcal{O}(N)$): The target element is at the tail, or missing entirely (requiring a full traversal).
• Average Case ($\mathcal{O}(N/2) \approx \mathcal{O}(N)$): The target is found somewhere in the middle of the list.

Summary and Key Takeaways

• Dynamic Sizing: Unlike fixed-size arrays with contiguous memory restrictions, Linked Lists allocate nodes dynamically anywhere in Heap memory.
• Node Architecture: Each node encapsulates two primary elements: the actual data and a next pointer referencing the subsequent node's memory address.
• The Head Pointer: The head is the sacred entry anchor of any Linked List; never alter or move head directly, or you will lose your data reference.
• Cross-Language Portability: Converting C++ pointer-based node logic (->, nullptr) to Java reference-based logic (., null) requires minimal syntactic adjustments.
• Time Complexity Trade-Off: Accessing an element by index takes $\mathcal{O}(N)$ time in Linked Lists (unlike $\mathcal{O}(1)$ in arrays), because traversal from the head is mandatory.
• Traversal Foundation: Traversal via a temporary pointer (temp = temp->next) underpins all advanced operations like finding length, searching, insertion, and deletion.