Data Structures (Part 1.3): Linked List [delete()]

[oaktree]

Hello 0x00sec people! This next part of my series is about delete(...).

Basic Algorithm Description

delete(...) will remove a node at a certain index in a linked list. It takes one parameter of type const size_t& idx. Basically, it takes in a number corresponding to a certain node in the list, if we count the root node as 0 and so on.

The function will then traverse the list until it arrives at the idxth node. Then, it’ll delete this node.

The function returns the data stored at that particular node. It has O(n) time complexity.

---

#The Code

template <class T>
T List<T>::delete(const size_t& idx) {
	node<T>* h = root;
	size_t cnt = 0;

	while(cnt < idx - 1 && h/*->next*/ != nullptr) {
		h = h->next;
		cnt++;
	}

	if (cnt == idx - 1) {
		if (h != nullptr && h->next != nullptr) {
			
			node<T>* tmp = h->next;
			T tmp2 = tmp->d();

			h->next = tmp->next; // overlap

			tmp->next = nullptr;
			delete tmp;

			len--; // update length

			return tmp2;
		} 
		// should i have else?!?!?
	}

        throw std::out_of_range("ERROR: there is no node at that index to delete!");
}

Note: I’m still actively trying to make this function better. This is just what I have as of this writing.

So, first a node<T>* called h is declared for traversal purposes. Then, we declare a size_t cnt to keep track of our position in the list. This is so we’ll know if the index idx passed to the function is out of bounds. If we never reach it, no node should get deleted.

Upon traversal (after the while loop), we’ve set it up so that h->next is the node to be deleted.

In the outer if, we want to make sure that our h is correct (h should be the one before h->next, so it’s index is one less than idx).

In that inner if, we want to make sure that h, or mylist[idx - 1], isn’t nullptr; we also need to ensure that h->next, the node we’d like to delete, is not a nullptr, either. This is because: if h is a nullptr, there is no mylist[idx] to delete; and, if h->next is nullptr, mylist[idx] has nothing to delete, because it’s the end of the list.

If we pass those two ifs, then the fun begins!

1. Make a temp node<T>* tmp to hold on to the node we intend to delete.
2. Save it’s data in T tmp2 = tmp->d() to return later. (Note that d() is a member function of a node that returns the data stored at a node.
3. Reassign h->next to tmp->next. This basically jumps over tmp in the linked list, virtually removing tmp from the list.
4. Now we have to clean up tmp->next by setting it to nullptr. Don’t worry! We haven’t lost tmp->next because h->next now holds that!
5. Now we can delete tmp, which calls the node destructor ~node().
6. Since we’ve taken a node out, we need to decrement the length of the list len.
7. Last, let’s return the data value stored in the node we just deleted.

If, for any reason, we don’t arrive at the node to delete, we throw an exception saying that there is no node to delete.

---

Conclusion

Okay, that’s it for delete. In the future, I will probably improve this function.

Thaaanks,
@oaktree

[pry0cc (Leader & Offsec Engineer & Forum Daddy)]

Nice work on the article man!