Linked Lists

In a linked list, each element is called a node. Each node consists of two parts: the data and a reference (also called a pointer) to the next node.

Here's an example of a simple linked list implemented using C++:

#include <iostream>
using namespace std;

int main() {
  // Linked List implementation

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

  // Create nodes
  Node* node1 = new Node;
  Node* node2 = new Node;
  Node* node3 = new Node;

  // Assign data values
  node1->data = 1;
  node2->data = 2;
  node3->data = 3;

  // Connect nodes
  node1->next = node2;
  node2->next = node3;
  node3->next = nullptr;

  // Traversal
  Node* current = node1;
  while (current != nullptr) {
    cout << current->data << ' ';
    current = current->next;
  }

  return 0;
}

In this example, the linked list contains three nodes: node1, node2, and node3. Each node is assigned a data value (1, 2, or 3) and a reference to the next node. The nullptr value indicates the end of the list.

To traverse the linked list, we start from the first node (node1) and print the data value. Then, we move to the next node using the reference (next) until we reach the end of the list.

```c++
#include <iostream>
using namespace std;

int main() {
  // Linked List implementation

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

  // Create nodes
  Node* node1 = new Node;
  Node* node2 = new Node;
  Node* node3 = new Node;

  // Assign data values
  node1->data = 1;
  node2->data = 2;
  node3->data = 3;

  // Connect nodes
  node1->next = node2;
  node2->next = node3;
  node3->next = nullptr;

  // Traversal
  Node* current = node1;
  while (current != nullptr) {
    cout << current->data << ' ';
    current = current->next;
  }

  return 0;
}
```

In a linked list, each element is called a __________. Each node consists of two parts: the data and a reference (also called a pointer) to the next node.

To implement a singly linked list in C++, we first define a Node class that represents each individual node in the linked list. The Node class contains two members: data, which stores the value of the node, and next, which is a pointer to the next node in the list.

#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

Next, we define a SinglyLinkedList class that contains a pointer to the head of the linked list. The SinglyLinkedList class provides methods for inserting nodes into the list and printing the list.

#include <iostream>
using namespace std;

class SinglyLinkedList {
public:
    Node* head;

    SinglyLinkedList() {
        head = nullptr;
    }

    void insert(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    void printList() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
    }
};

```c++
#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

class SinglyLinkedList {
public:
    Node* head;

    SinglyLinkedList() {
        head = nullptr;
    }

    void insert(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    void printList() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
    }
};

int main() {
    SinglyLinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.printList(); // Outputs 1 2 3
    return 0;
}
```

True or false swipe question for implementing a singly linked list: A singlly linked list contains a pointer to the previous node.

To add a new node to the linked list, follow these steps:

1. Create a new node with the desired data.

2. If the list is empty, make the new node the head of the list.

3. Otherwise, traverse the list to find the last node.

4. Insert the new node at the end of the list by setting the next pointer of the last node to point to the new node.

Here's an example of adding a new node to a singly linked list in C++:

#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

int main() {
  // Create the head of the list
  Node* head = new Node(1);

  // Add a new node
  Node* newNode = new Node(2);

  // Traverse the list to find the last node
  Node* current = head;
  while (current->next != nullptr) {
    current = current->next;
  }

  // Insert the new node at the end of the list
  current->next = newNode;

  // Optional: Display the updated list
  current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }

  return 0;
}

```c++
#include <iostream>
using namespace std;

int main() {
  // Create a new node
  Node* newNode = new Node(data);

  // If the list is empty, make the new node the head
  if (head == nullptr) {
    head = newNode;
  }
  // Otherwise, traverse the list to find the last node
  else {
    Node* current = head;
    while (current->next != nullptr) {
      current = current->next;
    }
    // Insert the new node at the end of the list
    current->next = newNode;
  }

  // Optional: Display the updated list
  Node* current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }

  return 0;
}
```

Adding a new node to a linked list involves creating a new node with the desired data. This node becomes the head of the list if the list is empty. If the list is not empty, the new node is inserted at the end of the list by setting the next pointer of the last node to point to the new node.

Solution: true

To search for a specific value in a linked list, you can traverse the list and compare each node's data with the target value. Here's an example of how to search for a value in a singly linked list using C++:

#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

// Function to search for a value in a linked list
bool searchLinkedList(Node* head, int value) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

int main() {
    // Create the head of the list
    Node* head = new Node(1);

    // Add nodes to the list
    Node* node1 = new Node(2);
    head->next = node1;
    Node* node2 = new Node(3);
    node1->next = node2;
    Node* node3 = new Node(4);
    node2->next = node3;
    Node* node4 = new Node(5);
    node3->next = node4;

    // Search for a value in the list
    int value = 3;
    bool found = searchLinkedList(head, value);
    if (found) {
        cout << "Value " << value << " found in the linked list" << endl;
    } else {
        cout << "Value " << value << " not found in the linked list" << endl;
    }

    return 0;
}

```c++
#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

// Function to search for a value in a linked list
bool searchLinkedList(Node* head, int value) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

int main() {
    // Create the head of the list
    Node* head = new Node(1);

    // Add nodes to the list
    Node* node1 = new Node(2);
    head->next = node1;
    Node* node2 = new Node(3);
    node1->next = node2;
    Node* node3 = new Node(4);
    node2->next = node3;
    Node* node4 = new Node(5);
    node3->next = node4;

    // Search for a value in the list
    int value = 3;
    bool found = searchLinkedList(head, value);
    if (found) {
        cout << "Value " << value << " found in the linked list" << endl;
    } else {
        cout << "Value " << value << " not found in the linked list" << endl;
    }

    return 0;
}
```

