Intro to Data Structures + Algo [Part 3]

Hello everyone, it's been another week and is time for the next part of our series. Today we are going to be talking about Linked list. We are covering two type of linked list, singly and doubly. So what problems did we had with static arrays?

We were able to allocate a certain amount of data or memory next to each other but then both dynamic and static arrays can increase their memory once they hit a certain limit and double the memory in another location. However, this operation of doubling up memory has a performance implication and it cost O(n). Additionally, arrays have bad performance for operations such as delete and / or insertion that have to shift indexes over. Specially when you do these operations when is not at the end of the array.

Then, as to our rescue came the hash tables which allows for you to store whatever you want in memory. Hash tables will know where to store it for us and take care of it. Unfortunately, hash tables by default aren't ordered but don't sweat it that where Linked list will make our life easier. Does this mean that Link lists are the go to alternative now? No, there is never an absolute answer in data structures. Remember, there will always be some trade offs.

Note: Hashes will be covered in a future post. 🙇

A singly linked list contains a set of nodes. These nodes contains two elements, the value of the data that you want to store and a pointer to the next node in line. The first node is called the 'Head' and the last one is 'Tail' the after the last node it points to 'Null'.

Example 1 - Pseudo Code

/* 
head
eggs 
4   --> ham     tail
        6  --> cheese
               12    --> null
*/

For more visual representation of algorithms use this website.

Are linked list good or bad? First, on arrays you are able to start from whatever index of your choosing but on linked list you can only iterate from the head until you hit null.

Let's talk about what do we mean about a pointer? refers to the next place (object or node) in memory. Simplest example for pointers in javascript is the following:

const objectOne = {stock1: 1.33}; const objectTwo = objectOne;

Now let's jump to a more concrete example. This upcoming piece of code will be the base for our first exercise. The challenge is to complete this linked list. Tip: Try completing an append() method that allows you to add the value to the list.SOLUTION

// 23 --> 51 --> 12
class LinkedList {
  constructor(val) {
    this.head = {
      value: val,
      next: null
    };
    this.tail = this.head;
    this.length = 1;
  }
  append(val) {
    // complete it for the linkedList pt 2
  }
}

let myLinkedList = new LinkedList(23);
myLinkedList.append(51);
myLinkedList.append(12);

Now let's try creating a prepend() method for our list under the append method. Check out the Linkedlist2 script for the Solution

Resources

• VisualAlgo.net by Dr Steven Halim
• GeekforGeeks

Conclusion

Hey y'all, thanks for sticking around in this mini series. We have covered the basics about linked list and Hopefully we have all learned a thing or two from today examples. If you guys have any suggestions or better examples please share them in the comment section below. P.S: I'm going to start updating all blogs now. Apologies for any inconvenience.