Rick Rieger
riegercodes

Follow

riegercodes

Follow

100 Days of Code day 10 Linked List Data Structure

Rick Rieger's photo
Rick Rieger
·Feb 18, 2022·

6 min read

100 Days of Code day 10 Linked List Data Structure

Hello, my name is Rick and I am in search for gig as a developer :)

This past December, I finished up a year long study with a full-stack school in NYC called Codeimmersives. We explored HTML, CSS, JavaScript, and how to build applications using the MERN stack. I learned about class-based components, passing props around (prop-drilling) and utilizing the component lifecycle(componentWillMount, componentDidMount, etc). After learning class based components, we moved on to functional based components using hooks, custom hooks, and different ways to manage state, such as the useContext and Redux APIs. (This is just a brief overview of the technologies I studied over the past year). Now that I am finished with Codeimmersives, I have decided to review the basics of programming/computer science, and continue to build projects. I am documenting my journey by sharing these blog posts. Please help me out by dropping a comment below on what you think!

If you need a refresher on how classes work in Java Script check this out.

What is a linked list?

  • Linear data structure with nodes

  • Ordered collection of data

  • Not stored in sequential memory locations (like an array)

  • nodes are linked together using a pointer

  • First node is called the "head"

  • Last node is the "tail" (reference to null)

What's a node?

In computer science (because it can mean different things in other areas of study), a node is a basic unit of a data structure, such as a linked list or a tree data structure. Nodes contain data and also may link to other nodes. Links between nodes are often implemented by pointers. There is a more in depth explanation here.

Familiar with the document object model? These are all considered nodes.

image.png

Let's just say a node is and object that points to another object in memory.

Take for example below, there are two objects, where one points to another.

let node1 = {
  data:'Bob'
}

let node2 = {
  data:'Lucy'
}

node1.next = node2

console.log(node1)  

// result ==> { data: '100', next: { data: '200' } }

Let's build a linked list

First, let's create a class that will instantiate each node. By default, the second argument, next (the pointer), is set to null. This is important so later we can identify where our ending node is (the tail).

class Node {
constructor(data, next = null){
  this.data = data;
  this.next = next;
    }
}

let node1 = new Node(100)

console.log(node1)

// result ==> Node { data: 100, next: null }

Next, we can create a class called LinkedList. The constructor will have two properties;

  1. head - it is set to null by default, to handle if the list is empty. The head will refer to our object we create using the Node class. When additional objects are created a new node will be first as the head.

  2. size - to keep track of how many nodes are in the linked list.

class Node {
constructor(data, next = null){
  this.data = data;
  this.next = next;
    }
}

class LinkedList {
  constructor(){
    this.head = null;
    this.size = 0;
  }

}

Let's create a method that inserts our first node.

class Node {
constructor(data, next = null){
  this.data = data;
  this.next = next;
    }
}

class LinkedList {
  constructor(){
    this.head = null;
    this.size = 0;
  }
  // METHOD - Insert first node
  // The head becomes the new Node
  // data is passed to Node class
  // the head (Node) is passed as a pointer to Node class (next)
  insertFirst(data){
    this.head = new Node(data, this.head);
    this.size++;
  }
}

const ll = new LinkedList

ll.insertFirst(100)
ll.insertFirst(200)

console.log(ll)

// result 

// LinkedList {
// next: Node { data: 200, next: Node { data: 100, next: null } },
// size: 2
// }

At this point, pause and recreate the code by memory and fully understand how it all works

Keep in mind how the data flows, each new node created becomes the new head and points at the previous node.

Now let's add a method that prints the data for each node.

class Node{
  constructor(data, next = null){
    this.data = data;
    this.next = next;
  }
}

class LinkedList{
  constructor(){
    this.head = null
    this.size = 0
  }

  insertFirst(data){
    this.head = new Node(data, this.head)
    this.size ++
  }

 // METHOD printing each node's data
  printListData(){
    // set variable to current node
    let current = this.head

    // loop through nodes
    while(current){
      console.log(current.data)
      // in order to move to each node set current to next node
      current = current.next;
    }
  }
}


ll = new LinkedList

ll.insertFirst(100)
ll.insertFirst(200)
ll.insertFirst(300)

ll.printListData(ll)

// result 

// 300
// 200
// 100

Next a Method that adds to the end of the linked list

class Node{
  constructor(data, next = null){
    this.data = data;
    this.next = next;
  }
}

class LinkedList{
  constructor(){
    this.head = null
    this.size = 0
  }

  insertFirst(data){
    this.head = new Node(data, this.head)
    this.size ++
  }

  insertLast(data){
    // create a new node obj
    let node = new Node(data);
    // create current variable
    let current;


    // edge case if linked list is empty, node will be the first and last
    if(!this.head){
      this.head = node
    }else{
      //make current the first node
      current = this.head
      // loop through each node, makeing current the node being pointed to 
      while(current.next){
        current = current.next;
      }
      // once you reach the end of the list, break out of loop and add the node to end of list
      current.next = node
    }
    // increase size variable
    this.size ++
  }

  printListData(){
    let current = this.head
    while(current){
      console.log(current.data)
      current = current.next
    }

  }
}

l = new LinkedList

ll.insertFirst(100)
ll.insertFirst(200)
ll.insertFirst(300)
ll.insertLast(400)

ll.printListData(ll)

// result

// 300
// 200
// 100
// 400

Method that inserts a node anywhere in between as if there was an index

class Node{
  constructor(data, next = null){
    this.data = data;
    this.next = next;
  }
}

class LinkedList{
  constructor(){
    this.head = null
    this.size = 0
  }

  insertFirst(data){
    this.head = new Node(data, this.head)
    this.size ++
  }

  insertLast(data){
    let node = new Node(data);
    let current;


    if(!this.head){
      this.head = node
    }else{
      current = this.head
      while(current.next){
        current = current.next;
      }
      current.next = node
    }
    this.size ++
  }

  insertAt(data, index){
    // if index is out of range
    if(index > 0 && index > this.size){
      return;
    }
    // if indext is 0, just call the above method
    if(index === 0){
    this.insertFirst(data)
    return;
    }
    const node = new Node(data)
    let current, previous;

    // set current to first 
    current = this.head;
    let count = 0;

    while(count < index){
        previous = current; // Node before index
        count ++;
        current = current.next
    }
    node.next = current;
    previous. next = node;

    this.size++;
  }

  printListData(){
    let current = this.head
    while(current){
      console.log(current.data)
      current = current.next
    }

  }
}


ll = new LinkedList

ll.insertFirst(100)
ll.insertFirst(200)
ll.insertFirst(300)
ll.insertLast(400)
ll.insertAt(500,2)

ll.printListData(ll)



// result

// 300
// 200
// 500
// 100
// 400

Think you have an understanding how to manipulate data in a linked list?

Try the following;

  1. Remove at a index

  2. Get at a Index

  3. Clear entire list

Resources

I gathered all of this from a Brad Traversy video on Linked List. I really enjoy the way he explains things, as it makes learning this stuff easier. While I followed along with him in the video, I constantly paused and tried to recreate the code by memory and understand each line of code on how and why it works.

 
Share this