Linked List Exercises

These exercises are based on dll.h, int_sll.h and ordered_dll.h.

Exercise 8: void reverse()
Exercise 9: T get_at_index(int index) const
Exercise 10: DLList<T> sublist(int index1, int index2) const
Exercise 11: void remove(int index1, int index2)
Exercise 12: void remove_all(const T& val)
Exercise 13: DLList find_common(const DLList& other) const
Exercise 14: void remove_duplicates()

Exercise 1

Implement the following member function of class List, which checks if a singly-linked list is sorted.

bool is_sorted() const;

Solution

bool List::is_sorted() const 
{
    if (is_empty())
        return true;

    for (Node* curr = head; curr->next != nullptr; curr = curr->next)
        if (curr->val > curr->next->val)
            return false;

    return true;
}

Exercise 2

Implement the following member function of class List, which returns the maximum element in a singly-linked list. If the list is empty, the function should throw an exception.

int get_max() const;

Solution

int List::get_max() const 
{
    if (is_empty())
        throw string("ERROR: Attempting to get the max in an empty list");
  
    Node* max_node = head;
    for (Node* curr = head->next; curr != nullptr; curr = curr->next)
        if (curr->val > max_node->val)
            max_node = curr;
  
    return max_node->val;
}

Exercise 3

Implement the following member function of class List, which sorts the singly-linked list using selection sort.

void selection_sort();

Solution

void List::selection_sort() 
{
    for (Node* ptr1 = head; ptr1 != tail; ptr1 = ptr1->next) {
        // find the minimum from ptr1 to the tail
        Node* min_ptr = ptr1;
        for (Node* ptr2 = ptr1->next; ptr2 != nullptr; ptr2 = ptr2->next) {
            if (ptr2->val < min_ptr->val)
                min_ptr = ptr2;
        }

        swap(ptr1->val, min_ptr->val);  
    }
}

Exercise 4

Implement the following member function of class List, which returns true if the list contains a sequence of 3 consequetive values equal to val.

bool check_seq3(int val) const;

Example: check_seq3(9) is true for the list 1, 2, 5, 2, 9, 9, 9, 5 and the list 9, 9, 9, 9, 9, 9 but not for the list 1, 9, 1, 9, 1, 9 or the list 9, 9.

Solution

bool List::check_seq3(int val) const
{
    // if the list has <= 2 elements
    if (head == tail || head->next == tail)
        return false;
        
    Node* curr = head;
    while (curr->next->next != nullptr) {
        if (curr->val == val && curr->next->val == val && curr->next->next->val == val)
            return true;
        curr = curr->next;
    }
    
    return false;
}

Exercise 5

Implement the following member function of class List, which returns true if val appears k times in the list in consecutive nodes and false otherwise.

bool check_seq(int k, int val) const;

Example: check_seq(3, 9) is true for the list 1, 2, 5, 2, 9, 9, 9, 5 and the list 9, 9, 9, 9, 9, 9 but not for the list 1, 9, 1, 9, 1, 9 or the list 9, 9.

Solution

bool List::check_seq(int k, int val) const
{
    if (k < 0)  return false;
    if (k == 0) return true;

    int count = 0;
    Node* curr = head;
    while (curr != nullptr) {
        if (curr->val != val)
            count = 0;
        else 
            count++;
        
        if (count == k) 
            return true;
        else            
            curr = curr->next;
    }

    return false;
}

Exercise 6

Implement the following member function of class List, which prints the contents of the singly-list in reverse.

void print_reverse(Node* node);

Assume that this function is called as follows:

print_reverse(head);

Solution

void List::print_reverse(Node* node) 
{
    if (node == nullptr)
        return;
    print_reverse(node->next);
    cout << node->val << " ";
}

Exercise 7

Implement the following member function of class List, which reverses the singly-linked list.

void reverse();

Solution # 1

void List::reverse() {
    List temp_list;

    while (!is_empty()) {
        temp_list.add_to_head(head->val);
        remove_head();
    }

    while (!temp_list.is_empty()) {
        add_to_tail(temp_list.head->val);
        temp_list.remove_head();
    }
}

Solution # 2

void List::reverse() {
    Node* prev = nullptr;
    Node* curr = head;

    while (curr != nullptr) {
        Node* temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }

    swap(head, tail);}

Solution # 3 (for recursion fans)

