Linked Lists

Welcome to the world of Linked Lists!

Linked lists are linear data structures that store elements in a non-contiguous manner. Unlike arrays, which store elements in contiguous memory locations, linked lists use nodes to hold the elements and pointers to connect the nodes.

Let's take a look at the advantages of linked lists over arrays:

1. Dynamic Size: Linked lists can grow or shrink dynamically based on the number of elements added or removed. This makes linked lists more flexible compared to arrays, which have a fixed size.

2. Efficient Insertion and Deletion: Inserting or deleting elements in a linked list is more efficient compared to arrays. In linked lists, you just need to update the pointers, while in arrays, you need to shift elements to make space for the new element or fill the gap created by the deleted element.

3. Flexibility in Memory Management: Linked lists allow for efficient memory management. The elements can be stored anywhere in memory, and the nodes can be scattered across different locations. This allows for efficient memory allocation and utilization.

So, as you can see, linked lists offer several advantages over arrays. They are especially useful in scenarios where the size of the data is not known beforehand or when efficient insertion and deletion operations are required.

Now, let's dive deeper into the implementation of linked lists in C++. Take a look at the code snippet below:

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

int main() {
  // Linked List implementation
  // ... code here

  return 0;
}
```

What is a major advantage of linked lists over arrays?

Welcome to the world of Linked Lists!

In this lesson, we will dive into implementing a linked list class and performing basic operations like insertion and deletion.

To get started, let's create a Node class that will represent each element of the linked list. Each node will contain a data value and a pointer to the next node.

#include <iostream>

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

int main() {
    // Create Nodes
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);

    // Link Nodes
    node1->next = node2;
    node2->next = node3;

    // Print Linked List
    Node* current = node1;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;

    return 0;
}

```c++
#include <iostream>

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

int main() {
    // Create Nodes
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);

    // Link Nodes
    node1->next = node2;
    node2->next = node3;

    // Print Linked List
    Node* current = node1;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;

    return 0;
}
```

In a linked list, each element is represented by a _______________ that contains data and a pointer to the next element.

Now let's implement a method to search for an element in a linked list. We'll traverse through the linked list and compare the data value of each node with the target value we want to search. If we find a match, we'll return true, indicating that the element is present in the linked list. If we reach the end of the list without finding a match, we'll return false to indicate that the element is not present.

Here's the C++ code for implementing the search operation:

#include <iostream>
using namespace std;

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List Class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Insertion at the Beginning of the Linked List
    void insert(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Search for an Element in the Linked List
    bool search(int value) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
};

int main() {
    // Create a Linked List
    LinkedList list;
    list.insert(3);
    list.insert(2);
    list.insert(1);

    // Search for an Element
    int searchValue = 2;
    bool isFound = list.search(searchValue);
    if (isFound) {
        cout << "Element " << searchValue << " is present in the Linked List." << endl;
    } else {
        cout << "Element " << searchValue << " is not present in the Linked List." << endl;
    }

    return 0;
}

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

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List Class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Insertion at the Beginning of the Linked List
    void insert(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Search for an Element in the Linked List
    bool search(int value) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
};

int main() {
    // Create a Linked List
    LinkedList list;
    list.insert(3);
    list.insert(2);
    list.insert(1);

    // Search for an Element
    int searchValue = 2;
    bool isFound = list.search(searchValue);
    if (isFound) {
        cout << "Element " << searchValue << " is present in the Linked List." << endl;
    } else {
        cout << "Element " << searchValue << " is not present in the Linked List." << endl;
    }

    return 0;
}
```

In a linked list, the time complexity for searching for an element in the worst-case scenario is O(n), where n is the number of elements in the linked list.

To insert an element into a sorted linked list while maintaining the order, we need to find the correct position for the new element based on its value. We can then insert the new element at that position.

Here's the C++ code for implementing the insertion in a sorted linked list:

#include <iostream>
using namespace std;

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List Class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Insertion in a Sorted Linked List
    void insertSorted(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr || value < head->data) {
            newNode->next = head;
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr && current->next->data < value) {
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
        }
    }
};

int main() {
    // Create a Linked List
    LinkedList list;
    list.insertSorted(3);
    list.insertSorted(1);
    list.insertSorted(2);

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

    return 0;
}

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

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List Class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Insertion in a Sorted Linked List
    void insertSorted(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr || value < head->data) {
            newNode->next = head;
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr && current->next->data < value) {
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
        }
    }
};

