Most taught data structure in computer science is linked list. Among that, singly linked list is most commonly used. Most of the JavaScript newbies or the "Back-end web developers" implements almost everything using Arrays. Here in this post I will be showing another alternate yet quick way (using linked list) to solve few real life problems in JavaScript.
You guessed it right, it will print 9. There is only one memory space which is being referenced by both movie and the item variables. It really doesn't matter, through which variable you are changing that memory's value. This concept will benefit us while creating a linked list.
We can assign some data to it -
Inserting after a node -
Linked list -
Image explains a lot, each node in a linked list holds two items, first item is the data while the other one is the pointer to the next item.
There are a few catches you might want to know -
- Suppose there are 10 nodes in a linked list (numbered 1 to 10). If the pointer of node 1 is changed to 3 instead of 2 (1 ---> 3 ---> 4 ---> 5 so on..) then JavaScript garbage collector will free the memory space of node 2 since node 2 has no references
- Linked list allows insertion or deletion of node at any place but does not allow random access
- Linked list is a sequential access data structure. It will cost you a lot to find the element at the 6th position or 5th position or nth position
- Use Linked list when you want to insert or delete an element where you have a huge amount of data, that's where Array will cost you a lot
Before moving forward, do you remember your training on object references, Luke? Well, you might want to recall how object references works in JavaScript -
var movie = {name: 'Star wars',rating: 8.5}var item = movie;item.rating = 9;console.log(movie.rating);
You guessed it right, it will print 9. There is only one memory space which is being referenced by both movie and the item variables. It really doesn't matter, through which variable you are changing that memory's value. This concept will benefit us while creating a linked list.
Implementation of Linked List -
A simple node -var node1 = {data: null,next: null}
We can assign some data to it -
node1.data = 'Empire strikes back';
Creating next node
var node2 = {data: null,next: null}node2.data = 'Return of the jedi';node1.next = node2;
Pretty easy! Right? Of course, manually creating a node each time when needed is not the solution that we are looking for. A better way is to create a List object, which implements all the internal logic of the linked list and only exposes some utility methods for the user.
function List() {this.head = null;this.end = null;}
Initially Linked list's head and end properties are set to null. That means the list is empty.
Now it should expose a method that can easily create a node
this.createNode = function() {return {data: null,next: null}}
Next thing should be adding this newly created node in our existing list. While adding the new node in the list, you must consider a few things -
- By default, new node should always be added at the end of the list
- Before adding new element there should be a check of empty list. if empty, new element should be added at the beginning of the list
Adding node in the list -
this.addNode = function(data) {// Checking if list is emptyif (this.start === null) {// Creating a new nodethis.head = List.createNode();// since we have only one node in list, start and end will point to same nodethis.end = this.start;} else {// Appending newly created node after the end of the listthis.end.next = List.createNode();// Setting last node as end nodethis.end = this.end.next;}// Finally assigning data to the newly created nodethis.end.data = data;}
so far your List function looks like -
function List() {this.head = null;this.end = null;this.createNode = function() {return {data: null,next: null}}this.addNode = function(data) {// Checking if list is emptyif (this.start === null) {// Creating a new nodethis.head = List.createNode();// since we have only one node in list, start and end will point to same nodethis.end = this.start;} else {// Appending newly created node after the end of the listthis.end.next = List.createNode();// Setting last node as end nodethis.end = this.end.next;}// Finally assigning data to the newly created nodethis.end.data = data;}}
Now you can create the linked list with multiple nodes dynamically -
var list = new List();for (var x = 0; x < 5; x++) {list.addNode(x);}
Now that you have base structure ready, you can add multiple methods to your list.
Adding node at start of the list -
this.appendAtFirst = function(data) {var tempNode = List.createNode();tempNode.next = this.head;this.head = tempNode;tempNode.data = data;}
Inserting after a node -
Inserting in between the linked list is way too easier as compared to array. Why you ask? Because array moves a lot of data in order to make space for new node while the linked list will simply changes pointer of one node. So, when you are dealing with huge amount of data that requires insertion and deletion, better to prefer linked list over array.
this.insertAfter = function(n, data) {// n: node after which data to be insertedvar instance = this.head;// Start traversing from the first/head element until you reach nth nodewhile (instance !== null) {if (instance.data === n) {var tempNode = List.createNode();tempNode.data = data;tempNode.next = instance.next;if (instance == this.end) {this.end = tempNode;}instance.next = tempNode;return;}instance = instance.next;}}
Removing a node -
For removing any node, you just need to change the pointer of it's previous node to point to it's next node. After this, your node will not be having any reference. JavaScript garbage collector will delete that node for you. So no need to explicitly delete any element.
this.remove = function(data) {// data - Node having data needs to be deletedvar instance = this.head;var previous = this.head;// Traverse list from head/start nodewhile (instance !== null) {if (data === instance.data) {if (instance === this.start) {this.head = instance.next;return;}if (instance == this.end)this.end = previous;previous.next = instance.next;return;}previous = instance;instance = instance.next;}}
List traversal -
Now it is easy to figure out how to traverse a list.
this.traverse = function() {var instance = this.head;while (instance !== null) {console.log(instance.data);instance = instance.next;}}
Follow this blog for more JavaScript hacks!