Searching a linked list involves traversing the list and comparing each node's data with the target value.

To delete a node from a linked list, you need to find the node with the value you want to delete and update the links to remove it from the list. The code snippet below demonstrates how to delete a node from a linked list in C++:

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

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

// Linked list class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Function to insert a node at the end
    void insert(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Function to delete a node from the linked list
    void deleteNode(int value) {
        Node* current = head;
        Node* previous = nullptr;

        // Iterate through the list to find the node to delete
        while (current != nullptr) {
            if (current->data == value) {
                // If the node to delete is the head
                if (current == head) {
                    head = current->next;
                } else {
                    previous->next = current->next;
                }
                delete current;
                return;
            }

            previous = current;
            current = current->next;
        }

        cout << "Node with value " << value << " not found" << endl;
    }

    // Function to print the linked list
    void printList() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;

    // Insert nodes
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);

    // Print initial list
    cout << "Initial List: ";
    list.printList();

    // Delete a node
    int value = 3;
    cout << "Deleting Node with value " << value << "..." << endl;
    list.deleteNode(value);

    // Print updated list
    cout << "Updated List: ";
    list.printList();

    return 0;
}

```c++
#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

// Linked list class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Function to insert a node at the end
    void insert(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Function to delete a node from the linked list
    void deleteNode(int value) {
        Node* current = head;
        Node* previous = nullptr;

        // Iterate through the list to find the node to delete
        while (current != nullptr) {
            if (current->data == value) {
                // If the node to delete is the head
                if (current == head) {
                    head = current->next;
                } else {
                    previous->next = current->next;
                }
                delete current;
                return;
            }

            previous = current;
            current = current->next;
        }

        cout << "Node with value " << value << " not found" << endl;
    }

    // Function to print the linked list
    void printList() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;

    // Insert nodes
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);

    // Print initial list
    cout << "Initial List: ";
    list.printList();

    // Delete a node
    int value = 3;
    cout << "Deleting Node with value " << value << "..." << endl;
    list.deleteNode(value);

    // Print updated list
    cout << "Updated List: ";
    list.printList();

    return 0;
}
```

Deleting a node from a linked list requires finding the node with the value you want to delete and updating the links to remove it from the list.

To reverse a linked list, you need to update the links between the nodes. The basic idea is to traverse the list while changing the next pointers to reverse the links.

Here is the C++ code to reverse a linked list:

#include <iostream>
using namespace std;

// Function to reverse a linked list
void reverseList(Node* &head) {
    Node* current = head;
    Node* prev = nullptr;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    head = prev;
}

int main() {
    // Linked list nodes
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);

    // Connect nodes
    head->next = second;
    second->next = third;
    third->next = fourth;

    cout << "Original List: ";
    printList(head);

    // Reverse the list
    reverseList(head);

    cout << "Reversed List: ";
    printList(head);

    return 0;
}

Let's go through the code step by step: - The function reverseList takes a reference to the head of the linked list as a parameter. - Inside the function, we define three pointers: current, prev, and next. - We initialize current with the head of the linked list and prev and next with nullptr. - We then iterate through the list using a while loop until current becomes nullptr. - Inside the loop, we first store the next node in the next pointer. - Then, we update the next pointer of the current node to point to the previous node. - After that, we update prev to be the current node and current to be the next node. - Once the loop ends, we update the head of the linked list to be the last node we reached (previously prev). - Finally, we print the original and reversed lists using the printList function.

The time complexity of this algorithm is O(n) as we need to traverse the entire list once to reverse it.

```c++
#include <iostream>
using namespace std;

// Function to reverse a linked list
void reverseList(Node* &head) {
    Node* current = head;
    Node* prev = nullptr;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    head = prev;
}

int main() {
    // Linked list nodes
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);

    // Connect nodes
    head->next = second;
    second->next = third;
    third->next = fourth;

    cout << "Original List: ";
    printList(head);

    // Reverse the list
    reverseList(head);

    cout << "Reversed List: ";
    printList(head);

    return 0;
}
```

Reversing a linked list can be done by reversing the order of the nodes.

To detect whether a linked list contains a cycle, we can use the Floyd's Cycle Detection Algorithm. This algorithm makes use of two pointers, a slow pointer and a fast pointer, to traverse the linked list.

Here is the C++ code to detect a cycle in a linked list:

#include <iostream>
using namespace std;

// Function to detect a cycle in a linked list
bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }

    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

int main() {

    // Create a linked list with a cycle
    ListNode *head = new ListNode(1);
    ListNode *second = new ListNode(2);
    ListNode *third = new ListNode(3);
    ListNode *fourth = new ListNode(4);

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second; // cycle

    if (hasCycle(head)) {
        cout << "The linked list contains a cycle." << endl;
    } else {
        cout << "The linked list does not contain a cycle." << endl;
    }

    return 0;
}

```c++
#include <iostream>
using namespace std;

// Function to detect a cycle in a linked list
bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }

    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

int main() {

    // Create a linked list with a cycle
    ListNode *head = new ListNode(1);
    ListNode *second = new ListNode(2);
    ListNode *third = new ListNode(3);
    ListNode *fourth = new ListNode(4);

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second; // cycle

    if (hasCycle(head)) {
        cout << "The linked list contains a cycle." << endl;
    } else {
        cout << "The linked list does not contain a cycle." << endl;
    }

    return 0;
}
```

Which algorithm can be used to detect whether a linked list contains a cycle?

Generating complete for this lesson!