int main() {
    // Create a Linked List
    LinkedList list;
    list.insertSorted(3);
    list.insertSorted(1);
    list.insertSorted(2);

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

    return 0;
}
```

In the context of insertion in a sorted linked list, which of the following options correctly describes the process?

A) The new element is always inserted at the beginning of the linked list.

B) The new element is inserted at the end of the linked list.

C) The new element is inserted at the correct position in the linked list while maintaining the sorted order.

D) The new element is inserted randomly at any position in the linked list.

To reverse a linked list, we can use a three-pointer approach. We initialize three pointers: prev, current, and next. Initially, prev and next are set to nullptr and current is set to the head of the linked list.

We then iterate through the linked list, updating the next pointer of the current node to point to the previous node. This way, we reverse the direction of the links.

Here's the C++ code for reversing a linked list using this approach:

#include <iostream>
using namespace std;

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List Class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Reversing a Linked List
    void reverseList() {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;

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

        head = prev;
    }
};

int main() {
    // Create a Linked List
    LinkedList list;
    list.head = new Node(1);
    list.head->next = new Node(2);
    list.head->next->next = new Node(3);
    list.head->next->next->next = new Node(4);

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

    cout << endl;

    // Reverse the Linked List
    list.reverseList();

    // Print the reversed Linked List
    current = list.head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }

    cout << endl;

    return 0;
}

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

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List Class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Reversing a Linked List
    void reverseList() {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;

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

        head = prev;
    }
};

int main() {
    // Create a Linked List
    LinkedList list;
    list.head = new Node(1);
    list.head->next = new Node(2);
    list.head->next->next = new Node(3);
    list.head->next->next->next = new Node(4);

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

    cout << endl;

    // Reverse the Linked List
    list.reverseList();

    // Print the reversed Linked List
    current = list.head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }

    cout << endl;

    return 0;
}
```

Reversing a linked list can be achieved efficiently using a two-pointer approach.

Detecting a Loop in a Linked List

To detect if a linked list has a loop, we can use the Floyd's Cycle-Finding Algorithm.

The algorithm works by using two pointers, one moving at twice the speed of the other. If there is a loop in the linked list, the faster pointer will eventually catch up to the slower pointer.

Here's the C++ code for detecting a loop in a linked list using this algorithm:

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

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

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List Class
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Detecting a Loop
    bool detectLoop() {
        Node* slow = head;
        Node* 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 loop
    LinkedList list;
    list.head = new Node(1);
    list.head->next = new Node(2);
    list.head->next->next = new Node(3);
    list.head->next->next->next = new Node(4);
    list.head->next->next->next->next = list.head->next;

    // Detect a loop in the Linked List
    bool hasLoop = list.detectLoop();

    if (hasLoop) {
        cout << "The Linked List contains a loop." << endl;
    } else {
        cout << "The Linked List does not contain a loop." << endl;
    }

    return 0;
}
```

Which algorithm can be used to detect a loop in a linked list?

Merging Two Sorted Linked Lists

To merge two sorted linked lists into a single sorted list, we can use a simple algorithm. We create a new list and iterate over the two input lists concurrently, comparing the elements and adding them to the new list in the sorted order.

Here's the C++ code for merging two sorted linked lists:

#include <iostream>
using namespace std;

// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to merge two sorted linked lists
Node* mergeLinkedLists(Node* head1, Node* head2) {
  // Create a dummy node to store the merged list
  Node* dummy = new Node(0);
  Node* tail = dummy;

  // Merge the two lists
  while (head1 && head2) {
    if (head1->data <= head2->data) {
      tail->next = head1;
      head1 = head1->next;
    } else {
      tail->next = head2;
      head2 = head2->next;
    }
    tail = tail->next;
  }

  // Append any remaining nodes of the first list
  if (head1) {
    tail->next = head1;
  }

  // Append any remaining nodes of the second list
  if (head2) {
    tail->next = head2;
  }

  // Return the merged list
  return dummy->next;
}

int main() {
  // Create two sorted linked lists
  Node* head1 = new Node(1);
  head1->next = new Node(3);
  head1->next->next = new Node(5);

  Node* head2 = new Node(2);
  head2->next = new Node(4);
  head2->next->next = new Node(6);

  // Merge the two lists
  Node* mergedHead = mergeLinkedLists(head1, head2);

  // Print the merged list
  while (mergedHead) {
    cout << mergedHead->data << " ";
    mergedHead = mergedHead->next;
  }

  return 0;
}

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

// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to merge two sorted linked lists
Node* mergeLinkedLists(Node* head1, Node* head2) {
  // Create a dummy node to store the merged list
  Node* dummy = new Node(0);
  Node* tail = dummy;

  // Merge the two lists
  while (head1 && head2) {
    if (head1->data <= head2->data) {
      tail->next = head1;
      head1 = head1->next;
    } else {
      tail->next = head2;
      head2 = head2->next;
    }
    tail = tail->next;
  }

  // Append any remaining nodes of the first list
  if (head1) {
    tail->next = head1;
  }

  // Append any remaining nodes of the second list
  if (head2) {
    tail->next = head2;
  }

  // Return the merged list
  return dummy->next;
}

int main() {
  // Create two sorted linked lists
  Node* head1 = new Node(1);
  head1->next = new Node(3);
  head1->next->next = new Node(5);

  Node* head2 = new Node(2);
  head2->next = new Node(4);
  head2->next->next = new Node(6);

  // Merge the two lists
  Node* mergedHead = mergeLinkedLists(head1, head2);

  // Print the merged list
  while (mergedHead) {
    cout << mergedHead->data << " ";
    mergedHead = mergedHead->next;
  }

  return 0;
}

```

Which of the following is the correct algorithm to merge two sorted linked lists?