void List::reverse(Node* first) 
{
    if (first == nullptr || first == tail)
        return;

    head = head->next;
    reverse(head);
    add_to_tail(first->val);
    delete first;
}

void List::reverse() {
    reverse(head);
}

Solution # 4 (for recursion fans)

explanation: https://static.us.edusercontent.com/files/lsgyClOC9HqQgPYpusojm1ls

void List::reverse(Node *prev, Node *curr)
{
    if (curr->next == nullptr) {
        swap(head, tail);
        tail->next = nullptr;
        head->next = prev;
        return;
    }
    else
        reverse(prev->next, curr->next);    

    curr->next = prev;
}

void List::reverse() 
{
    if (head == tail)
        return;
    reverse(head, head->next)
}

Exercise 8

Implement the following member function of class DLList, which reverses the doubly-linked list.

void reverse();

Solution

template <class T>
void DLList<T>::reverse() 
{
    if (head == tail) // 0 or 1 nodes
        return;

    DLLNode<T>* ptr1 = head;
    DLLNode<T>* ptr2 = tail;  

    //     (odd size)        (even size)  
    while (ptr1 != ptr2 && ptr1->prev != ptr2) {
        T temp = ptr1->val;    
        ptr1->val = ptr2->val;
        ptr2->val = temp;
        ptr1 = ptr1->next;
        ptr2 = ptr2->prev;
    }
}

Exercise 9

Implement the following member function of class DLList, which returns the value at the given index in the doubly-linked list, where the head is assumed to be at index 0.

T get_at_index(int index) const;

If the index is invalid, the function should throw an exception.

Solution

template <class T>
T DLList<T>::get_at_index(int index) const 
{  
    if (index < 0)
        throw string("ERROR: Invalid index passed to get_at_index()");
    
    int count = 0;
    DLLNode<T>* curr = head;
    while (curr != nullptr) {
        if (count == index)
            return curr->val;
        curr = curr->next;
        count++;
    }

    // if execution reaches here, then index is larger than
    // the last index in the list    
    throw string("ERROR: Invalid index passed to get_at_index()");
}

Exercise 10

Implement the following member function of class DLList, which returns the values in the nodes between the given indices (inclusive).

DLList sublist(int index1, int index2) const;

The function should throw an exception if any of the indices is invalid. If index2 is larger than or equal to the number of nodes in the list, return all the values from index1 to the tail.

Solution

template <class T>
DLList<T> DLList<T>::sublist(int index1, int index2) const 
{  
    if (index1 < 0 || index2 < 0 || index1 > index2)
        throw string("ERROR: Invalid index passed to sublist()");

    // get to index1  
    int count = 0;  
    DLLNode<T>* curr = head;
    while (curr != nullptr) {
        if (count == index1)
            break;
        curr = curr->next;
        count++;
    }

    // if null is reached before reaching index1
    if (curr == nullptr)
        throw string("ERROR: Invalid index passed to sublist()");

    // collect all the values in the nodes between index1  
    // and index2 (stop if the end of the list is reached  
    // before reaching index2)  
    DLList<T> result;  
    while (curr != nullptr && count <= index2) {
        result.add_to_tail(curr->val);
        curr = curr->next;
        count++;  
    }

    return result;
}

Exercise 11

Implement the following member function of class DLList, which removes the nodes between the given indices (inclusive).

void remove(int index1, int index2);

The function should throw an exception if any of the indices is invalid. If index2 is larger than or equal to the number of nodes in the list, remove all the nodes from index1 to the tail.

Solution

template <class T>
void DLList<T>::remove(int index1, int index2) 
{  
    if (index1 < 0 || index2 < 0 || index1 > index2)        
        throw string("ERROR: Invalid index passed to sublist()");     

    DLList<T> new_list;      

    // get all the nodes that are not between index1 and index2 inclusive.  
    int count = 0;   
    DLLNode<T>* curr = head;    
    while (curr != nullptr) {        
        if (count < index1 || count > index2)
            new_list.add_to_tail(curr->val);
        curr = curr->next;
        count++;
    }      

    // if curr == nullptr and count <= index1, then index1  
    // is outside the range of valid indices.  
    if (count <= index1)      
        throw string("ERROR: Invalid index passed to sublist()");      

    *this = new_list;
}

Exercise 12

Implement the following member function of class DLList, which removes all the occurrences of the given value from the doubly-linked list.

