Data Structures: Linked Lists

Welcome back to my Data Structure learning series. Today we are going to learn Linked Lists and how to implement it in JavaScript.

What are Linked Lists?

Linked Lists are simple, dynamic, lightweight, and flexible data structure. Like arrays, elements are stored sequentially in the list; however, elements are not stored in adjacent blocks of memory but rather in “nodes” or objects that are connected via memory pointers. They are useful for easy addition or removal of arbitrary data at the head and tail of a list, without re-indexing elements, preventing the worst performance case of an array.

The first element or entry point of the linked list is called the head. Each element or node in the linked list uses a pointer to indicate the element that comes after it. The last element points to null. If the list is empty, the head will reference to null.

Two Types of Linked Lists:

Singly Linked List

In singly linked list, we can only move forward through the list (but not backward), with each node pointing to the next one. The diagram below illustrates the singly linked list concept:

Doubly Linked List

Here, the nodes in the list have two pointers: one pointing to the previous node and another pointing to the next node

As shown in the diagram, with doubly linked list, we can move both forward and backward.

Implementing a Singly Linked list in JS

We will be implementing how to create a list as well as the common linked list operations and time complexity for each: append, prepend, insert, remove, and find a node, as well as getting the size of the list.

This is a quick cheat sheet summarizing the time complexity of singly linked list operations:

Final Note

Linked list are best when we need to efficiently insert or delete items from a list, and when we need a flexible list size. Unlike arrays, it does not require re-indexing other elements in the list. On the other hand, linked lists by themselves aren’t as good for indexing as arrays and they use more memories as it they need extra space to store the pointers. Additionally, search operations are slow with linked lists as there is no direct access to data (no keys/indexes). We must iterate through the list sequentially to perform a lookup.

That’s all I have on linked lists. I hope you found this helpful.

Until next time,

Happy learning / coding!!

Originally published at https://vanessuniq.github.io on February 7, 2021.