An Introduction to Linked Lists
What is a linked list?
In computer science terms, a linked list is a linear collection of elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a linear data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node (element) in the sequence. Unlike an array, the elements or nodes of a linked list is not stored in sequential memory locations. It is tied together by using a pointer, where it tells us where the next element in the link is stored.
Each node in a singly linked list has its own value, and a reference to the next node. The only node that is different is the last node where the linked list terminates, as its reference points to null. One major advantage of a linked list is it allows you to easily insert or remove an element/node from the list without altering the entire data structure. Where in an array, if you insert or delete an element, all the indexes after that element will be changed.
In order to create a linked list, we need to first create and define a class (Node) in the code above. As it was mentioned earlier, it initializes with two properties; a data and a reference to the next node. In this case we linked a series of nodes by telling it which node will be following another. In this very short linked list terminates at eNode and it this.next value will be null as there is not another node linked after it. With the above linked list, we can easily see where it terminates. But what if we get a linked list that is hundreds of nodes long and we need to find the last node?
We can setup a function like the one above. Since a node will always have this.next we can setup a while loop. While there is a node.next, we want to set the current node to the next node until it reaches the end. Since the value of node.next on the last node of a linked list will always be null, we can also console.log its value to confirm. Using this while loop, we can find the last node from any position in the link.
Above is another exercise to help us get more familiar with traversing the linked list. In this example we want to find the middle node of the chain. We set up two declarations, a slow node and a fast node, and where the fast node will be moving at twice the speed of the slow node. Using this method, our slow node will be at the middle of the linked when our fast node reaches the end. This function would only work if we start from the beginning or head of the linked list.
If you want to read more on linked lists and learn how to add a node to any position, please check out:
Thispost.next =
https://codeburst.io/linked-lists-in-javascript-es6-code-part-1-6dd349c3dcc3