void remove_all(const T& val);

Solution 1

template <class T>
void DLList<T>::remove_all(const T& val) 
{
    if (is_empty())
        return;

    while (head->val == val) {
        remove_head();
        if (head == nullptr)
            return;
    }

    while (tail->val == val)
        remove_tail();

    DLLNode<T>* curr = head->next;

    while (curr != nullptr) {
        if (curr->val == val) {
            DLLNode<T>* succ = curr->next;
            DLLNode<T>* pred = curr->prev;
            succ->prev = pred;
            pred->next = succ;
            delete curr;
            curr = succ;
        } else
            curr = curr->next;    
    }
}

Solution 2

template <class T>
void DLList<T>::remove_all(const T& val) 
{
    DLList<T> temp_list;

    while (!is_empty()) {
        if (head->val != val)
            temp_list.add_to_tail(head->val);
        remove_head();
    }

    *this = temp_list;
}

Exercise 13

Implement the following member function of class DLList, which returns all the common values between the current doubly-linked list and the recived doubly-linked list.

DLList find_common(const DLList& other) const;

Note 1. No value appears in the same list more than once.

Note 2. An O(n^2) solution is fine.

Solution

template <class T>
DLList<T> DLList<T>::find_common(const DLList<T>& other) const 
{
    DLList<T> result;

    if (is_empty() || other.is_empty())    
        return result;

    for (DLLNode<T>* ptr1 = head; ptr1 != nullptr; ptr1 = ptr1->next) {    
        // search for ptr1->val in the other list
        for (DLLNode<T>* ptr2 = other.head; ptr2 != nullptr; ptr2 = ptr2->next) {
            if (ptr1->val == ptr2->val) {
                result.add_to_tail(ptr1->val);
                break;
            }
        }
    }

    return result;
}

Exercise 14

Implement the following member function of class OrderedDLList, which removes all duplicate elements in the list. After calling this function, the list must contain only distinct elements.

void remove_duplicates();

Example: If the list is 1, 1, 1, 2, 3, 4, 4, 5, 5, 5 it should become 1, 2, 3, 4, 5.

Solution 1

template <class T>
void OrderedDLList<T>::remove_duplicates() 
{
    // 0 or 1 elements
    if (head == tail) 
        return;
        
    DLLNode<T>* curr = head->next;
    DLLNode<T>* pred = head;
    
    while (curr != nullptr) {
        if (pred->val == curr->val) {
            if (curr == tail) {
                remove_tail();
                return;
            } else {
                curr = curr->next;
                delete curr->prev;
                curr->prev = pred;
                pred->next = curr;
            }
        } else {
            curr = curr->next;
            pred = pred->next;
        }
    }
}

Solution 2

template <class T>
void OrderedDLList<T>::remove_duplicates() 
{
    OrderedList<T> temp_list;

    DLLNode<T>* curr = head;
    while (curr != nullptr) {
        if (temp_list.is_empty() || curr->val != temp_list.tail->val)
            temp_list.add_to_tail(curr->val);
        curr = curr->next;
    }

    *this = temp_list;
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

list_exercises.md

list_exercises.md

Linked List Exercises

Contents

Exercise 1

Solution

Exercise 2

Solution

Exercise 3

Solution

Exercise 4

Solution

Exercise 5

Solution

Exercise 6

Solution

Exercise 7

Solution # 1

Solution # 2

Solution # 3 (for recursion fans)

Solution # 4 (for recursion fans)

Exercise 8

Solution

Exercise 9

Solution

Exercise 10

Solution

Exercise 11

Solution

Exercise 12

Solution 1

Solution 2

Exercise 13

Solution

Exercise 14

Solution 1

Solution 2

Files

list_exercises.md

Latest commit

History

list_exercises.md

File metadata and controls

Linked List Exercises

Contents

Exercise 1

Solution

Exercise 2

Solution

Exercise 3

Solution

Exercise 4

Solution

Exercise 5

Solution

Exercise 6

Solution

Exercise 7

Solution # 1

Solution # 2

Solution # 3 (for recursion fans)

Solution # 4 (for recursion fans)

Exercise 8

Solution

Exercise 9

Solution

Exercise 10

Solution

Exercise 11

Solution

Exercise 12

Solution 1

Solution 2

Exercise 13

Solution

Exercise 14

Solution 1

Solution 2