Cracking Ordered Singly Linked Lists

Singly linked lists are a node based data structure, that as any other data structure, helps you organize data. In this kind of list, a node is an object with two instances variables: element and next. The element is the data that what we want to store, and the next is a reference to the next node in the list. So, basically, singly linked lists are a series of connected nodes where each one have a reference to the next and the last node in the list points to null. When we create a singly linked list we keep a reference to the head (the first element of the list) to be able to iterate through the list.

Ok, fine. I know what they are, but… why do I need then?
If you are curious about singly linked lists, probably you already know about arrays. Well, interestingly, they evolved from the cons of array. The worst thing about arrays is that the size can’t change, if want to expand it we need to create a bigger array and move all the elements to the new one, while the singly linked list can be easily expanded or shrunk.
What if I want to keep them ordered? It is really that difficult?
When I started studying this kind of lists not so long ago, it was really hard for me to keep them ordered. It was really confusing for me to rearrange the order, because in singly linked list you only have a reference to the next node. Once I cracked it, I did not suffer anymore. I figured that if it was a problem for me, probably it is for someone else to. So, I will explain it to you easily.
Adding an element in an ordered list.
I will show you a way to keep your list ordered when adding a new element. Imagine we want to create a list with all the scores of the players of a game, ordered from lowest to highest. We will not store any user’s data, just the anonymous score. And we will keep a reference to the lowest and highest score nodes of the list.
Before starting to resolve any given problem, it’s really, really, really important to be able to identify all the possible cases that our program will need to deal with. Let’s analyze all the possible cases for our score board.
No matter the case, we need to add a new score. For that reason, is a great idea to start creating a new node with is element as the new score and is next node referencing to null.
List is empty.
First, we need to able to identify if our list is empty. There a few ways of doing this, as determining if the lowest or highest score node are null (nothing have been assign to them) or keeping an instance of the current size of the list. I vote for the second option because it will increment our possibilities of adding new methods or functions.
Once we have identified if our list is empty, we need to state that our new node score is the lowest and highest score.
Java code:
lowest_score=new_score;
highest_score=new_score;
The new score element is the lowest score element.
If our new score element is lower than our lowest score element we need to tell our little system to update this important info. When I started studying singly linked lists I had no idea of how important the order of our statements is. So, follow carefully the following steps to update the lowest score.
First, we need to specify that the next node of the new score node is the lowest score. After we make this change, we state that the lowest score node is the new score node now.
Java code:
new_score.setNext(lowest_score);
lowest_score = new_score;
The new score element is the highest score element.
In the other hand, if the new score element is higher than the highest score element, we first state that the next node of the highest score node is now the new element score node. Then, we state that the highest score node is now the new element node.
Java code:
highest_score.setNext(new_score);
highest_score = new_score;
The new element is between the lowest and highest score.
We have taken care of all our easy bases, now is when things get really interesting. To be able to implement this part we need to create a new node: the current node. This node will help us iterate between all the other elements of the list.
Remember that we only have a reference to the next element of the list, so we need to be creative. First, we define that our current node is equal to the lowest score. By doing this, we have created a clone of our list without changing our lowest score node.
While the element of the next node of the current node is less than the element of the new score, we will keep stating the current to be equal to next node of the current value. By doing this, we will advance one position in our list until we find a value that is greater than the new score. When we find it we will know that the new score just goes before it.
Because we have been keeping a reference to the previous value of that element we can point that element to our new score. So, as always, the order is important. After the while loop breaks, we will state that next node of the new score node is the next node of the current score node. Then, we state that the next value of the current score is the next score node. This case will be much clear if we take a look to the code.
Java code:
Node current_score = lowest_score;
while(current_score.getNext().getElement()<new_score.getElement()){
current_score=current_score.getNext();}
new_score.setNext(current_score.getNext());
current_score.setNext(new_score);
Time to be creative.
Now is the time where you start thinking in 101 ways of improving this code. Please, let me know in the comments what you think about this quick tutorial and what would you do better. Conversation is the key to be better everyday. See you! :)
