Sorted Insert for Sorted Circular Linked List

This story was originally published here.

Trying to find the solution to this challenge may result in some of your guess running off to infinity and beyond. A close look at the edge cases and preparing some nested conditionals should give us the solution we are after.

Ground work

I’ll go on and start us off by saying that we have a list, sorted in ascending order, and the tail points back to the head of the list. The nodes are a basic struct with a data and next attribute. This completes our circularly linked list. Now how about inserting a new element into the list.

`def insert(value) #magic happens here…end`

Let’s say that we will traverse the list and use a pointer to the next node as a helper to remap the links when we do the insertion.

`def insert(value) current_node = @head_node next_node = current_node.next # iteration through loop hereend`

Now we can traverse the list and keep track of where our new node will be pointing and where our current node doesn’t get left by the wayside.

Traverse until we find our insertion point

We will traverse the linked list until our next node has a value greater than the value we are trying to insert. This tells us where our new node will point too.

`def insert(value) current_node = @head next_node = current_node.next  while value > next_node.data   current_node = next_node   next_node = current_node.next end  new_node = Node.new(value, next_node) current_node.next = new_nodeend`

After we break the loop we will create the new node and have it point to the next node. The current node will point to our new node. All is great right…?

Well no, if we are trying to enter a value that is greater than any value within the linked list we will fall right into a continuous loop.

Stomp out the edge case

To take care of this we can add a conditional to our loop that will break it when the next node has a value smaller than the current node. This implies that we have returned back to the beginning of the list. Let’s see what our final solution will look like.

`def insert(value) current_node = @head next_node = current_node.next while value > next_node.data   current_node = next_node   next_node = current_node.next   break if next_node.data < current_node.data end`
` new_node = Node.new(value, next_node) current_node.next = new_nodeend`

The source code can be found here on my github.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.