JavaScript Data Structures: Singly Linked List

Intro

This is a new series about Data Structures in JavaScript.

I will give you some details about the Data Structure and then we implement the Data Structure in JavaScript. The parts will be short, because most people have to familiarize with the logical steps and concepts behind it.

If you aren't familiar with Big O Notation, read the article in the Simple Wiki. Don't get caught in the details, only try to grasp the concept.

Simple example: If I have a todo list with pen and paper and I want to add a new todo to the end, that's O(1). Why? No matter how long the list actually is, adding a new todo to the end always requires the same amount of work.

Today we start with a simple one: Singly Linked List.

Singly Linked List

• simple example in real life: a treasure hunt, where you have a starting point and have to seek places and solve riddles in a particular order; the current place knows about the next place, but the current place doesn't know about the previous place

What is a Singly Linked List?

• consists of nodes
• each node has a value and a pointer to the next node (or null at the end of the list)
• has a head (=start), a tail (=end) and a length
• has no index like an Array
• "singly" because only one connection to another node (the next one)
• access has always to start from the start (O(N))
• insertion is cheap (O(1))
• deletion can be cheap (O(1) (head) or O(N) (tail))

What is an Array?

• every element has an index
• accessed is cheap (O(1)) (every element has an index)
• insert and delete can be expensive (O(N)) (index has to be shifted)

Big O of Singly Linked List

• Access: O(N)
• Insert: O(1)
• Delete: O(1) (head) or O(N) (tail)
• Search: O(N)

When to use a Singly Linked List instead of an Array?

• if you insert data often (SLL: O(1))
• if you delete data at the head often (SLL: O(1))

When NOT to use a Singly Linked List instead of an Array?

• if you access data often (Array: O(1))

---

Next Part

We will implement the first part of our Singly Linked List in JavaScript. If you want to be notified, subscribe :)

---

Questions

• Did you ever use a Singly Linked List in a project? Why?
• Do you have some good real life examples for a Singly Linked List?

Comments

[shivang]

Hii,

For arrays, isn't insert operation have O(1) complexity (since you don't have to shift anything when inserting) while deletion have O(n) (Referring to "What is an array" section)??

Thanks,

[miku86]

Hi @shivang,

if you have an array,
e.g. const myChars = ["A", "B", "C"],
then its elements are:
myChars[0] = "A",
myChars[1] = "B",
myChars[2] = "C".

If you add a new element at the beginning,
then every element has to get updated,
e.g. myChars[1] goes from B to A,
myChars[2] goes from C to B etc.

This is the worst case, because we have to update N elements.
In the middle of the array we have to update N/2 elements,
what also boils down to O(N).

Greetings
Michael

[shivang]

Thanks for reply and clarification!!!

[Adam Crockett 🌀]

Shame we don't get direct mem pointer access.

[John Kazer]

O (ah hah) finally an explanation of why use linked lists... thanks.