# 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. 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;
}
}

constructor(){
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;
}
}

constructor(){
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.size++;
}
}

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

console.log(ll)

// result

// 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;
}
}

constructor(){
this.size = 0
}

insertFirst(data){
this.size ++
}

// METHOD printing each node's data
printListData(){
// set variable to current node

// 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.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;
}
}

constructor(){
this.size = 0
}

insertFirst(data){
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
}else{
//make current the first node
// 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(){
while(current){
console.log(current.data)
current = current.next
}

}
}

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;
}
}

constructor(){
this.size = 0
}

insertFirst(data){
this.size ++
}

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

}else{
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
let count = 0;

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

this.size++;
}

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

}
}

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.