Table of contents
- Introduction
- Concepts and properties
- Linked-list types
- Upsides and downsides
- Big Otime 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
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 cant 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 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 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 post, we’re going to explain step by step how to implement a linked list using the ES6 features.
Thanks for reading!
