Description
For this lab we will complete our implementation of a Singly Linked List and a Doubly Linked List
Implement the following classes and functions:
| /* SLL = Singly Linked List */ template<class T> class SLList { private:
/* Class exercise to fill in. */ public: /* Empty constructor shall create an empty Linked List! */ SLList(); /* Do a deep copy of sll into the this. * Note: This one uses a reference to a Singly Linked List! */ SLList(const SLList<T> &sll); /* Deconstructor shall free up memory */ ~SLList(); /* Return the current length of the Singly Linked List */ int getLength() const; /* Insert at the end of the list.*/ bool append(const T &val); /* Insert val at position pos. * Return true if successful (it can be placed.) * Otherwise return false. */ bool insert(const int pos, const T &val); /* Print out the Singly Linked List */ void print() const; /* Remove the first instance of val * Return true if found and removed. * Otherwise return false. */ bool remove(const T &val); /* Retrieves the element at position pos */ T& operator[](const int pos); |
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
32
33
34
35
36
37
38
39
40
41
42/* Returns if the two lists contain the same elements in the 43* same order.
44*/
45bool operator==(const SLList<T> &list) const;
46};
47
48
49/* DLL = Doubly Linked List */
50template<class T>
51class DLList { 52private:
53/* Class exercise to fill in. */
54public:
55/* Empty constructor shall create an empty Linked List! */ 56DLList();
57
58/* Do a deep copy of dll into the this.
59* Note: This one uses a reference to a Singly Linked List!
60*/
61DLList(const DLList<T> &dll);
62
63/* Deconstructor shall free up memory */ 64~DLList();
65
66/* Return the current length of the Singly Linked List */
67int getLength() const;
68
69/* Insert at the end of the list.*/
70bool append(const T &val);
71
72/* Insert val at position pos.
73* Return true if successful (it can be placed.) 74* Otherwise return false.
75*/
76bool insert(const int pos, const T &val);
77
78/* Print out the Singly Linked List */
79void print() const;
80
81/* Remove the first instance of val 82* Return true if found and removed. 83* Otherwise return false.
84*/
85bool remove(const T &val);
86
87/* Retrieves the element at position pos */
| }; | T& operator[](const int pos);
/* Returns if the two lists contain the same elements in the * same order. */ bool operator==(const DLList<T> &list) const; |
88
89
90
91
92
93
94
Some Questions to Answer:
- What is the performance difference for append between an Array, SLList, and DLList?
- What is the performance difference for insert between an Array, SLList, and DLList?
- What is the performance difference for operator[] between an Array, SLList, and DLList?
- What is the performance difference for remove between an Array, SLList, and DLList?
- What is the performance difference for search between an Array, SLList, and DLList? You may answer in the comments of your code or in a separate .txt/.doc document.
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code. We will be creating some of these test cases in class.
Memory Management:
Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code!