A. Create a new list and insert elements from both lists in sorted order B. Traverse one list and insert elements from the other list at the appropriate positions C. Create a new list and append elements from both lists D. Merge the two lists by inserting elements at the end of the first list

To delete a node from a linked list, we need to update the pointers of the previous and next nodes to bypass the node to be deleted.

Here's the C++ code to delete a node from a linked list:

#include <iostream>
using namespace std;

// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to delete a node from a linked list
void deleteNode(Node* node) {
  if (node == nullptr || node->next == nullptr) {
    return;
  }

  Node* nextNode = node->next;
  node->data = nextNode->data;
  node->next = nextNode->next;
  delete nextNode;
}

int main() {
  // Create a linked list
  Node* head = newNode(1);
  head->next = newNode(2);
  head->next->next = newNode(3);
  head->next->next->next = newNode(4);

  // Delete a node
  deleteNode(head->next->next);

  // Print the modified linked list
  Node* current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }

  return 0;
}

In this code, we first check if the node to be deleted is nullptr or its next node is nullptr. If either of these conditions is true, we return from the function since it is not possible to delete the node.

Next, we create a pointer nextNode and assign it the value of the next node of the node to be deleted. Then, we update the data of the current node with the data of the next node, and update the next pointer of the current node to point to the next node of the next node. Finally, we delete the memory allocated for the next node.

Let's test this code with a sample linked list and delete a node from it.

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

// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to delete a node from a linked list
void deleteNode(Node* node) {
  if (node == nullptr || node->next == nullptr) {
    return;
  }

  Node* nextNode = node->next;
  node->data = nextNode->data;
  node->next = nextNode->next;
  delete nextNode;
}

int main() {
  // Create a linked list
  Node* head = new Node(1);
  head->next = new Node(2);
  head->next->next = new Node(3);
  head->next->next->next = new Node(4);

  // Print the original linked list
  Node* current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }

  // Delete a node
  deleteNode(head->next->next);

  // Print the modified linked list
  current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }

  return 0;
}
```

Deleting a node from a linked list involves updating the pointers of the previous and next nodes to bypass the node to be deleted.

To find the middle element of a linked list, we can use the slow and fast pointer approach. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

Here's an example C++ code to find the middle element of a linked list:

#include <iostream>
using namespace std;

// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to find the middle element of a linked list
Node* findMiddle(Node* head) {
  if (head == nullptr) {
    return nullptr;
  }

  Node* slow = head;
  Node* fast = head;

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

  return slow;
}

int main() {
  // Create a linked list
  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);

  // Find the middle element
  Node* middle = findMiddle(head);

  if (middle != nullptr) {
    cout << "The middle element is: " << middle->data << endl;
  } else {
    cout << "The list is empty." << endl;
  }

  return 0;
}

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

// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to find the middle element of a linked list
Node* findMiddle(Node* head) {
  if (head == nullptr) {
    return nullptr;
  }

  Node* slow = head;
  Node* fast = head;

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

  return slow;
}

int main() {
  // Create a linked list
  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);

  // Find the middle element
  Node* middle = findMiddle(head);

  if (middle != nullptr) {
    cout << "The middle element is: " << middle->data << endl;
  } else {
    cout << "The list is empty." << endl;
  }

  return 0;
}
```

To find the middle element of a linked list, we can use the _______________ approach. The slow pointer moves ________ node at a time, while the fast pointer moves ________ nodes at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

To sort a linked list, we can use various sorting algorithms such as merge sort, bubble sort, or insertion sort. Here, we will implement merge sort to sort a linked list.

The merge sort algorithm for sorting a linked list can be divided into three steps:

1. Divide: Divide the linked list into two halves using the fast and slow pointer technique.
2. Conquer: Recursively sort the two halves of the linked list using merge sort.
3. Merge: Merge the two sorted halves of the linked list into a single sorted list using a merge function.

Let's take a look at an example implementation of merge sort for a linked list in C++:

#include <iostream>
using namespace std;

// Node definition
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to insert a new node at the beginning of the list
void insertAtBeginning(Node** head, int value) {
  Node* newNode = new Node(value);
  newNode->next = *head;
  *head = newNode;
}

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

int main() {
  // Create a linked list
  Node* head = nullptr;
  insertAtBeginning(&head, 5);
  insertAtBeginning(&head, 10);
  insertAtBeginning(&head, 3);
  insertAtBeginning(&head, 8);

  // Print the linked list
  cout << "Linked List: ";
  printList(head);

  return 0;
}

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

// Node definition
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

// Function to insert a new node at the beginning of the list
void insertAtBeginning(Node** head, int value) {
  Node* newNode = new Node(value);
  newNode->next = *head;
  *head = newNode;
}

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

int main() {
  // Create a linked list
  Node* head = nullptr;
  insertAtBeginning(&head, 5);
  insertAtBeginning(&head, 10);
  insertAtBeginning(&head, 3);
  insertAtBeginning(&head, 8);

  // Print the linked list
  cout << "Linked List: ";
  printList(head);

  return 0;
}
```

Which sorting algorithm can be used to sort a linked list efficiently?

Generating complete for this lesson!