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;
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.
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;
Remove at a index
Get at a Index
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.