DSA Tutorial

🔄 Linked List Structure: Each node points to the next node, forming a chain-like structure.

Types of Linked Lists

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

Algorithm for Insertion in Singly Linked List

• Step 1: Create a new node with the given value.
• Step 2: Point the new node's next to the current head of the list.
• Step 3: Update the head pointer to point to the new node.

Pseudo Code

function insertAtBeginning(head, value):
    new_node = createNewNode(value)
    new_node.next = head
    head = new_node
    return head
    

💻 C Code Example: Insert at Beginning

#include <stdio.h>
#include <stdlib.h>

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

struct Node* insertAtBeginning(struct Node* head, int value) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = value;
    new_node->next = head;
    head = new_node;
    return head;
}

void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    head = insertAtBeginning(head, 5);
    head = insertAtBeginning(head, 10);
    head = insertAtBeginning(head, 15);
    
    printList(head);
    return 0;
}
    

⏱ Time Complexity

- Insertion at the beginning of the list: O(1) (constant time).
- Searching for a value: O(n) (linear time), where 'n' is the number of nodes.

📊 Linked List vs Array:
- Linked Lists allow efficient insertion/deletion at any point (O(1)), while arrays require shifting elements (O(n)).
- Arrays offer constant-time access (O(1)) using indices, whereas linked lists require traversal (O(n)) to access an element.

🚀 Try Implementing Linked Lists:
- Create a singly linked list and implement insertion, deletion, and traversal.
- Explore how doubly linked lists work by adding a `prev` pointer to each node.