Javascript Basic Data Structures

Array

A JavaScript array is a dynamically-sized collection of elements, with the property that each element is uniquely identified by an integer key (called "index") starting from 0, can be of any type, and can be individually retrieved or modified. We call the side with the lowest index the "start" / "beginning" of an array, and the side with the highest index the "end". Access an element by an index is O(1).

Indexing

Only non-negative integer indices are allowed, and unlike in Python, accessing negative indices with bracket notation does not give you access to the last elements of the array.

Subarray slicing can be done with slice(start_index, upto_index), and the slicing indices are left-inclusive and right-exclusive. The upto_index can be omitted to extract till the end of the array, and both start_index and upto_index can be negative to indicate an offset from the end of the array.

1const arr = [0, 10, 20, 30, 40, 50];
2let subarray = arr.slice(2, 5);
3// [20, 30, 40]
4subarray = arr.slice(-2);
5// [40, 50]

Common Array Operations

  • push(item) adds item to the end of array and returns the array length; amortized O(1)
  • pop() removes and returns the last element of the array; amortized O(1)
  • shift() removes and returns the first element of the array; O(n)
  • unshift(item) adds item to the start of the array and returns the array length; O(n)
  • splice(start_index, count_to_remove, add_item1, add_item2, ...) removes and returns count_to_remove item(s) from an array given its/their index and optionally replaces them with add_items; O(n)

A note on Javascript runtimes: JavaScript array performance varies depending on the implementation, but almost always supports amortized O(1) time append/remove at the end of an array. Some implementations also support fast prepend/remove at the beginning.

In general, to iterate through a list, for loop is easier to reason than while since there's no condition to manage that could skip elements. In JavaScript, you can iterate through a list with C-like for loops, forEach loops, and for...of loops. The for...of loop can iterate over any iterable object, such as String, Array, and Map.

1const numbers = [20, 6, 13, 5]
2// C-like for loop fetches elements using indices
3for (let i = 0; i < numbers.length; i++) {
4    const number = numbers[i];
5    console.log(number);
6}
7
8// forEach loop directly fetches elements and their indices
9numbers.forEach(function(item, index) {
10    console.log(`${item} ${index}`);
11});
12// 20 0
13// 6 1
14// 13 2
15// 5 3
16
17// for...of loops directly fetches elements
18for (const number of numbers) {
19    console.log(number);
20}

Linked List

JavaScript doesn't have a built-in linked list. Normally at an interview, you'll be given a definition like this:

1// create linked list with class constructor
2class LinkedListNode {
3    constructor(val, next = null) {
4        this.val = val;
5        this.next = next;
6    }
7}
8
9// create linked list with function constructor
10function LinkedListNode(val, next) {
11  this.val = val;
12  this.next = next;
13}
14
15// create linked list with object literal
16const linkedListNode = { val: 1, next: { val: 2, next: null } };
  • append to end is O(1)
  • finding an element is O(N)

Stack

Javascript's Array also doubles as a stack. For an array const stack = []:

  • push: push(item), amortized O(1)
  • pop: pop(), amortized O(1)
  • size: stack.length, O(1)
  • top: stack[stack.length - 1], O(1)

Stack is arguably the most magical data structure in computer science. In fact, with two stacks and a finite-state machine you can build a Turing Machine that can solve any problem a computer can solve.

Recursion and function calls are implemented with stack behind the scene. We'll discuss this in the recursion review module.

Queue

←
↑TA 👨‍🏫