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.