lOMoARcPSD|19774343

Double Linked List Attempt review

Data Structure (Ho Chi Minh City University of Technology)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Đã bắt đầu vào Chủ nhật, 8 Tháng mười 2023, 7:05 AM

lúc
Tình trạng Đã hoàn thành
Hoàn thành vào Thứ hai, 9 Tháng mười 2023, 8:48 PM
lúc
Thời gian thực 1 ngày 13 giờ
hiện
Điểm 6,00/6,00
Điểm 10,00 của 10,00 (100%)

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 1/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Câu hỏi 1
Chính xác

Điểm 1,00 của 1,00

Implement methods add, size in template class DLinkedList (which implements List ADT) representing the doubly linked list with
type T with the initialized frame. The description of each method is given in the code.

template <class T>

class DLinkedList {
public:
class Node; // Forward declaration
protected:
Node* head;
Node* tail;
int count;
public:
DLinkedList();
~DLinkedList();
void add(const T &e);
void add(int index, const T &e);
int size();
public:
class Node
{
private:
T data;
Node *next;
Node *previous;
friend class DLinkedList<T>;

public:
Node()
{
this->previous = NULL;
this->next = NULL;
}

Node(const T &data)
{
this->data = data;
this->previous = NULL;
this->next = NULL;
}
};

};

In this exercise, we have include <iostream>, <string>, <sstream> and using namespace std.

For example:

Test Result

DLinkedList<int> list; [0,1,2,3,4,5,6,7,8,9]

int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
cout << list.toString();

DLinkedList<int> list; [9,8,7,6,5,4,3,2,1,0]

int size = 10;
for(int idx=0; idx < size; idx++){
list.add(0, idx);
}
cout << list.toString();

Answer: (penalty regime: 0, 0, 0, 5, 10 %)

Reset answer

1 template <class T>

2 void DLinkedList<T>::add(const T& e) {
https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 2/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

2 ▼ void DLinkedList<T>::add(const T& e) {
3 /* Insert an element into the end of the list. */
4 Node * newnode = new Node(e);
5▼ if(tail==nullptr) {
6 head = newnode;
7 tail = newnode;
8 }
9▼ else {
10 tail->next = newnode;
11 newnode->previous = tail;
12 tail = newnode;
13 }
14 count++;
15
16 }
17
18 template<class T>
19 ▼ void DLinkedList<T>::add(int index, const T& e) {
20 /* Insert an element into the list at given index. */
21 Node * newnode = new Node(e);
22 ▼ if(head == nullptr) {
23 head = newnode;
24 tail = newnode;
25 }
26 ▼ else if(index == 0){
27 newnode->next = head;
28 head->previous = newnode;
29 head = newnode;
30 }
31 ▼ else if(index == count){
32 tail->next = newnode;
33 newnode->previous = tail;
34 tail = newnode;
35 ▼ } else {
36 Node * current = head;
37 ▼ for(int i=0;i<index;i++){
38 current = current->next;
39 }
40 Node * prev = current->previous;
41 prev->next = newnode;
42 newnode->previous = prev;
43 newnode->next = current;
44 current->previous = newnode;
45 }
46 count++;
47 }
48
49 template<class T>
50 ▼ int DLinkedList<T>::size() {
51 /* Return the length (size) of list */
52 return this->count;
53 return 0;
54 }

Test Expected Got

 DLinkedList<int> list; [0,1,2,3,4,5,6,7,8,9] [0,1,2,3,4,5,6,7,8,9] 

int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
cout << list.toString();

 DLinkedList<int> list; [9,8,7,6,5,4,3,2,1,0] [9,8,7,6,5,4,3,2,1,0] 

int size = 10;
for(int idx=0; idx < size; idx++){
list.add(0, idx);
}
cout << list.toString();

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 3/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Passed all tests! 

Chính xác
Điểm cho bài nộp này: 1,00/1,00.

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 4/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Câu hỏi 2
Chính xác

Điểm 1,00 của 1,00

Implement methods get, set, empty, indexOf, contains in template class DLinkedList (which implements List ADT) representing
the singly linked list with type T with the initialized frame. The description of each method is given in the code.

template <class T>

class DLinkedList {
public:
class Node; // Forward declaration
protected:
Node* head;
Node* tail;
int count;
public:
DLinkedList();
~DLinkedList();
void add(const T &e);
void add(int index, const T &e);
int size();
bool empty();
T get(int index);
void set(int index, const T &e);
int indexOf(const T &item);
bool contains(const T &item);
public:
class Node
{
private:
T data;
Node *next;
Node *previous;
friend class DLinkedList<T>;

public:
Node()
{
this->previous = NULL;
this->next = NULL;
}

Node(const T &data)
{
this->data = data;
this->previous = NULL;
this->next = NULL;
}
};

};

In this exercise, we have include <iostream>, <string>, <sstream> and using namespace std.

For example:

Test Result

DLinkedList<int> list; 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |
int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
cout << list.get(idx) << " |";
}

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 5/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Test Result

