Data Storage

1.2 Data Structures

Data Structures

Primitives

In JavaScript all values are either a primitive or an object. Primitives are just values. They have no properties or methods or events. If your variable is not one of these then it is an Object. HTML element? - Object. Function? - Object.

The Primitives types are:

• Number
• String
• Boolean
• null
• undefined
• Symbol
• BigInt (numbers that exceed Number.MAX_SAFE_INTEGER)

Variables of these types are just values. Although, if you think about it, we have been using String methods since first semester. So, wtf?

Javascript will create an Object instance of type String behind the scenes whenever you need to use one of those string methods. JS creates the object instance and gives it the value from your String primitive. It will then run the method and update the value of your primitive with the result of the method.

Copying and Passing Variables

When you assign a primitive to a new variable or pass variable with a primitive value to a function, you are actually creating a copy of the value for the new variable.

With Objects when you assign it to a new variable or pass it to a function you are passing a reference to the original object.

Arrays

An Array is a numbered list. Each of the numbers is called an index. We use the square bracket syntax to access each of the values. In some programming languages you need to provide a specific size|length for the Array when you create it. JavaScript is a bit more flexible in that you can create an Array and then continue to add and remove any number of elements you want to the Array.

let a1 = new Array(); //new empty Array object
let a2 = []; //empty Array literal
let a3 = new Array(3); // new Array object with length of 3.
a2[78] = 5; // add the number 5 at index 78. The length of the array will be 79
a2.forEach((item) => {
  console.log(item);
}); // will only output 78 as that is the only value in the Array.
for (let i = 0; i < a2.length; i++) {
  console.log(i, a2[i]);
} // will output the index and `undefined` 77 times then 78 78.

If you create an empty array you can place a value at any index. JS will automatically put undefined in all the other index positions up to that position. The forEach method will skip over the undefined values. The for loop will show every index.

We use the push() and pop() methods to add or remove things at the highest index. We use unshift() and shift() methods to add or remove items at the zero index position. slice() can remove any index(es). splice() lets us remove any index(es) and replace it with a new value(s).

The most useful Array methods for working with data in Arrays are forEach, map, filter, reduce, find, findIndex, some, every and includes. You should be familiar with all these methods and ready to use them on a regular basis.

Objects

The general description of an Object in JavaScript is everything that is not a Primitive value.

Objects in JavaScript can have properties, methods, prototypes, and events. That means a function, which is an object, can be given properties.

However, for the purposes of data structures we are talking more about things like Object literals. Eg:

let data = {
  id: 123,
  name: 'Bilbo',
  weapon: 'Sting',
};

Data Objects in JavaScript are like Hash Tables. They are made up of key-value pairs.

All the keys must be strings or symbols. A symbol is a value that is guaranteed to be unique. If you try to use something other than a String for a key then JavaScript will convert what you used into a String. As an example, let's use the Object we created called data as one of the keys in a new Object.

let obj2 = {
  id: 456,
  [data]: 'His name is Bilbo', //wrap the variable in square brackets to reference it
};
for (let prop in obj2) {
  console.log(prop);
}
//output will be
// id
// [Object object]
console.log(obj2[data]); //data gets converted to [Object object]
// and we are outputting  obj2['[Object object]']
let data2 = {
  id: 34534,
};
obj2[data2] = 'His name is Gandalf';
//this will overwrite obj2[data] with the new string becase
// it is also interpreted as obj2['[Object object]']

Our variable data gets converted to the string [Object object]. Which means that if you used a whole bunch of objects as the keys they would all overwrite each other and the last value would be the only one saved.

The values can be anything you want. Just remember that if you have another object as a value then you actually have a reference to the other object, not a copy.

let obj3 = {
  one: data,
  two: data2,
};
//if we change the contents of data or data2 the changes will be seen inside obj3 too

Sets

A Set is similar to an Array. The main difference between an Array and a Set is that a Set makes sure that all its values are unique. If you try to add a duplicate then it will be ignored.

You can call new Set() to create an empty set or pass in an Array literal and have it converted to a set. Duplicates will be removed during conversion.

