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 the course’s GitHub repository.

Starting from the code in the linkedlist.h file created in class, add the operations described below to the generic LinkedList<T> class.

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

Operación Descripción
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 is equivalent to insert_front when index is equal to 0. Similarly, this function is equivalent to insert_back 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 is equivalent to remove_front when index is equal to 0. Similarly, this function is equivalent to remove_back 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, ...]"

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
 * Implementation of the LinkedList class.
 *
 * Date: 26-Sep-2022
 * 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 Tuesday, September 26.