DLinkedList<int> list; [2,5,6,3,67,332,43,1,0,9]

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
list.set(idx, value[idx]);
}
cout << list.toString();

Answer: (penalty regime: 0, 0, 0, 5, 10 %)

Reset answer

1 template<class T>
2 ▼ T DLinkedList<T>::get(int index) {
3 /* Give the data of the element at given index in the list. */
4 if(index>= this->count||index<0) throw std::out_of_range("-1");
5 Node *current = head;
6 ▼ for(int i =0;i<index;i++){
7 current = current->next;
8 }
9 return current->data;
10 }
11
12 template <class T>
13 ▼ void DLinkedList<T>::set(int index, const T& e) {
14 /* Assign new value for element at given index in the list */
15 if(index>= this->count||index<0) throw std::out_of_range("-1");
16 Node *current = head;
17 ▼ for(int i =0;i<index;i++){
18 current = current->next;
19 }
20 current->data = e;
21 }
22
23 template<class T>
24 ▼ bool DLinkedList<T>::empty() {
25 /* Check if the list is empty or not. */
26 if(this->count ==0) return 1;
27 return 0;
28
29 }
30
31 template<class T>
32 ▼ int DLinkedList<T>::indexOf(const T& item) {
33 /* Return the first index wheter item appears in list, otherwise return -1 */
34 Node *current = head;
35 int n=0;
36 ▼ while(current !=nullptr){
37 if (current->data == item ) return n;
38 n++;
39 current = current->next;
40 }
41 return -1;
42 }
43
44 template<class T>
45 ▼ bool DLinkedList<T>::contains(const T& item) {
46 /* Check if item appears in the list */
47 Node *current = head;
48 int n=0;
49 ▼ while(current !=nullptr){
50 if (current->data == item ) return 1;
51 n++;
52 current = current->next;
53 }
54 return 0;
55 }

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 6/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Test Expected Got

 DLinkedList<int> list; 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 | 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 | 
int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
cout << list.get(idx) << " |";
}

 DLinkedList<int> list; [2,5,6,3,67,332,43,1,0,9] [2,5,6,3,67,332,43,1,0,9] 

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};
for(int idx=0; idx < size; idx++){
list.add(idx);
}
for(int idx=0; idx < size; idx++){
list.set(idx, value[idx]);
}
cout << list.toString();

Passed all tests! 

Chính xác
Điểm cho bài nộp này: 1,00/1,00.

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 7/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Câu hỏi 3
Chính xác

Điểm 1,00 của 1,00

Implement Iterator class in class DLinkedList.

