Let's Link! My Journey With Linked -> Lists

Paul Sobers — Fri, 06 Mar 2020 14:37:30 +0000

It doesn’t matter what language we start using when we begin our journey to code. You eventually learn they are different types of data structures. There are many ways & tools to solve a problem, the issue is knowing the right time to use these tools to best solve your problem.

What Is A Linked List?
To understand what a linked list is, you first need to understand what type of data structures they are. A linked list is a collection of nodes and the only properties they have are their data and their next reference. Linked lists have a linear type of data structure—meaning, there’s a sequence and an order to how they are constructed and traversed. We can think of a linear data structure like a game of hopscotch: in order to get to the end of the list, we have to go through all of the items in the list in order, or sequentially.

In a linear data structure to access any element/node, you have to traverse the entire list.

Different Types Of Linked Lists:
A singly linked list is a collection of nodes that collectively form a linear sequence. Each node stores a reference to an object as well as a reference to the next node of the list.
Example:

class Node:
        Def __init__(self,value):
            self.value = value
            self.next = next    

a = Node(1)
b = Node(2)
 c = Node(3)
 a.next = b
 b.next = c
// 1 → 2 → 3

So, just as a node can reference it’s subsequent neighbor node, it can also have a reference pointer to its previous node, too. Because there are two references contained with each node, we call this a doubly linked list. This can be helpful if we want to traverse our data structure not just in a single track or direction, but also backwards, too.
Example:

class Doubly_LinkedListNode(obj):
        def __init__(self,value):
            self.value = value
            self.next = next    
            self.prev = prev

a = Doubly_LinkedListNode(1)
b = Doubly_LinkedListNode(2)
c = Doubly_LinkedListNode(3)
a.next = b
b.prev =a
b.next = c
c.prev = b
    // 1 → 2 → 3
          ←    ←

For a singly linked list, the tail node points to null. Conversely, a circular linked tail node refers back to a previous node.

Example:

class Node(obj):
        Def __init__(self,value):
            self.value = value
            self.next = next    

a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
c.next = a
// 1 → 2 → 3
   ^_______^

Why use a Linked List Instead Of an Array?
Memory Management:
One big difference between linked lists and arrays is the memory allocation and the space that’s needed under the hood of your computer every time you create a linked list or an array. What do I mean by this? Each time you create an array, your computer needs a certain amount of space in it’s memory. The space in an array is stored in a block-like structure. If the space next to the last item is not free, your computer relocates or shifts every element over making space for the new item. When a linked list is created, the space is stored anywhere in memory. Linked lists can be scattered throughout the computer’s memory.

Array space in computer space:
Visualize going to the theaters with your friends. Typically, you want to sit with your friends and if one row doesn’t have a seat you check the next row until you have a space that accommodates all of you.

Linked List in computer space:
Visualize going to the theaters with your friends again but this time it’s a really popular new movie and you guys are dying to see it. This time you can’t all sit together so you split up and find any seat available. Each friend has a reference to the next friend.

Reference Passing in JavaScript

Paul Sobers — Wed, 18 Dec 2019 19:20:18 +0000

Before we talk about Pass by Value and Pass by Reference, we have to talk about variables. Variables are bindings that hold values. Often times we want to change or store that value somewhere, and when we assign a value to a variable our computer stores that data in the computer’s memory. Memory is stored in one of two places: the Stack or the Heap. A Stack is a data structure that is used to store elements in Last-in First-out (LIFO) order, which I will explain in more detail later. A Heap is a data structure where objects are stored. Heaps are slower to access but are better suited for long term storage. You can think of “Stack” as plates being placed upon each other one by one, making a stack of plates. And you can think of “Heap” as the cupboard that holds a set of many different unordered plates.

When variables are declared or functions are called, they are placed on the stack.
Here’s an example:

const multiplyByTwo = (number) => {
    let calculator = number * 2;
    return calculator;
}

let salary =  25000;
multiplyByTwo(salary); // 50000
console.log(salary); // 25000


salary = multiplyByTwo(salary); // 50000
console.log(salary); // 50000

On line 5, we declared a variable, salary, and assigned it a value of 25,000. Here, Javascript stores your variable on the Stack part of the memory. If we go back to our model of the stack of plates, you can envision that when the function on line 6 is executed, it returns the variable value that was last placed on top. Ultimately, that plate then falls off of the stack first because it was last placed there.

When you store variables on the stack, it is faster to access. Large objects that have large data values that will take longer to access are stored on the heap rather than the stack.

Let’s go back to my first example to explore pass by value and pass by reference. Pass by value refers to copying the value of a variable and passing that value to a function as an argument. For example, on line 5, we defined salary and assigned it a number value 25,000 and we passed that number value on line 6 when we execute our function: multiplyByTwo. We are passing the number value 25,000 as an argument to our function and our function is performing our code and returning 50,000. Note when we run line 7, our value is still 25,000, meaning we are just passing the value. To visualize this, imagine a blue cup filled with coffee. To pass by value, we would grab another blue cup and fill it with coffee. Ultimately, what we do with the second cup doesn’t affect the first cup, they simply have the same properties (blue cup and coffee.)

When a variable is passed by reference, the function receives a pointer to an address in the memory block of your computer. When a variable is passed to a function by reference, the function is able to mutate the original value of the variable. To visualize this, in the coffee example, pass by reference assumes that, instead of just passing our friend a copy of the copy, we would hand over the original blue cup of coffee for them to modify. (for example, adding cream and sugar.)

I chose to write this blog on Pass by Value and Pass by reference because as you can see, these ideas can seem extremely complicated. But when you slow down and start from the very beginning, you realize how simple and helpful this concept might be to your work.

Paul Sobers

DEV Community: Paul Sobers

Let's Link! My Journey With Linked -> Lists

Reference Passing in JavaScript