Exercises

1.

Allocate 4 list nodes on the heap containing the values 1, 2, 3, 4. Connect them in a linked list (in numerical order). Make a pointer to the first node called start.

🔗

2.

Write the removeStart function for the Simple Linked List. Make sure to delete the node from memory.

🔗

3.

Write the listSize function for the Simple Linked List. You should walk through the nodes and count them, then return the count.

🔗

4.

Finish the insertAt function for the Simple Linked List. It should insert a new node at the specified index. You do not have to worry about bad indexes.

🔗

Hint 1.

To insert at index i, you need to traverse the list to position i-1 so you can update the next pointer of the node before location i.

🔗

Hint 2.

You will have to update two next pointers when inserting a new node.

🔗

5.

Finish the removeStart function for the Linked List (with size and tail). Make sure to consider the case where there is just a single node.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import LinkedList;

#include <iostream>
using namespace std;
^^^!
          
template<typename T>
void LinkedList<T>::removeStart() {
  if (head == nullptr)
    throw out_of_range("Can't remove from empty list");

// TODO - Remove first item in list

}
===!
template<typename T>
void LinkedList<T>::clear() {
  // placeholder implementation
}

void buildTestIntList(LinkedList<int>& list) {
  list.insertStart(3);
  list.insertStart(2);
  list.insertStart(1);
}

TEST_CASE("LL/removeStart") {
  LinkedList<int> test_list;
  buildTestIntList(test_list); // 1, 2, 3

int startNodeCount = ListNode<int>::nodeCount;

test_list.removeStart();
  REQUIRE(test_list.size == 2);
  REQUIRE(startNodeCount - ListNode<int>::nodeCount == 1);

test_list.removeStart();
  REQUIRE(test_list.size == 1);
  REQUIRE(test_list.retrieveAt(0) == 3);
  REQUIRE(startNodeCount - ListNode<int>::nodeCount == 2);

test_list.removeStart();
  REQUIRE(test_list.size == 0);
  REQUIRE(test_list.head == nullptr);
  REQUIRE(test_list.tail == nullptr);
  REQUIRE(startNodeCount - ListNode<int>::nodeCount == 3);
}

🔗

6.

Finish the insertEnd function for the Linked List (with size and tail).

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import LinkedList;

#include <iostream>
using namespace std;
^^^!
          
template<typename T>
void LinkedList<T>::insertEnd(const T& value) {
    ListNode<T>* newNode = new ListNode<T>(value);
    if (size == 0) {
      // node is both head and tail
    } else {
      // attach to end of list and update tail
    }
    size++;
}
===!
template<typename T>
void LinkedList<T>::clear() {
  // placeholder implementation
}

void buildTestIntList(LinkedList<int>& list) {
  list.insertStart(3);
  list.insertStart(2);
  list.insertStart(1);
}

TEST_CASE("LL/InsertEnd") {
  LinkedList<int> test_list;
  buildTestIntList(test_list); // 1, 2, 3

test_list.insertEnd(10);
  REQUIRE(test_list.size == 4);
  REQUIRE(test_list.retrieveAt(3) == 10);
  REQUIRE(test_list.tail->data == 10);      // check tail pointer
  REQUIRE(test_list.tail->next == nullptr); // check after tail

test_list.insertEnd(20);
  REQUIRE(test_list.size == 5);
  REQUIRE(test_list.retrieveAt(4) == 20);
  REQUIRE(test_list.tail->data == 20);      // check tail pointer
  REQUIRE(test_list.tail->next == nullptr); // check after tail
}

TEST_CASE("LL/InsertEndEmptyList") {
  LinkedList<int> test_list;

test_list.insertEnd(10);
  REQUIRE(test_list.head != nullptr); // check head pointer
  REQUIRE(test_list.size == 1);
  REQUIRE(test_list.retrieveAt(0) == 10);
  REQUIRE(test_list.head->data == 10);      // check head pointer
  REQUIRE(test_list.tail->data == 10);      // check tail pointer
  REQUIRE(test_list.tail->next == nullptr); // check after tail
}

🔗

7.

Write the clear function for the Linked List (with size and tail).

🔗

You can copy/paste in your removeStart from Exercise 27.17.5 to help with this implementation.

🔗

8.

Write the copyFrom function for the Linked List (with size and tail).

🔗

You should use your insertEnd from Exercise 27.17.6 to simplify your implementation. You may assume the list starts out as a valid empty list.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import LinkedList;

#include <iostream>
using namespace std;
^^^!
          
template<typename T>
void LinkedList<T>::copyFrom(const LinkedList<T>& other) {
  // Your code here
}
===!
template<typename T>
void LinkedList<T>::clear() {
  // placeholder implementation
}

template<typename T>
LinkedList<T>::LinkedList(const LinkedList<T>& other) {
  //copy constructor that uses your copyFrom
  head = nullptr;
  tail = nullptr;
  size = 0;
  copyFrom(other);
}

void buildTestIntList(LinkedList<int>& list) {
  list.insertStart(3);
  list.insertStart(2);
  list.insertStart(1);
}

TEST_CASE("LL/CopyConstructor") {
  LinkedList<int> test_list;
  buildTestIntList(test_list); // 1, 2, 3

int startNodeCount = ListNode<int>::nodeCount;

LinkedList<int> copy(test_list);

REQUIRE(copy.retrieveAt(0) == 1);
  REQUIRE(copy.retrieveAt(1) == 2);
  REQUIRE(copy.retrieveAt(2) == 3);
  REQUIRE(copy.size == 3);
  REQUIRE(ListNode<int>::nodeCount - startNodeCount == 3);

// Make sure changing one does not change the other
  test_list.insertStart(0);
  REQUIRE(copy.retrieveAt(0) == 1);
  REQUIRE(copy.retrieveAt(1) == 2);
  REQUIRE(copy.retrieveAt(2) == 3);
  REQUIRE(copy.size == 3);
}

🔗

9.

Write the constructor for the Doubly Linked List. You need to create an empty list with dummy nodes for head and tail that are connected together.

🔗

To make a new node with a dummy (default) value, you can use ListNode<T>(T{})

🔗

10.

Write the removeEnd function for the Doubly Linked List. It should remove the node before the dummy tail node. You will have to add your constructor from Exercise 27.17.9.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import DoublyLinkedList;

#include <iostream>
using namespace std;
^^^!

// Your constructor here

template<typename T>
void DoublyLinkedList<T>::removeEnd() {
  if (size == 0)
    throw out_of_range("Can't remove from empty list");

// Your code here
}
===!
TEST_CASE("DLL/removeEnd") {
  DoublyLinkedList<int> test_list;
  test_list.insertStart(40);
  test_list.insertStart(30);
  test_list.insertStart(20);
  test_list.insertStart(10);

int startNodeCount = ListNode<int>::nodeCount;

test_list.removeEnd();

REQUIRE(test_list.size == 3);
  REQUIRE(test_list.retrieveAt(0) == 10);
  REQUIRE(test_list.retrieveAt(2) == 30);
  REQUIRE(startNodeCount - ListNode<int>::nodeCount == 1);

test_list.removeEnd();
  test_list.removeEnd();

REQUIRE(test_list.size == 1);
  REQUIRE(test_list.retrieveAt(0) == 10);
  REQUIRE(startNodeCount - ListNode<int>::nodeCount == 3);

test_list.removeEnd();

REQUIRE(test_list.size == 0);
  REQUIRE(startNodeCount - ListNode<int>::nodeCount == 4);
}

🔗

Welcome to Programming and Data Structures

Exercises 27.17 Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.