let names = new Set();
names.add('Steve'); //adds Steve to the set
names.add('Tony');
names.add('Robert');
names.add('Su Cheng');
console.log(names.size); //4
names.delete('Tony'); //removes Tony from the set
names.delete('Vladimir'); // does nothing because Vladimir is not in the list
names.has('Robert'); //true
names.forEach((item) => console.log(item)); //loops through all the items
names.clear(); //empties the whole set

MDN reference for Set (opens new window)

Maps

A Map is like an object in that it is a collection of key-value pairs.

However, unlike an Object the keys can be ANYTHING. You can use any Primitive or Object as a key. A Map also remembers the order that items were added. A Map has a size property. Unlike Objects, Maps are iterable. A Map cannot be directly converted to JSON due to the non-string keys.

The methods for maps are close to the ones for Set.

let m = new Map();
m.set('key1', 'value'); // adds `value` with the key `key1`
m.get('key1'); // `value`
console.log(m.size); //1
m.has('key1'); // true
m.forEach((val, key) => {
  console.log(key, val); //output the keys and values
});

m.delete('key1'); //removes the value and key at `key1`
m.clear(); // empties the whole map

Maps and Sets also have keys(), values(), and entries() methods that return an iterator that can be used to loop through the keys, values, or both. Basic usage with a for...of loop is like this:

for (let val of myMap.values()) {
  console.log(val);
}

We will talk more about iteration vs enumeration later.

MDN reference for Map (opens new window)

Stacks

The Stack follows a LIFO last-in-first-out model where the last item added to the stack is the first item removed. So, we are basically talking about the Array pop and push methods. It will also need to have a size method (like the Map and Set types).

With a Stack think a stack of Lego bricks. You can only add to the top or remove the top one.

The idea of a call stack is something that we see in the execution of our JavaScript programs. Within your error messages in the browser you can view the call stack. This is a stack of all the functions that were called from most recent to oldest.

A basic implementation, in JavaScript, of a Stack would be like this:

function Stack() {
  this._storage = new Map();
  //we could use other structures instead
  //if we use a string then it will need a separator
  this._index = 0;
  //index will be the length|size
  //it will also be the next number to use for adding an item
}
Stack.prototype.push = function (item) {
  //add to the stack
  this._storage.set(this._index++, item);
  //increment after adding the item
};
Stack.prototype.pop = function () {
  //remove from the stack
  //return the removed item
  let item = this._storage.get(--this._index);
  //decrement index before using it
  this._storage.delete(this._index);
  return item;
};
Stack.prototype.peek = function () {
  //see an item without removing it
  return this._storage.get(this._index - 1);
};
Stack.prototype.size = function () {
  //determine the size of the stack
  return this._index;
};

let pets = new Stack();
pets.push('Dog');
pets.push('Cat');
pets.size(); //2
let next = pets.peek(); //Cat
let removed = pets.pop(); // Cat

Queues

Queues are similar to a stack except for the order in which items are added. In the case of a queue, the first item in is the first item out - FIFO. Rather than push() and pop() methods, a queue has an enqueue() method for adding items and a dequeue() method for removing items.

If we think about this in terms of an Array the enqueue method is like the push and the dequeue method is like the shift method.

function Queue() {
  this._storage = {};
  this._head = 0; // key for next in line
  this._tail = 0; // key for last in line
  //head and tail are both numbers but when used as object keys
  //they will be converted to a string value before accessing the object
}
Queue.prototype.enqueue = function (value) {
  this._storage[this._tail++] = value;
  return this.count();
};
Queue.prototype.dequeue = function () {
  let element = this._storage[this._head];
  delete this._storage[this._head];
  if (this._head < this._tail) this._head++;
  return element;
};
Queue.prototype.peek = function () {
  return this._storage[this._head];
};
Queue.prototype.count = function () {
  return this._tail - this._head;
};
Queue.prototype.contains = function (value) {
  for (var i = this._head; i < this._tail; i++) {
    if (this._storage[i] === value) return true;
  }
  return false;
};

