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.

Node = Struct.new(:data, :next)

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 here
end

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)
    @node_count += 1
    current_node.next = new_node
end

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_node
end

The source code can be found here on my github.