logo Use CA10RAM to get 10%* Discount.
Order Nowlogo

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).

INSTRUCTIONS TO CANDIDATES
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

1068 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

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

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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

1068 Times Downloaded

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Um e HaniScience

822 Answers

Hire Me
expert
Muhammad Ali HaiderFinance

995 Answers

Hire Me
expert
Husnain SaeedComputer science

657 Answers

Hire Me
expert
Atharva PatilComputer science

743 Answers

Hire Me
July
January
February
March
April
May
June
July
August
September
October
November
December
2025
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
SunMonTueWedThuFriSat
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
00:00
00:30
01:00
01:30
02:00
02:30
03:00
03:30
04:00
04:30
05:00
05:30
06:00
06:30
07:00
07:30
08:00
08:30
09:00
09:30
10:00
10:30
11:00
11:30
12:00
12:30
13:00
13:30
14:00
14:30
15:00
15:30
16:00
16:30
17:00
17:30
18:00
18:30
19:00
19:30
20:00
20:30
21:00
21:30
22:00
22:30
23:00
23:30