Gain insights into array and linked list-based implementations, delve into advanced structures like skiplists and trees, and explore template-based collections for efficient data optimization and retrieval.

java.tar.gz

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches.

In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement a variety of trees and graphs, and data structures related to bits of an integer. Toward the end of the course, you’ll learn the implementation of structures based on external storage.

After completing this course, you’ll be able to create reusable programs with template-based collections that can efficiently analyze how to optimize the storage and retrieval of very large amounts of data. Overall, this course will enhance your productivity and performance as a software developer.

Data Structures with Generic Types in C++

## Task
Here is the task that implements a version of the merge-sort algorithm that sorts a `DLList` without using an auxiliary array.

## Solution

The code implements the merge-sort algorithm for a doubly linked list.






#include <iostream>
#include <functional>
using namespace std;

template<typename T>
class Node {
public:
    T data;
    Node<T>* prev;
    Node<T>* next;

    Node(const T& data) : data(data), prev(nullptr), next(nullptr) {}
};

template<typename T>
class MergeSortDLL {
private:
    Node<T>* head;
    function<bool(const T&, const T&)> compare;

public:
    MergeSortDLL(const function<bool(const T&, const T&)>& compare)
        : head(nullptr), compare(compare) {}

    void add(const T& data) {
        Node<T>* newNode = new Node<T>(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node<T>* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
            newNode->prev = current;
        }
    }

    void mergeSort() {
        head = mergeSort(head);
    }

    Node<T>* mergeSort(Node<T>* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        Node<T>* middle = getMiddle(head);
        Node<T>* nextOfMiddle = middle->next;
        middle->next = nullptr;

        Node<T>* left = mergeSort(head);
        Node<T>* right = mergeSort(nextOfMiddle);

        return merge(left, right);
    }

    Node<T>* merge(Node<T>* left, Node<T>* right) {
        Node<T>* result = nullptr;

        if (left == nullptr) {
            return right;
        }
        if (right == nullptr) {
            return left;
        }

        if (compare(left->data, right->data)) {
            result = left;
            result->next = merge(left->next, right);
            result->next->prev = result;
        } else {
            result = right;
            result->next = merge(left, right->next);
            result->next->prev = result;
        }

        return result;
    }

    Node<T>* getMiddle(Node<T>* head) {
        if (head == nullptr) {
            return nullptr;
        }

        Node<T>* slow = head;
        Node<T>* fast = head->next;

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

        return slow;
    }

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

int main() {
    MergeSortDLL<int> mergeSortDLL([](const int& a, const int& b) {
        return a <= b;
    });

    mergeSortDLL.add(5);
    mergeSortDLL.add(2);
    mergeSortDLL.add(9);
    mergeSortDLL.add(1);
    mergeSortDLL.add(3);
    mergeSortDLL.add(6);

    cout << "Original List: ";
    mergeSortDLL.printList();

    mergeSortDLL.mergeSort();

    cout << "Sorted List: ";
    mergeSortDLL.printList();

    return 0;
}


## Explanation

Let’s focus on the detailed explanation of the code:

* **Line 22:** The `MergeSortDLL` class is a template class that implements a doubly linked list and performs a merge sort algorithm on its elements.

* **Line 23:** The constructor of `MergeSortDLL` takes a `compare()` function as a parameter. This function is used to determine the sorting order of the elements in the list. It initializes the `head` pointer of the doubly linked list to `nullptr`.

* **Lines 25–37:** The `add()` method adds a new node with the specified data to the end of the doubly linked list. It creates a new `Node` object, assigns the data, and then appends it to the list by traversing to the last node and updating the `next` and `prev` pointers accordingly.

* **Lines 43–48:** The `mergeSort()` method triggers the merge sort algorithm on the doubly linked list. It calls the private `mergeSort()` method and assigns its return value to the `head` pointer, effectively updating the list with the sorted order. The `mergeSort()` method is the recursive part of the merge-sort algorithm. It takes a `Node` pointer representing the head of a sublist and returns the sorted sublist. The method uses a divide-and-conquer approach. If the sublist has zero or one element, it is already sorted and returned as is. Otherwise, it finds the middle node using the `getMiddle()` method, divides the sublist into two halves, recursively sorts each half, and then merges them together using the `merge` method.

* **Lines 58–76:** The private `merge()` method merges two sorted sublists (left and right) and returns the resulting sorted sublist. It takes the left and right pointers as parameters and compares the data of the nodes to determine the order. It creates a new `result` pointer and assigns it to the smaller node between `left` and `right`. Then, it recursively merges the remaining nodes by updating the `next` and `prev` pointers accordingly.

* **Lines 81–94:** The private `getMiddle()` method finds the middle node of a sublist using the "`slow` and `fast` pointer" technique. It takes the head pointer as a parameter and initializes two pointers, `slow` and `fast`, both pointing to the `head`. The `slow` pointer moves one node at a time, while the `fast` pointer moves two nodes at a time. When the `fast` pointer reaches the end of the sublist, the `slow` pointer will be at the middle node, which is returned.

* **Lines 97–104:** The `printList()` method traverses the doubly linked list starting from the `head` and prints the data of each node. It is used to display the original and sorted lists.

The `main()` function demonstrates the usage of the `MergeSortDLL` class. It creates an instance of `MergeSortDLL` with a lambda function for comparison, adds elements to the list, prints the original list, performs merge-sort, and prints the sorted list.


Solve a task implementing an updated version of the merge-sort algorithm.


Overview

Array-Based Lists

Linked Lists

Skiplists

Hash Tables

Binary Trees

Random Binary Search Trees

Scapegoat Trees

Red-Black Trees

Heaps

Sorting Algorithms

Graphs

Data Structures for Integers

External Memory Searching

Wrap Up

Solution: Sorting Algorithms

Task