Collin:COCS-2436

# Linked Lists

#### Objectives

1. Understand the concept and structure of linked lists
2. Differentiate between types of linked lists
3. Implement basic operations on linked lists
4. Analyze the time complexity of linked list operations
5. Compare linked lists with arrays

---

## What is a Linked List?

- A linear data structure
- Elements are stored in nodes
- Each node contains:
    - Data
    - Reference \(link\) to the next node
- Last node points to null

![img.png](assets/linkedList.png)

---

## Why Linked Lists?

- Dynamic size
- Efficient insertion and deletion
- Flexible memory allocation
- Foundation for other data structures

#### Array
![img.png](assets/array.png)

---  
#### Linked List

![img.png](assets/linkedList.png)

![train.png](assets/train.png)
---

# Linked Lists vs ArrayLists vs Arrays

| Aspect| Linked List | ArrayList     | Array|
|--------------------|--------------------------|----------------------------|-------------------|
| Memory allocation  | Dynamic     | Dynamic       | Static            |
| Insertion/Deletion | O(1) at beginning/end    | O(n) for shifting          | O(n) for shifting |
| Random access      | O(n) (must traverse)        | O(1)          | O(1) (direct index) |
| Memory usage       | Higher (extra for links) | Higher (resizing overhead) | Lower|

---

## Types of Linked Lists

| Type |   |
|------|--------------------------------|
| Singly Linked List | ![img.png](assets/singly.png)  |
| Doubly Linked List | ![img_1.png](assets/doubly.png) |
| Circular Linked List | ![img_2.png](assets/circular.png) |

---

## Singly Linked List

- Each node has data and a reference to the next node
- Last node points to null

```java

class Node {
    int data;
    Node next;

Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head;

SinglyLinkedList() {
        this.head = null;
    }
}
```
![img.png](assets/singly.png)

---

## Doubly Linked List

- Each node has data, a reference to the next node, and a reference to the previous node
- First node's previous points to null
- Last node's next points to null

```java 
class Node {
    int data;
    Node next;
    Node prev;

Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }

}

class DoublyLinkedList {
    Node head;

DoublyLinkedList() {
        this.head = null;
    }
}
```
![img_1.png](assets/doubly.png)

---

## Circular Linked List

- Last node points to the first node
- Circular structure

```java
class Node {
    int data;
    Node next;

Node(int data) {
        this.data = data;
        this.next = null;
    }
}    
```
![img_2.png](assets/circular.png)

---

## Basic Operations

- Insertion
- Deletion
- Traversal
- Search

---

### Insertion in Singly Linked List

```java
public void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
}
```

---

# Deletion in Singly Linked List

```java
public void deleteNode(int key) {
    if (head != null && head.data == key) {
        head = head.next;
        return;
    }
    Node current = head;
    Node prev = null;
    while (current != null && current.data != key) {
        prev = current;
        current = current.next;
    }
    if (current != null) {
        prev.next = current.next;
    }
}
```

---

# Traversal in Singly Linked List

```java
public void traverse() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null");
}
```

---

## Recursion in Linked Lists

- Elegant and concise solutions
- Natural fit for linked list structure
- Useful for complex operations

---

#### Recursive Traversal

```java
public void printListRecursive(Node head) {
    if (head == null) return;
    System.out.print(head.data + " -> ");
    printListRecursive(head.next);
}
//----------
public void printListIterative(Node head) {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null");
}
```

---

#### Recursive Reverse

```java
public Node reverseRecursive(Node head) {
    if (head == null || head.next == null) return head;
    Node rest = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return rest;
}
//-------
public Node reverseIterative(Node head) {
    Node prev = null;
    Node current = head;
    Node next = null;
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
```

---

## Advanced Operations and Applications

- Reversing a Linked List: This is a common interview question and a practical operation.
- Detecting a Cycle: This is useful in graph algorithms and system design.
- Finding the Middle Element: This is helpful in various applications.
- Merging Two Sorted Linked Lists: This is a common operation in sorting algorithms.
- Real-world Applications
    - Implementation of stacks and queues
    - Undo/Redo functionality in applications
    - Music playlist management
    - Browser cache implementation: LRU Cache (Least Recently Used Cache)
    - Graphs & Social Networks
    - Scheduler for Task Processing: CPU Task Scheduling, Round-Robin Algorithms

---

### Knowledge Check - http://quiz.codewithme.com
### OR 
### Visit gosocrative.com and enter room name cocs2436
---
# LABS