If you’re getting trouble with linked-list. This post is for you.
Note: When learning linked list, forget everything you know about array. The reason is nowadays, array is way more widely used, so people who only know array will find it hard to understand linked list cause their mind are engraved deeply by the array mindset. Forget about length, index,… of an array before reading this.
What really is a linked list?
So, beside an array, how can we store a collection of data without index and without an object that contains all of the data we want to access? The answer is we can do that by making the data have ability to link to the other piece of data itself. That’s the origin of linked list.
It like with array you have a box that divide into different room with their number. You can pick anything from the box when you have the address.
In other hand, linked list is like you have a letter A in the alphabet. You don’t know what the next letter is and you don’t know how many letters are there, but you can ask the letter A to tell you what should you learn next, and the letter A show you B
Okay, now go into the code world with this example:
class Node {
String letter;
Node next;
}We have a Node instance, that what people usually refer to a piece of data in linked list. A node contains a letter, that is the actual data we gonna use, it can be an int, string or any type of data you want. Another field is next, which is a reference to the next data that is link directly to this node instance.
Imagine we have letter “A”. So the node instance contains letter A, of couse and another node instance tell us where they store the next letter. In this case, it is the letter B. And the letter B will give us the access to the letter C and so on…
But where is the end of this list? The linked list end is when you can’t find any next one. That’s mean the node instance of the Z letter will have the next property is null. That’s how we know the list ends.
Okay, for now you may ask “I still feel something werid, how can I get access to one specific node? Example I want to find the letter D”
With linked list, you can travel from A (the head) through all the element in the list, that’s how you find your letter
// don't mind this, this is just the initialization of linked-list, like we set the
// array = ["A","B","C","D]
head = Node("A", Node("B", Node("C", Node("D", null))));// we find the node contains letter D
Node nodeD = findLetter(head, "D");// findLetter function
Node findLetter(Node head, String letter) {
var node = head;
while(node != null) {
if(node.letter == letter) return node;
node = head.next;
}
return null;
}
In the function findLetter above, we create a loop with node, why? Because one node will lead us to the next one, and when the node is null, that mean we reached the end of the linked list.
Of course you may feel dumb because we already have the letter “D”, why are we finding the node? Because it is just example im using a simple type of data is String, in real case application, the data can have customer data type and we need to find that data base on one of its property.
So you may ask again, why we just use array?
The answer is you can. But in some scenarios, linked list is faster than array. Two of them are insertion and deletion For example the problem is: insert a letter “Z” between letter C and D.
With array you will:
- Find the letter C at index i.
- create a new array have the length more than the original array 1 unit
- Copy element from 0 to i of the original array into the new array at position 0 to i
- Copy element from i + 1 to the end **of the original array into the new array at position i + 2 to the end
- newArr[i+1] = Z
With the linked list, you can do:
- Find the node that contains letter C
- Assign the next property of the node “Z” to “D”
- Assign the next property of the node “C” to “Z”
Done! You can see the image below that demonstrate this action
As you can see, a linked list require much less step to complete
Another question you may ask is why I need to copy the array? I literally have a JS method just for that.
The answer is, like many mordern language nowaday. The array in JS is actually an Dynamic array. It mean this array can increasing or decreasing the size of the array automatically. We are talking about the normal array. Dynamic array has lots of feature because it’s doing many things underhood.
What are others type of linked list?
- Singly linked list
This is what we’ve already disscussed above. Each node have a reference to the next node
- Doubly linked list
Beside having a next property. Now each node have a prev reference which point to the node right before the current node. This linked-list is more harder to maintain and create but it gives you travel throughout the list easier because now you can travel back, instead of just moving forward like in Singly Linked list
- Circular linked list
The circular linked list is a linked list where all nodes are connected to form a circle. In a circular linked list, the first node and the last node are connected to each other which forms a circle. There is no NULL at the end.
- Doubly Circular linked list : I think you get the idea
Using Recursion in linked list
When you’re working with linked list, especially when you’re reading others code, you will encouter someone prefer using recusion with linked list
Take the findLetter function above as example, now I will write that function again using recursion. Try to keep up!
head = Node("A", Node("B", Node("C", Node("D", null))));// we find the node contains letter D
Node nodeD = findLetter(head, "D");Node findLetter(Node node, String letter) {
if (letter == node.letter) return node;
return findLetter(node.next);
}
Try to understand it in a while. If you can not, Im here to help (Skip if you want)
The first time findLetter is called is with the param Node(A).
It will check the condition (D == A → false), go to return
So the result of the function findLetter(NodeA, “D”) will be equal to the result of the function findLetter(NodeB, “D”)
The function findLetter(NodeB, “D”) is called. Function findLetter(NodeA, “D”) will depend and wait for the function findLetter(NodeB, “D”) to be completed.
The result of the function findLetter(NodeB, “D”) will be equal to the result of the function findLetter(NodeC, “D”)
The result of the function findLetter(NodeC, “D”) will be equal to the result of the function findLetter(NodeD, “D”)
The result of the function findLetter(NodeD, “D”) is NodeD
— > The result of findLetter(NodeA, “D”) is NodeD → task completed
Conclusion
Linked list maybe rarely be used, but it is still useful in many case, and you will meet it in your journey to become a better developer. Hope this article helps you feel linked-list is a bit easier. Thanks for reading!
