# Sorted Insert for Sorted Circular Linked List

September 2016 · 2 minute read

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