# Data Structures (Part 1.4): Linked List [insert()]

Okay, 0x00sec people! Now for `insert(...)`. I expect this to be the last technical part of the Linked List subseries before a fairly significant code dump.

# Algorithm Description

Our insertion function takes two parameters: `T val` and `const size_t& idx`.

• `T val` is a value of type `T` (remember, I like `template`s) to be inserted.
• `const size_t& idx` is the index at which a new `node` is to be placed.

The function will return `val` upon a successful run; otherwise, it will `throw` an exception (to be explained later).

So, `insert(...)` will traverse the list until it reaches the index `idx` desired, or until the end of the `List` is reached. If we never arrive at `idx`, the exception (again, to be discussed later) gets `throw`n.

Time Complexity: `O(n)`.

# Source Code

``````template <class T>
T List<T>::insert(T val, const size_t& idx) {
if (idx == 0 && root == nullptr) {
this->append(val);
return val;
}
node<T>* h = root;
size_t cnt = 0;

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

if (cnt == idx - 1) {
if (h != nullptr) {

node<T>* new_node = new node<T>(val);

new_node->next = h->next;

h->next = new_node;

len++; // update length

return val;
}
}

// WATCH THIS LINE
throw std::out_of_range("ERROR: called insert() past the acceptable range of the current linked list");
}
``````

Oh dear! Thatâ€™s hella code. Letâ€™s get to itâ€¦

First, we want to check if `root` is `nullptr`. If it is, and if weâ€™re trying to insert at `idx = 0`, we call a function `append()`, which I have yet to reveal, that tacks on to the end. In this case, our `insert(...)`ing is done, so we return right then and there.

The next two lines of the function should remind you of the `delete(...)` function from last time (wait, you didnâ€™t read that?).

In the `while` loop we traverse the list (again, much like we did so in `delete(...)`) until we reach `idx - 1` or the end of the list. Note: I chose `idx - 1` so that `h` is the `node` before. Thus, the new `node` becomes `h->next`.

The `while` loop ended. Now we must check a few things:

1. Are we at `idx - 1`; meaning, are we where we want to be (in the list)?
2. Did we hit the end of the list already?

First, I make sure that first condition is true. Inside that `if`, though, I put a second `if`, reading `if (h != nullptr)`. This is because, if `h` (which is `some_list[ idx - 1 ]`) is a `nullptr`, that means that weâ€™ve come just short of the index `idx` where we want to put a new `node`. Note: We canâ€™t just tack on a new `node` at `idx - 1` if `h` is a `nullptr` because then we wouldnâ€™t be inserting at `idx`, now would we?

Okay, but what if we pass both conditions? Now weâ€™re inside the nested `if`s.

1. Construct a new `node<T>*` and set `val` as its `data`.
2. Set `new_node->next` to `h->next`. In math-y English, this means "make `some_list[ idx ]` point to `some_list[ idx + 1]`". If `h->next` is a `nullptr`, that wonâ€™t affect us, because any `node`'s default `next` defaults to `nullptr`, anyway!
3. Make `h->next = new_node`; ensure that `some_list[ idx - 1 ]` points to `some_list[ idx ]`. We are trying to not lose any `node`s (because thatâ€™d be a memory leak, and good programmers donâ€™t leak their memories).
4. Increment the length `len` of the list to account for this shiny new `node` weâ€™ve just `insert(...)`ed!
5. `return val`, thereby ending our presence in the function before reaching that default `throw`.

## Brief Explanation of the Default Exception

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

What does this mean? So, if we donâ€™t reach the spot in the list where we wanted to `insert(...)` a new `node`, what do we do? Do we panic? Sort of. But itâ€™s 2016! Letâ€™s be civil about how we panic by using `exception`s. This way, the caller of the function can accommodate for trying to `insert(...)` past the bounds, or `out_of_range`, of the list.

# Conclusion

Thatâ€™s `insert(...)` for ya! I now challenge you to implement an `insert`ion function that takes a linked list rather than one value to insert! Would you want to copy over all the values? What would you do?

Thatâ€™s it for today,
oaktree

A microphone can be heard hitting the ground.

2 Likes

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