Note: Iterator is a concept of repetitive elements on sequence structures. Iterator is implemented in class vector, list in STL container in C++
(https://www.geeksforgeeks.org/iterators-c-stl/). Your task is to implement the simple same class with iterator in C++ STL container.

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 8/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

template <class T>

class DLinkedList
{
public:
class Iterator; //forward declaration
class Node; //forward declaration
protected:
Node *head;
Node *tail;
int count;
public:
DLinkedList() : head(NULL), tail(NULL), count(0){};
~DLinkedList();
void add(const T &e);
void add(int index, const T &e);
T removeAt(int index);
bool removeItem(const T &item);
bool empty();
int size();
void clear();
T get(int index);
void set(int index, const T &e);
int indexOf(const T &item);
bool contains(const T &item);
string toString();
Iterator begin()
{
return Iterator(this, true);
}
Iterator end()
{
return Iterator(this, false);
}
public:
class Node
{
private:
T data;
Node *next;
Node *previous;
friend class DLinkedList<T>;

Iterator begin()
{
return Iterator(this, true);
}
Iterator end()
{
return Iterator(this, false);
}

public:
Node()
{
this->previous = NULL;
this->next = NULL;
}

Node(const T &data)
{
this->data = data;
this->previous = NULL;
this->next = NULL;
}
};
class Iterator
{
private:
DLinkedList<T> *pList;
Node *current;
int index; // is the index of current in pList

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 9/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

public:
Iterator(DLinkedList<T> *pList, bool begin);
Iterator &operator=(const Iterator &iterator);
void set(const T &e);
T &operator*();
bool operator!=(const Iterator &iterator);
void remove();

// Prefix ++ overload
Iterator &operator++();

// Postfix ++ overload
Iterator operator++(int);
};
};

Please read example carefully to see how we use the iterator.

For example:

Test Result

DLinkedList<int> list; 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |
int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
DLinkedList<int>::Iterator it = list.begin();
for(; it != list.end(); it++)
{
cout << *it << " |";
}

DLinkedList<int> list; []
int size = 10;
for (int idx = 0; idx < size; idx++)
{
list.add(idx);
}

DLinkedList<int>::Iterator it = list.begin();
while (it != list.end())
{
it.remove();
it++;
}
cout << list.toString();

DLinkedList<int> list; []
int size = 10;
for (int idx = 0; idx < size; idx++)
{
list.add(idx);
}

DLinkedList<int>::Iterator it = list.begin();
for(; it != list.end(); it++)
{
it.remove();
}
cout << list.toString();

Answer: (penalty regime: 0, 0, 0, 5, 10 %)

Reset answer

1 ▼ /*
2 * TODO: Implement class Iterator's method
3 * Note: method remove is different from SLinkedList, which is the advantage of DLinkedList
4 */
5 template <class T>
6 DLinkedList<T>::Iterator::Iterator(DLinkedList<T> *pList, bool begin)
7▼ {
8 this->pList = pList;
9▼ if(begin == 1) {
10 if(thi Li t ! ll t ){
https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 10/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

10 ▼ if(this->pList != nullptr){
11 this->current = this-> pList->head;
12 index = 0;
13 }
14 else{this->current = nullptr;this->index=-1;}
15 ▼ } else{
16 this->current = nullptr;
17 if(this->pList != nullptr){this->index = this->pList->count; }
18 else this->index = 0;
19 }
20 }
21
22 template <class T>
23 typename DLinkedList<T>::Iterator& DLinkedList<T>::Iterator::operator=(const DLinkedList<T>::Iterator &iterat
24 ▼ {
25 current = iterator.current;
26 index = iterator.index;
27 this->pList = iterator.pList;
28 return *this;
29 }
30
31 template <class T>
32 void DLinkedList<T>::Iterator::set(const T &e)
33 ▼ {
34 if(this->current == nullptr) throw std::out_of_range("Segmentation fault!");
35 this->current->data = e;
36 }
37
38 template<class T>
39 T& DLinkedList<T>::Iterator::operator*()
40 ▼ {
41 if(current == nullptr) throw std::out_of_range("Segmentation fault!");
42 return current->data;
43 }
44
45 template<class T>
46 void DLinkedList<T>::Iterator::remove()
47 ▼ {
48 ▼ /*
49 * TODO: delete Node in pList which Node* current point to.
50 * After that, Node* current point to the node before the node just deleted.
51 * If we remove first node of pList, Node* current point to nullptr.
52 * Then we use operator ++, Node* current will point to the head of pList.
53 */
54 if(current ==nullptr) throw std::out_of_range("Segmentation fault!");
55 ▼ else if(index == 0){
56 pList->removeAt(0);
57 current = nullptr;
58 index = -1;
59 current++;
60 }
61 ▼ else {
62 Node* prev = pList->head;
63 ▼ for (int i = 0; i < index - 1; ++i) {
64 prev = prev->next;
65 }
66 pList->removeAt(index);
67 current = prev;
68 index--;
69 }
70 }
71
72 template<class T>
73 bool DLinkedList<T>::Iterator::operator!=(const DLinkedList::Iterator &iterator)
74 ▼ {
75 if(this->current == iterator.current && this->index == iterator.index) return 0;
76 return 1;
77 }
78
79 template<class T>
80 typename DLinkedList<T>::Iterator& DLinkedList<T>::Iterator::operator++()
81 ▼ {
82 if(this->index == this->pList->count) throw std::out_of_range("Segmentation fault!");
83 if(this->index == -1) {this->current = this->pList->head;this->index =0;}
84 else {this->current = this->current->next;this->index +=1 ; }
85 return *this;
86 }
87
88 template<class T>
89 typename DLinkedList<T>::Iterator DLinkedList<T>::Iterator::operator++(int)
90 ▼ { Iterator temp =*this;
https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 11/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

90 ▼ { Iterator temp this;
91 if(this->index == this->pList->count) throw std::out_of_range("Segmentation fault!");
92 if(this->index == -1) {this->current = this->pList->head;this->index =0;}
93 else {this->current = this->current->next;this->index +=1 ; }
94 return temp;
95 }
96
97

Test Expected Got

 DLinkedList<int> list; 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 | 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 | 
int size = 10;
for(int idx=0; idx < size; idx++){
list.add(idx);
}
DLinkedList<int>::Iterator it = list.begin();
for(; it != list.end(); it++)
{
cout << *it << " |";
}

 DLinkedList<int> list; [] [] 
int size = 10;
for (int idx = 0; idx < size; idx++)
{
list.add(idx);
}

DLinkedList<int>::Iterator it = list.begin();
while (it != list.end())
{
it.remove();
it++;
}
cout << list.toString();

 DLinkedList<int> list; [] [] 
int size = 10;
for (int idx = 0; idx < size; idx++)
{
list.add(idx);
}

DLinkedList<int>::Iterator it = list.begin();
for(; it != list.end(); it++)
{
it.remove();
}
cout << list.toString();

Passed all tests! 

Chính xác
Điểm cho bài nộp này: 1,00/1,00.

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 12/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Câu hỏi 4
Chính xác

Điểm 1,00 của 1,00

Implement methods removeAt, removeItem, clear in template class SLinkedList (which implements List ADT) representing the
singly linked list with type T with the initialized frame. The description of each method is given in the code.

template <class T>

class DLinkedList {
public:
class Node; // Forward declaration
protected:
Node* head;
Node* tail;
int count;
public:
DLinkedList();
~DLinkedList();
void add(const T &e);
void add(int index, const T &e);
int size();
bool empty();
T get(int index);
void set(int index, const T &e);
int indexOf(const T &item);
bool contains(const T &item);
T removeAt(int index);
bool removeItem(const T &item);
void clear();
public:
class Node
{
private:
T data;
Node *next;
Node *previous;
friend class DLinkedList<T>;

public:
Node()
{
this->previous = NULL;
this->next = NULL;
}

Node(const T &data)
{
this->data = data;
this->previous = NULL;
this->next = NULL;
}
};

};

In this exercise, we have include <iostream>, <string>, <sstream> and using namespace std.

For example:

Test Result

DLinkedList<int> list; [5,6,3,67,332,43,1,0,9]

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};

for(int idx=0; idx < size; idx++){

list.add(value[idx]);
}
list.removeAt(0);
cout << list.toString();

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 13/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Answer: (penalty regime: 0 %)

Reset answer

1 template <class T>

2 T DLinkedList<T>::removeAt(int index)
3 ▼ {
4 /* Remove element at index and return removed value */
5 Node *remove = nullptr;
6 Node *current = head;
7 ▼ for(int i=0;i<index;i++){
8 current = current->next;
9 }
10 remove =current;
11 Node * prev = current->previous;
12 Node * next = current->next;
13 if(prev!= nullptr) prev->next = next;
14 if(next != nullptr) next->previous = prev;
15 ▼ if(index==0){
16 remove =head;
17 this->head = this->head->next;
18 if(this->head !=nullptr) head->previous = nullptr;
19 }
20 ▼ if(index== count -1){
21 remove = tail;
22 tail =tail->previous;
23 if(tail!=nullptr) tail->next = nullptr;
24 }
25
26 T data = remove->data;
27 delete remove;
28 this->count--;
29 return data;
30 }
31
32 template <class T>
33 bool DLinkedList<T>::removeItem(const T& item)
34 ▼ {
35 /* Remove the first apperance of item in list and return true, otherwise return false */
36 Node *current = head;
37 int n =0;
38 ▼ while(current !=nullptr){
39 if (current->data == item ) {removeAt(n); return 1;}
40 current = current->next;
41 n++;
42 }
43 return 0;
44 }
45
46 template<class T>
47 ▼ void DLinkedList<T>::clear(){
48 /* Remove all elements in list */
49 int a = this->count;
50 ▼ for(int i =0;i<a;i++){
51 removeAt(0);
52 }
53 head = nullptr;
54 tail = nullptr;
55 count =0;
56 }
57

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 14/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Test Expected Got

 DLinkedList<int> list; [5,6,3,67,332,43,1,0,9] [5,6,3,67,332,43,1,0,9] 

int size = 10;
int value[] = {2,5,6,3,67,332,43,1,0,9};

for(int idx=0; idx < size; idx++){

list.add(value[idx]);
}
list.removeAt(0);
cout << list.toString();

Passed all tests! 

Chính xác
Điểm cho bài nộp này: 1,00/1,00.

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 15/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Câu hỏi 5
Chính xác

Điểm 1,00 của 1,00

In this exercise, we will use Standard Template Library List (click open in other tab to show more) to implement a Data Log.
This is a simple implementation in applications using undo and redo. For example in Microsoft Word, you must have nodes to store states when
Ctrl Z or Ctrl Shift Z to go back or forward.

DataLog has a doubly linked list to store the states of data (an integer) and iterator to mark the current state. Each state is stored in a node, the
transition of states is depicted in the figure below.

Your task in this exercise is implement functions marked with /* * TODO */.

class DataLog
{
private:
list<int> logList;
list<int>::iterator currentState;

public:
DataLog();
DataLog(const int &data);
void addCurrentState(int number);
void subtractCurrentState(int number);
void save();
void undo();
void redo();

int getCurrentStateData()
{
return *currentState;
}

void printLog()
{
for (auto i = logList.begin(); i != logList.end(); i++) {
if(i == currentState) cout << "Current state: ";
cout << "[ " << *i << " ] => ";
}
cout << "END_LOG";
}
};

Note: Normally, when we say a List, we talk about doubly linked list. For implementing a singly linked list, we use forward list.

We have include <iostream> <list> and using namespace std;

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 16/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

For example:

Test Result

DataLog log(10); [ 10 ] => Current state: [ 25 ] => [ 40 ] => END_LOG

log.save();
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.undo();
log.printLog();

DataLog log(10); [ 10 ] => [ 25 ] => [ 40 ] => Current state: [ 35 ] => END_LOG

log.save();
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.save();
log.subtractCurrentState(5);
log.printLog();

Answer: (penalty regime: 0, 0, 0, 5, 10 %)

Reset answer

1 DataLog::DataLog()
2▼ {
3▼ /*
4 * TODO: add the first state with 0
5 */
6 logList.push_back(0);
7 currentState = logList.begin();
8 }
9
10 DataLog::DataLog(const int &data)
11 ▼ {
12 ▼ /*
13 * TODO: add the first state with data
14 */
15 logList.push_back(data);
16 currentState = logList.begin();
17 }
18
19 void DataLog::addCurrentState(int number)
20 ▼ {
21 ▼ /*
22 * TODO: Increase the value of current state by number
23 */
24 ▼ if (currentState != logList.end()) {
25 *currentState += number;}
26 }
27
28 void DataLog::subtractCurrentState(int number)
29 ▼ {
30 ▼ /*
31 * TODO: Decrease the value of current state by number
32 */
33 ▼ if (currentState != logList.end()) {
34 *currentState -= number;}
35 }
36
37 void DataLog::save()
38 ▼ {
39 ▼ /*
40 * TODO: This function will create a new state, copy the data of the currentState
41 * and move the currentState Iterator to this new state. If there are other states behind the
42 * currentState Iterator, we delete them all before creating a new state.
43 */
44 list<int>::iterator after = currentState;
45 after++;
46 if(after != logList.end())logList.erase(after,logList.end());
47 logList.push_back(*currentState);
48 currentState = prev(logList.end());
49
50 }
51
52 void DataLog::undo()
53 ▼ {
54 /*
https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 17/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

54 ▼ /*
55 * TODO: Switch to the previous state of the data
56 * If this is the oldest state in the log, nothing changes
57 */
58 if(currentState != logList.begin()) currentState --;
59
60 }
61
62 void DataLog::redo()
63 ▼ {
64 ▼ /*
65 * TODO: Switch to the latter state of the data
66 * If this is the latest state in the log, nothing changes
67 */
68 list<int>::iterator after = currentState;
69 after++;
70 if(after != logList.end()) currentState ++;
71 }
72

Test Expected Got

 DataLog log(10); [ 10 ] => Current state: [ 25 ] => [ 40 ] [ 10 ] => Current state: [ 25 ] => [ 40 ] 
log.save(); => END_LOG => END_LOG
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.undo();
log.printLog();

 DataLog log(10); [ 10 ] => [ 25 ] => [ 40 ] => Current [ 10 ] => [ 25 ] => [ 40 ] => Current 
log.save(); state: [ 35 ] => END_LOG state: [ 35 ] => END_LOG
log.addCurrentState(15);
log.save();
log.addCurrentState(15);
log.save();
log.subtractCurrentState(5);
log.printLog();

Passed all tests! 

Chính xác
Điểm cho bài nộp này: 1,00/1,00.

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 18/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Câu hỏi 6
Chính xác

Điểm 1,00 của 1,00

Given the head of a doubly linked list, two positive integer a and b where a <= b. Reverse the nodes of the list from position a to position b and
return the reversed list

Note: the position of the first node is 1. It is guaranteed that a and b are valid positions. You MUST NOT change the val attribute in each node.

struct ListNode {
int val;
ListNode *left;
ListNode *right;
ListNode(int x = 0, ListNode *l = nullptr, ListNode* r = nullptr) : val(x), left(l), right(r) {}
};

Constraint:
1 <= list.length <= 10^5
0 <= node.val <= 5000
1 <= left <= right <= list.length

Example 1:
Input: list = {3, 4, 5, 6, 7} , a = 2, b = 4
Output: 3 6 5 4 7

Example 2:
Input: list = {8, 9, 10}, a = 1, b = 3
Output: 10 9 8

For example:

Test Input Result

int size; 5 3 6 5 4 7
cin >> size; 3 4 5 6 7
int* list = new int[size]; 2 4
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list;

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 19/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Test Input Result

int size; 3 10 9 8
cin >> size; 8 9 10
int* list = new int[size]; 1 3
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list;

Answer: (penalty regime: 0 %)

Reset answer

1 ▼ /*
2 ▼ struct ListNode {
3 int val;
4 ListNode *left;
5 ListNode *right;
6 ListNode(int x = 0, ListNode *l = nullptr, ListNode* r = nullptr) : val(x), left(l), right(r) {}
7 };
8 */
9
10 ▼ ListNode* reverse(ListNode* head, int a, int b) {
11 ListNode* current = head;
12 ListNode* tail = head;
13 for(int i=1;i<a;i++) current = current->right;
14 for(int i=1;i<b;i++) tail = tail->right;
15 ▼ for(int i =0;i<b-a;i+=2){
16 ListNode *lcurrent = current->left;
17 ListNode *rcurrent = current->right;
18 ListNode *ltail = tail->left;
19 ListNode *rtail = tail->right;
20 ▼ if(current->right == tail){
21 tail->right = current;
22 current->left = tail;
23 ▼ } else{
24 tail->right = rcurrent;
25 rcurrent->left = tail;
26 ltail->right = current;
27 current->left=ltail;
28 }
29 ▼ if(lcurrent != nullptr){
30 lcurrent->right = tail;
31 tail->left = lcurrent;
32 } else head =tail, tail->left=nullptr;
33 ▼ if(rtail !=nullptr){
34 current->right = rtail;
35 rtail->left=current;
36 } else current->right = nullptr;
37 ListNode *a = current;
38 current = tail;
39 tail =a;
40 current = current->right;
41 tail = tail->left;
42 }
43 return head;
44 }

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 20/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Test Input Expected Got

 int size; 5 3 6 5 4 7 3 6 5 4 7 
cin >> size; 3 4 5 6 7
int* list = new int[size]; 2 4
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list;

 int size; 3 10 9 8 10 9 8 
cin >> size; 8 9 10
int* list = new int[size]; 1 3
for(int i = 0; i < size; i++) {
cin >> list[i];
}
int a, b;
cin >> a >> b;
unordered_map<ListNode*, int> nodeValue;
ListNode* head = init(list, size, nodeValue);
ListNode* reversed = reverse(head, a, b);
try {
printList(reversed, nodeValue);
}
catch(char const* err) {
cout << err << '\n';
}
freeMem(head);
delete[] list;

Passed all tests! 

Chính xác
Điểm cho bài nộp này: 1,00/1,00.

BÁCH KHOA E-LEARNING

WEBSITE

HCMUT
MyBK
BKSI

LIÊN HỆ
 268 Lý Thường Kiệt, P.14, Q.10, TP.HCM

 (028) 38 651 670 - (028) 38 647 256 (Ext: 5258, 5234)

 [email protected]

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 21/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])
 lOMoARcPSD|19774343

17:52 14/10/2023 Double Linked List: Attempt review

Copyright 2007-2022 BKEL - Phát triển dựa trên Moodle

https://e-learning.hcmut.edu.vn/mod/quiz/review.php?attempt=1431309&cmid=186808 22/22
Downloaded by TH?NH LÊ L?C QU?C ([email protected])