# Linked List

Linked List is a data structure, which is a collection of nodes where each node contains data and pointer to the next node. There is a head pointer which points to the first node of the list and is used in program to access the whole list, head is basically the whole identity of the list which we as a programmer have access to.

## Definition of a Node

Nodes can be defined in a C\C++ program using structs. It contains data (which can be of any type) and a pointer to a Node. Because of the fact that it contains a pointer to Node, it is called **Self-Referential** structures.

struct Node
{
    int data;
    struct Node* next;
}

digraph D
{
    node[shape=record]
    rankdir=LR
    layout=neato
    N[label="{data|next}", pos="0,0!"]
    "Node" [pos="0,0.5!",color=invis]
}

## Displaying/Printing

For displaying the Linked List we have to traverse(visit a node) the list and print the value of every node.

We use a `while` loop for visiting each node and checking if the current node is equal to `NULL` or not, if not then we execute the block of code which prints the value to the terminal. Otherwise the loop terminates and the function returns.

### Implementation

void Print()
{
    Node* current = head;
    std::cout << "Elements in List: ";
    while (current != NULL)
    {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << '\n';
}

### Analysis

We go through each element(or node) of the list once, so the <br> **Time complexity** is **O(n)** and there is no extra memory used in allocating other data structures so the **Space complexity** is **O(1)**.

### Recursively Displaying

Displaying can be done recursively as well. We pass the head pointer to the function parameter and check if the pointer is `NULL` or not. If it is `!NULL` we print the data in the current node and recursively call the function on the next node.

The upper if condition is there purely for aesthetic reasons. We declare a static int variable so that the string `"Elements in the List: "` is only printed once and not everytime the function is called. Static variables have this special property of only being able to be initialized once and not every time the function is called. So once the flag is set to 1, it won't get initialized to 0 in the next function call.

#### Implementation

void RecursivePrint(Node* ptr)
{
    static int flag = 0;
    if (flag == 0)
    {
        std::cout << "Elements in List: ";
        flag = 1;
    }
    if (ptr != NULL)
    {
        std::cout << ptr->data << " ";
        RecursivePrint(ptr->next);
    }
}

#### Analysis

Just like the iterative display function, we go through each element once, so **Time complexity** is **O(n)**. But space complexity is not constant even though we are **not explicitly** allocating memory, but behind the scenes stack data structure is used by the language and each function call allocates a stack frame. So the **Space complexity** is **O(n)**.

## Length

Here we are simply traversing the list and maintaining a variable which will get incremented when a node is encountered.

### Implementation

int Length()
{
    Node* current = head;
    int len = 0;
    while (current != NULL)
    {
        current = current->next;
        len++;
    }
    return len;
}

### Analysis

**Time complexity** = O(n)
**Space complexity** = O(1)

### Recursive Implementation

int Length(Node* p)
{
    if (p == NULL) return 0;
    else return Length(p->next) + 1;
}

## Max/Min

Here, just like other functions we traverse the linked list and maintain a max variable which is initialized to INT32_MIN, and just if any node has

### Implementation

**Max**

int LinkedList::Max()
{
    int max = INT32_MIN;
    Node* current = head->next;
    while (current != NULL)
    {
        if (current->data > max)
        {
            max = current->data;
        }
        current = current->next;
    }
    return max;
}

**Min**

int Min()
{
    int min = INT32_MAX;
    Node* current = head->next;
    while (current != NULL)
    {
        if (current->data < min)
        {
            min = current->data;
        }
        current = current->next;
    }
    return min;
}

### Analysis

**Time complexity** = O(n)
**Space complexity** = O(1)

## Searching

Searching in a linked list can be done by performing Linear search. Binary Search is not really an option as accessing an element doesn't take a constant amount of time making Binary search's Time complexity O(n).

Node* Search(Node* p, int key)
{
    while (p != NULL)
    {
        if (key == p->data) return p;
        p = p->next;
    }
    return NULL;
}

## Insertion

void Insert(Node* p, int data, int pos)
{
    if (index < 0 || index > Length(p))
        return;

    else
    {
        Node* t = new Node();
        t->data = data;

        if (pos == 0)
        {
            t->next = head;
            head = t;
        }

        else
        {
            for (int i = 0; i < pos - 1; i++)
            {
                p = p->next;
            }
            t->next = p->next;
            p->next = t;
        }
    }
}

### In a sorted list

void SortedInsert(Node* p, int data)
{
    Node* t, *q = NULL;
    t = new Node();
    t->data = data;
    t->next = NULL;

    if (head == NULL) head = t;
    else
    {
        while (p != NULL && p->data < x)
        {
            q = p;
            p = p->next;
        }
        if (p == head)
        {
            t->next = head;
            head = t;
        }
        else
        {
            t->next = q->next;
            q->next = t;
        }
    }
}

## Deletion

int Delete(int pos)
{
    Node* prev = head;
    int x;
    if (pos == 1)
    {
        head = prev->next;
        x = prev->data;
        delete prev;
    }
    else
    {
        for (int i = 0; i < pos - 2; i++)
            prev = prev->next;

        Node* toDelete = prev->next;
        prev->next = toDelete->next;
        x = toDelete->data;
        delete toDelete;
    }
    return x;
}

## Checking for a sorted list

We can check if a list is sorted by traversing the whole list and checking if the previous element is smaller than the next element(Ascending Order), and stop checking if the condition becomes false.

We use a `prev` pointer which points to the previous element of the node that we currently are at, and check if it is smaller than the current node value. If True, then update `prev = current` and `current = current->next` and check the next nodes. If False, then it will return False and break out of the function.

### Implementation

bool IsSorted()
{
    int current = INT32_MIN;
    Node* prev = head;
    while (prev != NULL)
    {
        if (prev->data < current)
            return false;

        current = prev->data;
        prev = prev->next;
    }
    return true;
}

We initially take current value as INT32_MIN which is the **lowest** possible value of integer of **32 bits** and therefore we can even check for sorted lists when the values are negative.

# Till Video Number 25