A singly linked list is a type of linked list in which data can be read in one direction, from head (first node) to tail (end or last node). Singly linked lists are similar to arrays but they differ in the sense that if you need to access the 3rd item in the array you would be able to have direct access where in the linked list you would have to traverse each node until you reached the 3rd node. I don't really understand too much about memory and how these data structures are actually stored in memory but I'll try to explain what I know. In any array you need consecutive memory slots where in a linked list they can store in any available memory slot with a pointer to their next node.
So as far as memory goes it seems that linked lists are much more memory efficient than an array. Adding and removing nodes on a linked list overwrite and setting new pointers to and from the nodes. When you insert and remove from arrays you are actually have to shift and move every element after the insertion or deletion. Outside of adding to the end of the array it would seem that would be the only time when performance wise it would beat a linked list. So now knowing this, I can actually see why a linked list is more efficient in memory and depending on the use case would show greater performance than an array(which I currently use daily / all the time). A goal of mine in the near future is to actually start implementing these new learned data structures into my code base. Is it necessary, probably not, will anyone care, no (I currently work as the only dev on my team.....), but will it make me have a better understanding and help continue my learning path, yes!!!!
I personally have never run into this on an interview but I think that one of the more common and low level questions someone will ask you at some point in your career would be reverse a singly linked list. Why is it important? I mean if it's an array I could do Array.reverse() and bam look at me. The idea from what I gather is how well do you know the simplest data structure and can you traverse and then store all the nodes and values in their reverse order. So let's do it!!!!!!!!!
I went ahead and built out a javascript Singly Linked List data structure to better understand them. This can be found here along with all of my other data structures that I'll be creating over time. SinglyLinkedList. So if you look at the repo you can see I added a reverse function which would take care of the statement above but we'll type it out again down here. I know you can do it both iteratively and recursively. I'm just gonna tackle the standard iterative and if you look at my class on github I do it with a for loop but here I'll change it to a while loop cause why not.
function reverse(list) {
let node = list.head;
let previous = null;
let next = null;
while(node) {
next = node.next;
node.next = previous;
previous = node;
node = next;
}
return list;
}
So I hope any or some of this will help you out in your growth as a developer. I will say trying to squeeze a bunch of learning into a very short period of time especially when dealing with this particular subject, I'd say hold off. Take your time and really try to understand what is going on. I'd say half the time I don't take my own advice so again we'll see how this journey ends.
Top comments (0)