miku86

JavaScript Data Structures: Singly Linked List

2019-11-14

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 :)