To make things easier, you’ll implement a list of int, rather than a template class. #pragma once /* dlist.h Doubly-linked lists of ints */ class dlist { public: dlist() { } struct node { int value; node* next; node* prev; }; node* head() const { return _head; } node* tail() const { return _tail; } // **** Implement ALL the following methods **** // Returns the node at a particular index (0 is the head).

ANSWER ALL QUESTIONS

In this assignment, you will implement a doubly-linked list class, together with some list operations.

To make things easier, you’ll implement a list of int, rather than a template class. #pragma once /* dlist.h Doubly-linked lists of ints */ class dlist { public: dlist() { } struct node { int value; node* next; node* prev; }; node* head() const { return _head; } node* tail() const { return _tail; } // **** Implement ALL the following methods **** // Returns the node at a particular index (0 is the head). If n >= size() // return nullptr; if n < 0, return the head of the list. // Must run in O(n) time. node* at(int n) const; // Insert a new value, after an existing one. If previous == nullptr, then // the list is assumed to be empty. // Must run in O(1) time. void insert(node *previous, int value); // Delete the given node. Should do nothing if which == nullptr. // Must run in O(1) time. void remove(node* which); // Add a new element to the *end* of the list // Must run in O(1) time. void push_back(int value); // Add a new element to the *beginning* of the list // Must run in O(1) time. void push_front(int value); // Remove the first element. // If the list is empty, do nothing. // Must run in O(1) time void pop_front(); // Remove the last element. // If the list is empty, do nothing. // Must run in O(1) time void pop_back(); // Get the size of the list // Should run in O(n) time at the worst int size() const; // Returns true if the list is empty // Must run in O(1) time bool empty() const; private: node* _head = nullptr; node* _tail = nullptr; //

Add any other private members you need }; // **** Implement ALL the following functions **** /* a == b Compares two lists for equality, returning true if they have the same elements in the same positions. (Hint: it is *not* enough to just compare pointers! You have to compare the values stored in the nodes.) Must run in O(m) time, where m is the length of the shorter of the two lists. */ bool operator== (const dlist& a, const dlist& b); /* a + b Returns a new list consisting of all the elements of a, followed by all the elements of b (i.e., the list concatenation). Must run in O(n) time in the length of the result (i.e., the length of a plus the length of b). */ dlist operator+ (const dlist& a, const dlist& b); /* reverse(l) Returns a new list that is the *reversal* of l;

that is, a new list containing the same elements as l but in the reverse order. Must run in O(n) time. */ dlist reverse(const dlist& l); (You can download this header file.) You should save the above into dlist.hpp, and put the implementations of the functions (and any methods that you don’t want to implement in the class body) into dlist.cpp. (If you want to, you can implement everything in dlist.hpp by writing the functions as inline, thus creating a “header-only” list library.) You should download assign2_test.cpp, the test-runner for this assignment, and use it to test your code.

As before, it provides a main which will run all the different functions and make sure they are implemented correctly. However, it’s possible in this assignment that some mistakes might show up not as failing tests, but as segment violations (or null-pointer dereferences); i.e., your program will crash instead of the test printing a FAILED message. You can find both these files on the server in the path /usr/local/class/src. E.g. you could create the directory and copy the files with mkdir ~/cs133/assign2/ cp /usr/local/class/src/assign2_test.cpp ~/cs133/assign2/ cp /usr/local/class/src/dlist.hpp ~/cs133/assign2/ On the server, you can diagnose segfaults by running your program like this: catchsegv ./assign2_test If your program crashes,

this will print out a backtrace which shows, among other things, the line number on which the error occurred. Of course, it’s also possible that your code might mess up the list structure to the point where the test runner gets into an infinite loop. If that happens, look at the most recent message printed for a clue as to where the problem is. Things to watch out for Implementations that do not meet the time complexity requirements.

E.g., an O(n2) O ( n 2 ) implementation where O(n) O ( n ) is required. Failing to update the prev pointers when modifying the list structure.

Almost every list-modifying method will have to update the prev pointer in an existing node. Modifying the input lists in operator+ or reverse. Both of these must leave their input lists totally unchanged!

Submission

Save your work in a directory on the server named cs133/assign2/.

Expert's Answer

Related Questions

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of