Linear Data Structures

One characteristics of of linked lists is that they are linear data structures, which means that there is sequence and an order to how they are constructed and traversed. 

In non-linear data structures, items don't have to be arranged in order, which means that we could traverse the data structure non-sequentially.

How to Solve any linked list problem

Here’s a guide to help you tackle linked list problems:

1️⃣ Understand the Problem Statement

• Read Carefully: Make sure you fully understand what the problem is asking. Identify whether it's a singly or doubly linked list, whether it has additional pointers (like random pointers), and what operations need to be performed.
• Clarify Edge Cases: Consider edge cases like an empty list, a single-node list, a list with cycles, or lists that intersect.

2️⃣ Plan Your Approach

• Identify the Core Operation: Determine the main operation you need to perform (e.g., insertion, deletion, reversing, detecting loops).
• Think About the Data Structure: Understand how the data structure works, particularly how pointers need to be manipulated.
• Decide on the Technique: Common techniques for solving linked list problems include:
  • Two-pointer Technique: Useful for problems like finding the middle of a linked list or detecting cycles.
  • Dummy Nodes: Simplifies edge cases, especially for problems involving head node deletion or insertion.
  • Recursive Approach: Suitable for problems like reversing a linked list recursively or merging two sorted lists.

3️⃣ Write the Algorithm Step-by-Step

• Break Down the Problem: Write down each step you need to perform. For example, if you are reversing a linked list, steps might include iterating through the list, reversing pointers one by one, and keeping track of the previous node.
• Pseudo Code: Before jumping into code, write pseudo code to outline your approach. This helps in structuring your thoughts and ensuring you don't miss any steps.

4️⃣ Implement the Solution

• Start Simple: Begin with a straightforward solution that is easy to implement, even if it's not the most optimized.
• Handle Edge Cases: Ensure your implementation handles edge cases like an empty list or a list with only one node.
• Use Comments: Comment your code to explain what each section does, particularly for complex pointer manipulations.

5️⃣ Test Your Solution

• Test With Simple Cases: Start by testing your solution with simple, small linked lists to ensure the basic functionality works.
• Test Edge Cases: Include tests for edge cases, such as empty lists, single-node lists, and lists with duplicate values.
• Test Performance: For larger inputs, consider the time and space complexity of your solution.

6️⃣ Optimize the Solution

• Evaluate Complexity: Review your solution’s time and space complexity. For linked list problems, the goal is often O(n) time complexity and O(1) space complexity.
• Refactor Code: Look for ways to simplify and optimize your code. Avoid unnecessary loops or recursive calls that could be converted to iterative ones.

Understanding Pointers

A pointer is a variable that stores the memory address of another variable. In simpler terms, it "points" to the location in memory where data is stored. This allows you to indirectly access and manipulate data by referring to its memory address.

Pointers are a powerful feature in C++ that enable dynamic memory allocation and the creation of complex data structures like linked lists, trees, and graphs. They are declared using an asterisk (*) before the pointer name, and the address-of operator (&) is used to obtain the memory address of a variable.

For example, if you have a variable int x = 10;, a pointer to this variable can be declared as int* ptr = &x;. The pointer ptr now holds the memory address of x. You can access the value of x indirectly through the pointer by using the dereference operator (*), like this: *ptr.

Pointers are essential for efficient memory management and are widely used in low-level programming, performance optimization, and working with advanced data structures. Understanding how to use pointers effectively can greatly enhance your ability to write efficient and powerful C++ programs.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 10; 
    // Declare a pointer and assign it the address of x
    int* ptr = &x;     

    // Print the value of x and the address of x
    cout << "Value of x: " << x << endl;
    cout << "Address of x: " << &x << endl;

    // Print the value stored in ptr and the value pointed to by ptr
    cout << "Value stored in ptr (address of x): " << ptr << endl;
    cout << "Value pointed to by ptr: " << *ptr << endl;

    // Modify the value of x using the pointer
    *ptr = 20;

    // Print the new value of x
    cout << "New value of x after modification: " << x << endl;

    return 0;
}

