Data Structures

Lab #2: Linked Lists

Objective

During this activity, students will be able to:


Description

This activity must be developed in the pre-assigned teams of two.

NOTE: The files needed to start this lab are available in this tarball file: linkedlist.tgz. To uncompress, type at the Linux terminal:

tar xzf linkedlist.tgz

In the file linkedlist.h, write a generic LinkedList<T> class that implements a circular doubly linked list with the operations described below.

IMPORTANT: Before the definition of each operation you must include a comment that indicates its corresponding time complexity.

Operation Description
LinkedList() Constructor. Create an empty list.
LinkedList(
    std::initializer_list<T>
        args
)
Constructor. Create a list initialized with the elements contained in args
~LinkedList() Destructor. Destroy this list making sure that all its dynamically allocated memory is freed.
bool contains(T value) const Member function. Returns true if value is an element contained in this list, or false otherwise.
void extend(
    const LinkedList<T>&
        other
)
Member function. Append all the elements contained in other to the end of this list.
T get(int index) const Member function. Returns the element contained at the specified index of this list. The first element is at index 0. Throws a std::out_of_range exception if index is out of range (less than 0 or greater or equal to the number of elements in the list).
void insert_at(
    int index,
    T value
)
Member function. Insert value at position index. This function inserts at the front of the list when index is equal to 0. Similarly, this function inserts at the back of the list when index is equal to the number of elements in this list. Throws a std::out_of_range exception if index is out of range (is less than 0 or greater than the number of elements in the list).
void insert_back(T value) Member function. Insert value at the end of this list.
void insert_front(T value) Member function. Insert value at the front of this list.
bool is_empty() const Member function. Returns true if this list is empty, or false otherwise.
T remove_at(int index) Member function. Removes and returns the element at position index. This function removes from the front of the list when index is equal to 0. Similarly, this function removes from the back of the list when index is equal to the number of elements in this list minus one. Throws a std::out_of_range exception if index is out of range (less than 0 or greater or equal to the number of elements in the list).
T remove_back() Member function. Removes and returns the element at the back of this list. Throws a std::length_error exception if the list is empty.
T remove_front() Member function. Removes and returns the element at the front of this list. Throw a std::length_error exception if the list is empty.
int size() const Member function. Returns the number of elements contained in this list.
std::string to_string() const Member function. Returns the representation of this list as a string of characters like this:
"[elem1, elem2, elem3, ...]"

Add the following declarations inside your class’ public section in order to avoid memory related issues produced by the default copy constructor and assignment operator:

LinkedList(const LinkedList& other) = delete;

LinkedList<T>& operator=(const LinkedList& other) = delete;

Test your code using the tests in the file tests.cpp (contains a total of 125 assertions). Also, run the code using valgrind to check for memory leaks and other memory related errors.

Deliverables

Place in a comment at the top of the linkedlist.h source file the authors’ personal information (student ID and name), for example:

/*----------------------------------------------------------
 * Lab #2: Linked Lists
 *
 * Date: 22-Sep-2023
 * Authors:
 *           A01770771 Kamala Khan
 *           A01777771 Carol Danvers
 *----------------------------------------------------------*/

Upload Instructions

To deliver the linkedlist.h file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Friday, September 22.