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!

- Make a temp
`node<T>* tmp`

to hold on to the`node`

we intend to delete. - 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`

. - Reassign
`h->next`

to`tmp->next`

. This basically jumps over`tmp`

in the linked list, virtually removing`tmp`

from the list. - 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! - Now we can
`delete tmp`

, which calls the`node`

destructor`~node()`

. - Since we’ve taken a
`node`

out, we need to decrement the length of the list`len`

. - 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