let q = new Queue();
q.enqueue('Alex');
q.enqueue('Devon');
q.enqueue('Riley');
q.enqueue('Cole');
q.count(); // 4
q.contains('Riley'); //true
let next = q.peek(); // Alex
let name = q.dequeue(); // Alex

Linked Lists

Another data structure is known as a Tree. A Tree has nodes and those nodes have children. When a node has no children then you can refer to it as a leaf. The tree also has one root node. The DOM uses a tree structure to define all the nodes in your webpage - text nodes and element nodes. A special type of tree is known as a Linked List. A link list is a tree but each Node is only allowed to have one child.

node -> node -> node -> node -> node

The Linked List has one root node. Each of the nodes will have two properties - a value and next. The value property is the data that the node holds and the next property is the reference to the next node. Each node only is aware of one other node. This is why this is sometimes called a singularly linked list. The final node in the list has its next property set to null.

To build a Linked List we need to actually have two constructors - one for the list and one for Nodes.

//The Node constructor
function Node(value) {
  this.next = null; //the last node will have null as next value
  this.value = value;
}

//The LinkedList constructor
function LinkedList(headValue) {
  if (headValue === undefined) console.log('Must provide value for first node');
  this.head = new Node(headValue);
  this.tail = this.head; //means only one node in LinkedList
}

LinkedList.prototype.forEach = function (callback) {
  let node = this.head;
  while (node) {
    callback(node.value); //pass the value, not the whole node to the callback
    node = node.next;
  }
};

LinkedList.prototype.print = function () {
  let result = [];
  this.forEach(function (value) {
    result.push(value);
  });
  return result.join(', ');
};

LinkedList.prototype.insertAfter = function (node, value) {
  // get reference to former next
  let oldNext = node.next;
  // create new node
  let newNext = new Node(value);
  // store it as the new next
  node.next = newNext;
  // set next for the new node to be the old next
  newNext.next = oldNext;
  // if reference node is tail, set tail to newNext
  if (this.tail === node) this.tail = newNext;
  return newNext;
};

LinkedList.prototype.removeAfter = function (node) {
  // store reference to removed node
  let removedNode = node.next;
  // if node is tail, then there's nothing to remove
  if (!removedNode) return 'Nothing to remove';
  // get reference to node after removed node
  let newNext = removedNode.next;
  // set newNext as the next node
  node.next = newNext;
  // remove reference from removed node to linked list
  removedNode.next = null;
  // if removedNode is tail, set tail to node
  if (removedNode === this.tail) this.tail = node;
  return removedNode;
};

LinkedList.prototype.insertHead = function (value) {
  let newHead = new Node(value);
  let oldHead = this.head;
  this.head = newHead;
  newHead.next = oldHead;
  return this.head;
};

LinkedList.prototype.removeHead = function () {
  let oldHead = this.head;
  let newHead = oldHead.next;
  this.head = newHead;
  oldHead.next = null;
  return oldHead;
};

LinkedList.prototype.findNode = function (value) {
  let node = this.head;
  while (node) {
    if (node.value === value) return node; //exit when found
    node = node.next;
  }
  return 'No node with value: ' + value + ' found.';
};

LinkedList.prototype.appendToTail = function (value) {
  let newTail = new Node(value);
  // with myList.tail property: O(1)
  this.tail.next = newTail;
  this.tail = newTail;
  return newTail;
};

Note that there is no size or count methods in a Linked List.

Other Data Structures

For your own future edification I recommend that you research Doubly Linked Lists, Trees, Binary Search Trees and Graphs.

Future Types

Tuples and Records are two new datatypes that are currently under consideration for addition into JavaScript. They will give us immutable versions of Arraysand Objects that can be put into JSON and extracted from JSON as well as letting us do deep comparisons between the objects.

What to do this week

TODO

Things to do before next week.

• Read all the content from Modules 1.1, 1.2, and 2.1.
• Prepare questions to ask in class.
• Start working on Hybrid one

Watch Iterable vs Enumerable

Watch Immutability in JavaScript

Watch video about Prototypes

Watch video about keyword this

Learn about shallow and deep copying of objects

Learn about WeakSets, WeakMaps, and the new Week Ref proposal. * Advanced Concepts ahead