The Simplest guide to digest

Table of contents

• Introduction
• Concepts and properties
• Linked-list types
• Upsides and downsides
• Big O time complexity
• Real use cases

From my point of view, data structure and algorithms are the heart and foundation of computer science. I think they’re the most important topics we should care and learn about before anything else.

This is the beginning of a data-structure series with their implementations in JavaScript with the ECMAScript 6 specification.

Firstly, I would like to walk through the concepts surrounding all of this. We’ll get to know (or brush you up on) what a linked list is — its types, a few cons, a few pros, its complexity, and the real use cases where we could and should use them.

Note: JavaScript doesn’t implement a built-in linked list type as C# and JAVA do — it uses arrays instead.

This post is split up into two main sections: understanding linked lists and implementing them.

Understanding

Practice without theory is blind, but theory without practice is sterile. So we need both. First of all, we need to digest the main concepts.
Concepts and properties

Linked list

A linked list is a dynamic data structure that stores the values sequentially. It is a single chain of nodes connected by pointers.

Wait. Wait. Why is it dynamic? Because we are able to change the linked list elements at run time. This means the memory size allocated can be modified when the program is running or, in other words,can grow or decrease as needed.

Comparison with arrays

A linked list allows us to add or remove elements at ease. Conversely, the arrays store data with a specific/fixed memory size allocated. You can't change it. To grasp it fully let’s see the next analogy.

Analogy: The linked list as train cars

Let’s say that a linked list is like train cars. The train cars are linked in a specific order at the beginning. However, they could be loaded, unloaded, and changed at ease.

Their growth is dynamic since we have the ability to add or remove a new train car at any point on the train and also change its content.

Analogy: Arrays as bus seats

An array is similar to bus seats.
The bus (memory) has a fixed number of seats, which are the items of the array. They can’t grow. However, despite the size of the seats being fixed, they can be used by different passengers. Thus, the values could change at some time.

Nodes

A node is the most basic building block for many common data structures.
For a linked list, it provides a mechanism to contain a piece of data and also for connecting itself to other nodes via the object reference pointer (this is known as the next pointer).

Head and tail

The head, as its name says, is the first node in the list, and the tail is the last one.

Node chains

Node chains are how nodes can be linked together to build chains of nodes.

Mainly operations with a linked list

Adding

Add to front
Add to the end
Add to at a random position

Removing

Remove to the front
Remove to the end
Remove at a random position

Accessing and Search

Linked-list types

There are other types of linked lists. In this article, we’re only going to mention the ones most necessary to be aware of.

Doubly linked list

Unlike the singly linked list, in a doubly linked list, each node contains a reference to the previous node and also to the next node.

Circular linked list

As the name implies, it’s a chain of nodes where all of them are connected to form a circle.

Upsides & Downsides

Upsides and downsides give you an idea when and where a linked list is helpful or under which scenarios they’re the best option to solve a problem. So let's list them …

Upsides

• It’s a dynamic data structure. As we mentioned above, it allows changing the elements at run time either growing or shrinking dynamically
• Insertion and deletion doesn’t require reorganizing the entire data structure
• There’s no need to define an initial size.
• Other data structures, such as stack and queue, can be implemented using a linked list

Downsides

• Random access is not allowed — we must start from the first node if we want to access an element
• Search operations are slow since you need to traverse your input to find any elements — these operations have linear complexity O(n)

Big O time complexity

Adding and removing items

These operations only involve allocating the data and updating a few pointers, so its complexity remains constant O(1).
Regardless of how many nodes are in the list, it always will be performed in constant time.

Accessing and searching

Theses operations involve traversing the entire input to access/search items in the list. This means, its complexity is linear O(n). Complexity will grow in direct proportion to the size of the input data.

Real use cases

The simplest way to use the linked list in the real world is to think about the previous and next options. Here some examples of them.

• Use a linked list to implement a stack and a queue
• In real applications that use previous and next elements, such as an image viewer, you’ll find that since the previous image is linked to the next one and the previous video is linked to the next one, on a browser we can use a linked list to link the previous link to the next one
• Undo and redo behavior in a program — such as Photoshop, MS Word, or whichever program/software uses that behavior

So, as you can see, in all real applications where we need previous and next, we can easily use the linked list.

Implementation

Now that we’re not going in blind and know everything about linked lists, we’re ready to go and implement one.
I don’t like long posts. So in the next point, we’re going to explain step by step how to implement a linked list using the ES6 features.

Thanks for reading! If this story turned out to be interesting, I’d really appreciate it if you like and share it with your friends. I hope to add a little bit more knowledge to you.
Supporting and follow me on my blog and Medium