Welcome to my very first blog! Currently I'm going through the junior phase of immersion at Operation Spark. Recently I have been introduced to different types of data structures and today I'm going to talk about Linked List specifically a Singly Linked List.
So what is a Linked List? The simplest way I can describe it, is a data structure that collects elements, each element is called a node, and stores them in a sequential order. Now that sort of reminds me of something else. That sounds just like an array doesn't it! Now the new question is, why would I even use a Linked List when you can just use an array to basically do the same thing. To answer that we have to dive a bit deeper to what exactly is going on in each data structure.
Earlier I mentioned that the nodes that were being collected were stored in sequential order, but the difference here is how it's being stored in memory. For an array physically in memory it's stored contiguously meaning that all the nodes within the array are right next to each other, therefor it's able to get indexed. For Linked List on the other hand Every node in the sequential order can be anywhere in memory.
For the node to know where the next node is, it carries two pieces of information instead of just one. It carries the value, and a reference to where the next node is. Each node is able to point to where the next one is in memory making them sequential.
This introduces pros and cons for accessing and modifying each data structure when it comes to time complexity. If you're trying to get access to a certain value in an array, all you would need to know is the index of the value. Since each node is right next to each other in memory you can just jump right to that index accessing the value in a instant O(1). For a Linked List because each node is not next to each other, the computer is going to have to iterate from the very first node until it finds the value that you're looking for. To you it might feel like it found the value in a instant but for computers in terms of time complexity it took a bit more then a instant, term for this is O(n) or linear time.
So far the score is 1 for array and 0 for a Linked List! What advantages does the Linked List have over an array? It comes down to when you want to delete or add something to either data structure where Linked List is able to turn the tide. For an array if you want to add/delete a node lets say in the middle, every node after it would have to move over or back a block. The time complexity for both methods would be linear O(n) since the time it takes depends on how many elements have to resort. For a Linear List you can add or delete anywhere and it will be an instant action.
With Linked List this is all a pointing game, from the code above when you add the tail, all you have to do is make the previous tail point to the new tail and that's it. If the list is first empty you just make the first node the head and the tail. There's no iterating through anything. Deleting and adding is all done in an instant O(1). There we go new score array:1 and Linked List:2.
So simply put if your'e making a list and you know how much data will be used, by all means use an array. If you're making a list and you're constantly adding and removing things from it, a Linked List is your way to go. Your computer will thank you!
Thank you for making it all the way to the end, hopefully I was able to shine some light on this data structure to any beginners out there.
Top comments (0)