Value of x: 10
Address of x: 0x5052f8
Value stored in ptr (address of x): 0x5052f8
Value pointed to by ptr: 10
New value of x after modification: 20

Creation of Simple Linked List

We can create a simple linked list either using structure or class in c++.

Here is the very basic prototype of an linked list using structure in c++.

Linked List using Structure:

// Define a Node using a struct
struct Node {
    int data;       // Data stored in the node
    Node* next;     // Pointer to the next node in the list

    // Constructor to initialize the node with data and set next to nullptr
    Node(int data) {
    	this->data = data;
    	next = nullptr;
    }
};

int main() {
	Node* head = new Node(1);
	head->next = new Node(2);
	head->next->next = new Node(3);
	head->next->next->next = new Node(4);
	head->next->next->next->next = new Node(5);

// Print the Linked List 	
 	Node* curr = head;
	while(curr != nullptr) {
		cout << curr->data << " -> ";
		curr = curr->next;
	}
    cout << "nullptr" << endl;
}

Linked List using Class:

// Define a Node using a class
class Node {
public:
    int data;       // Data stored in the node
    Node* next;     // Pointer to the next node in the list

    // Constructor to initialize the node with data and set next to nullptr
    Node(int data) {
    	this->data = data;
    	next = nullptr;
    }
};

int main() {
	Node* head = new Node(1);
	head->next = new Node(2);
	head->next->next = new Node(3);
	head->next->next->next = new Node(4);
	head->next->next->next->next = new Node(5);

// Print the Linked List 	
 	Node* curr = head;
	while(curr != nullptr) {
		cout << curr->data << " -> ";
		curr = curr->next;
	}
    cout << "nullptr" << endl;

}

Difference Between Node and Node*

In C++, the terms Node and Node* are related but refer to different concepts:

Node:

1. This represents a variable of type Node.
2. It is an instance of the Node structure or class.
3. When you declare a variable as Node, it directly holds the data and any member variables defined in the Node structure or class.
4. Example: Node node1; creates a Node object named node1.

Node*:

1. This represents a pointer to a Node type.
2. It does not hold the actual data but rather the memory address where a Node object is stored.
3. Using a pointer allows for dynamic memory allocation, meaning you can create and manage nodes at runtime using the new operator.
4. Example: Node* nodePtr = new Node(); creates a pointer to a dynamically allocated Node object.

Memory Space:

Let's consider storing integers. A key difference between arrays and linked lists is their memory usage. For arrays, each integer takes up 4 bytes of memory. In contrast, linked lists store both data and a pointer in each node, so the memory usage depends on the system configuration.

Common Patterns

Two-pointer Technique:

The Two Pointer Technique is a powerful strategy in linked list manipulation, enabling efficient solutions to many common problems. In linked lists, this technique usually involves using two pointers that traverse the list at different speeds or start from different points, allowing us to solve problems with reduced time complexity and memory usage.

1️⃣ Fast and Slow Pointers (Tortoise and Hare):

Purpose: This technique involves using two pointers that move at different speeds to find specific elements or detect cycles within a linked list.

Common Use Cases:

• Cycle Detection: Determine if a linked list has a loop.
• Finding the Middle of a Linked List: Locate the middle node in a single traversal.
• Finding the Start of a Cycle: Identify the entry point of a loop after detecting a cycle.

2️⃣ Lag and Lead Pointers (N-Pointer Distance):

Purpose: This variation finds a node based on its position from the end of the linked list. It involves using two pointers that start at different positions or with a certain distance apart however traverse in same speed.

Common Use Cases:

• Finding the Nth Node from the End: Retrieve the node that is a certain distance from the end.
• Removing the Nth Node from the End: Remove a node based on its position from the end.

Resources

1️⃣ Become Master In Linked List - LeetCode Discuss

2️⃣ https://www.techinterviewhandbook.org/algorithms/linked-list/

3️⃣ https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d

4️⃣ https://medium.com/basecs/whats-a-linked-list-anyway-part-2-131d96f71996