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

[oaktree]

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 templates) 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 thrown.

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

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 nodes (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 exceptions. 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 insertion 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.