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

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 `idx`th `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 `if`s, 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

4 Likes

Nice work on the article man!

1 Like

This topic was automatically closed after 30 days. New replies are no longer allowed.