How JavaScript works: Lists vs Blockchain + implementation practices
This is post # 49 of the series, dedicated to exploring JavaScript and its building components. In the process of identifying and describing the core elements, we also share some rules of thumb we use when building SessionStack, a JavaScript tool for developers to identify, visualize, and reproduce web app bugs through pixel-perfect session replay.
In this article, we will be making a comparison between two interesting data structures, Lists and Blockchain. You must probably be thinking about how and why we are comparing a Blockchain to a List? If you have an idea of Blockchain before now, you should know that there are a few similarities between Lists — Linked List to be more precise and Blockchain.
Before we continue, please note that we will be comparing a Linked List which is an implementation of List to Blockchain. The List data structure has two implementations: Linked List and Array List. Our focus is Linked List but we have to talk about the List data structure for a more general understanding.
A Linked List is a linear structure containing data that is ordered and connected. Whereas a Blockchain is a series of blocks linked together, each block contains data and a hash number of the previous block. One noticeable difference is that a Linked List has a pointer function to each of its elements (or block technically) while Blockchain uses a hash function to recognize the older blocks.
We will look at the List data structure, its implementation which is the Array and Linked List, and how it is implemented in JavaScript. Also, for the Blockchain, we will discuss more on the Block Merkle tree and the implementation in JavaScript.
List
List is a common and simple data structure. It is a collection of different elements in an ordered manner. List is an Abstract data type(ADT) which means it is just a model where you can have your own implementation. When we say that a List is just a model it means it is a structure with specific features where you can make your own implementation.
The mandatory functionality In a List is to add and remove elements. It is more like a Set but a Set has more restrictions. Duplicate elements are not allowed in Sets.
Since we know that List is an Abstract data type it can be implemented in two common ways: the Array and Linked List. Also, other implementations include Stack and Vector.
Array List
This is the most common implementation of a List. Note that we are not talking about Array but Array List — they are different. Array List grows and shrinks/reduces automatically while an Array has a fixed size and cannot increase after it has already been declared.
Although this is slower than the standard Array, it is more powerful when a lot of manipulation is needed:
Basic Operations in Array Lists
The basic operations in Array Lists are very common;
- Adding data
- Accessing data
- Changing data
- Removing data
Linked List
Linked Lists are our focus. a linear structure that consists of a group of nodes in a sequence. Each node as you can see in the image below holds the data and the address of the next node. The important thing to note is that each node has a pointer to the next available node. The direction to the next node depends on the type of the Linked List.
Linked Lists are also used to create trees and graphs where there are nodes and vertices in-between.
Types of Linked Lists
- Single Linked List: This type of Linked List is unidirectional which means it can only be traversed in one way where the node has only one pointer to the next node.
- Double Linked List: This Linked List contains two pointers: each node contains these two pointers to the left and right node in the sequence.
- Circular Linked List: In this Linked List, the last node in the sequence contains an address to the first node, making it form a circular chain.
Applications of a List
Linked Lists can also be used to implement Stacks where the push
and pop
methods can be replaced to behave like a Linked List. The main reason for using a Linked List over an Array is because the size of data can grow and shrink automatically.
Looking at a real-world example, a Music player uses a Linked List where we can traverse the list in a forward and backward direction. This is the same as forwarding and rewinding the songs.
Another application is in Blockchain which is what we will discuss later and understand the differences. Each block in the chain contains information about the parent block. The first block/node in the chain is always known to be the genesis block.
List is also used in a Linux Process Manager where if you want to quickly get or identify the host structure you would have to use the Circular Linked List implementation.
Implementation
Our implementation will be that of Linked List because that is our focus. The Linked List is similar to Blockchain so it would be ideal to see how both are implemented.
Before writing each method we will need to create a Node class which will be an individual node in the List:
This takes two arguments: data and next which is the pointer to the next node.
In adding data to the list, we create the node, check if the head of the list is empty so we can add the new node to the head and tail of the list and increase its length. Notice that our Linked List has three properties: head, tail, and length.
The remove method takes the index parameter, checks if the index is out of range so it stops at that point. When removing the index 0, we just make the next node to be the head.
Blockchain
Blockchain is a set of blocks in a serialized and ordered manner which continuously grows as more records are added. It has only the ability to append data to the chain, updating and deleting previous blocks/nodes is not possible.
It has similarities to a Linked List but a Linked List has a pointer function while the Blockchain has a hash function. The hash function creates a hash for each block such that the previous block uses it to recognize the next block:
As earlier said, Blockchain does not have the pop
or remove
functions where data can be deleted because of its hashing algorithm that links blocks together. Blockchain itself is said to be a very complex topic, but once a few concepts are understood it becomes easy. Understanding that Blockchain is a data structure is a fundamental step in getting to understanding its complexity.
The purpose of each block in the chain is to hold data such as the transactions and the hash value and they are cloned to every node in the Blockchain network. One thing to note is that if a block is added to the chain, every node in the network has to have a copy of the data in the block and the added block is announced publicly to the network. This is a distributed ledger.
Block Merkle tree
We talked about a block being distributed and decentralized in a Blockchain network meaning that the content of a block is shared across different nodes but there seems to be a big problem which is “trust”. What happens if the transaction in a distributed ledger is altered at one node? What if the network is hacked and a block is altered, changing the data? This is where the Merkle tree comes in. Merkle tree helps in performing efficient data verification of each block before it is distributed to the network. This way it is not possible to tamper with a block because other blocks already distributed will not be the same data.
A Merkle tree is still a Binary tree where each node in the Blockchain network stores hashes instead of the data instead. For example, before data in a node is duplicated and distributed, a hash function has to act on that data(or each transaction in the block) and produce a hash instead. It is that hash that we then store and duplicate across. This makes the records tamper-proof.
Implementation
Let’s look at a simple way we can implement a Blockchain in JavaScript. This might not be optimal but it should provide some clarity.
The first thing we will need to create is the Block(I like to take a Block as a node).
Our Block is going to hold a time, data and a previous hash to the previous Block. We also need to use a hash function to hash all mentioned properties and store the value from the output. This is our getHash
method.
Next is to create a Blockchain that will contain all the created Blocks.
Just a quick reminder that this implementation is just a basic illustration and not the typical way a Blockchain is implemented. There is much more.
List vs Blockchain
A List implemented as a Linked List is what we are comparing to Blockchain and yes, they are both data structures. The Blockchain refers to the previous block using a hash while the List uses a pointer. Most arguments have been centered around Blockchain not being a data structure but a technology implementing a Linked List with consensus.
In my opinion, Blockchain is a technology, no doubt, still, a data structure but a lot of implementations have to be considered. The two have very different levels of complexity even at the abstract level, adding a new node is quite different on Blockchain with rules to be applied. Also, it is decentralized.
You have to be very careful about the data structures you pick for certain tasks, especially for ones that could potentially degrade the performance of your product.
A solution like SessionStack will allow you to replay customer journeys as videos, showing you how your customers actually experience your product. You can quickly determine whether your product is performing according to their expectations or not. In case you see that something is wrong, you can explore all of the technical details from the user’s browser such as the network, debug information, and everything about their environment so that you can easily understand the problem and resolve it.
There is a free trial if you’d like to give SessionStack a try.
If you missed the previous chapters of the series, you can find them here:
- An overview of the engine, the runtime, and the call stack
- Inside Google’s V8 engine + 5 tips on how to write optimized code
- Memory management + how to handle 4 common memory leaks
- The event loop and the rise of Async programming + 5 ways to better coding with async/await
- Deep dive into WebSockets and HTTP/2 with SSE + how to pick the right path
- A comparison with WebAssembly + why in certain cases it’s better to use it over JavaScript
- The building blocks of Web Workers + 5 cases when you should use them
- Service Workers, their life-cycle, and use case
- The mechanics of Web Push Notifications
- Tracking changes in the DOM using MutationObserver
- The rendering engine and tips to optimize its performance
- Inside the Networking Layer + How to Optimize Its Performance and Security
- Under the hood of CSS and JS animations + how to optimize their performance
- Parsing, Abstract Syntax Trees (ASTs) + 5 tips on how to minimize parse time
- The internals of classes and inheritance + transpiling in Babel and TypeScript
- Storage engines + how to choose the proper storage API
- The internals of Shadow DOM + how to build self-contained components
- WebRTC and the mechanics of peer to peer connectivity
- Under the hood of custom elements + Best practices on building reusable components
- Exceptions + best practices for synchronous and asynchronous code
- 5 types of XSS attacks + tips on preventing them
- CSRF attacks + 7 mitigation strategies
- Iterators + tips on gaining advanced control over generators
- Cryptography + how to deal with man-in-the-middle (MITM) attacks
- Functional style and how it compares to other approaches
- Three types of polymorphism
- Regular expressions (RegExp)
- Introduction to Deno
- Creational, Structural, and Behavioural design patterns + 4 best practices
- Modularity and reusability with MVC
- Cross-browser testing + tips for prerelease browsers
- The “this” variable and the execution context
- High-performing code + 8 optimization tips
- Debugging overview + 4 tips for async code
- Deep dive into call, apply, and bind
- The evolution of graphics
- Dockerizing a Node.js application
- A deep dive into decorators
- Best practices for data compliance
- Proxy and Reflect
- SVG and its use cases (part 1)
- Class static blocks + 6 proposed semantics
- Introduction to Graphs and Trees
- Introduction to PM2, Strongloop, and Forever + 4 tips for Production Process Managers
- Аdvanced SVG capabilities (part 2)
- Тhe publisher-subscriber pattern
- Stacks and Queues + tips for efficient implementation