Bugs found in “doubly_linked_list.h” and possible solutions

[Fr1eran]

I have found three bugs in the doubly_linked_list class, below I will show how to reproduce them and give possible solutions.

Bug in search method

Due to t != tail condition statement, the value stored in tail node can never be searched.

How to reproduce

test code like:

vector<int> v {1, 2, 3};
doubly_linked_list<int> dll(v);
cout << dll.search(3);

expected output: 1

actual output: 0

Possible solution

template<typename T>
bool doubly_linked_list<T>::search(T const key) const {
	if (this->empty()) {
		return false;
	}
	else {
		std::shared_ptr<node> t = root;
		while (t != nullptr && t->val != key) {
			t = t->next;
		}
		if (t == nullptr) {
			return false;
		}
		return true;
	}
	//return false;
}

Bug in push_front method

Due to the lack of tail = p , root and tail will not point to the same node when push_front is called on an empty chain.

How to reproduce

test code like:

doubly_linked_list<int> dll;
dll.push_front(1);
dll.push_back(2);
dll.push_back(3);
cout << dll;

expected output: {1 2 3 }

actual output: {1 }

Possible solution

template<typename T>
void doubly_linked_list<T>::push_front(T const key) {
	std::shared_ptr<node> p = std::make_shared<node>(key);
	p->next = root;
	p->prev = nullptr;
	if (root != nullptr) {
		root->prev = p;
	}
	else {	
		tail = p;
	}
	root = p;
	_size++;
}

Bug in erase method

When the node that tail points to contains a value equal to key, the pointing of tail does not change, which results in that node actually not being deleted.

How to reproduce

test code like:

vector<int> v {1, 2, 3};
doubly_linked_list<int> dll(v);
dll.erase(3);
dll.push_back(4);
dll.push_back(5);
cout << dll;

expected output: {1 2 4 5}

actual output: {1 2 }

Possible solution

I refactored this function and provided a version that can delete all matching elements.

template<typename T>
void doubly_linked_list<T>::erase(T const key) {
	if (root == nullptr) {
		return;
	}
	std::shared_ptr<node> curr = root->next;
	while (curr != nullptr) {
		if (curr->val == key) {
			if (curr == tail) {	// handle tail node
				tail = tail->prev;
				tail->next = nullptr;
				break;
			}
			else {	// handle intermediate nodes
				curr->next->prev = curr->prev;
				curr->prev->next = curr->next;
			}
			_size--;
		}
		curr = curr->next;
	}

	if (root->val == key) {	// handle root node
		root = root->next;
		if (root == nullptr) {
			tail = nullptr;
		} else {
			root->prev = nullptr;
		}
		_size--;
	}

}// after leaving the scope, all objects are deleted

If there's a more elegant way to write it then that would be great. :)

[github-actions]

Thank you for your interest in AlgoPlus, a maintainer will see your issue soon!

[spirosmaggioros]

Hi @Fr1eran, thanks for pointing this out, due to heavy work these couple of days i will look at this shortly(most probable tomorrow). No need to mention something else!

[spirosmaggioros]

@Fr1eran PR #89 is open, you can take a look.

Will merge it once you check that everything is fine now and can't reproduce any of the bugs you found.
Once again, thank you for pointing them out!