Arrays

Everyone knows arrays, right? But do you really know how an array works in the CompSci sense? Yes there are arrays in JavaScript and other languages - but these things do quite a lot more than the traditional array. I'll get into that later.

An array is a collection of values that is stored in contiguous memory. This means that once you create an array, that's it! It can't be resized unless another block of memory is allocated. You can't add items to an array nor can you take them away. Iteration is fast and simple, however, because things reside right next to each other in memory.

Locating a value within an array can be done in two ways: by index or by iteration. These have time complexity implications (aka "Big-O") - do you know what they are?

Linked Lists

A Linked List is a very simple structure that consists of a "wrapper" around some data, called a "node" that also has a pointer to the next node in the list. A traditional linked list goes one direction: forward.

Here's some code you could start with:

class Node{  constructor(val){    this.value = val;    this.next = null;  }  addNext(val){    this.next = new Node(val);    return this.next;  }}

A linked list is much more flexible than an array, why do you think that would be?

Doubly Linked Lists

Just like a regular linked list, but with these you can go forward and backward. A very popular interview question might ask you to create a linked list from scratch. Can you do that? Maybe after you watch the video you can.

Both doubly and singly-linked lists have limitations - do you know what those might be? One of them has to do with accessing a particular value. What do you think the Big-O of a traditional linked list is?

If you're going for a junior position at a large company, you might be asked one of the following:

  • How would you reverse a linked list?
  • How can you tell if a linked list has a cycle?
  • Write some code to remove a node from a linked list without breaking the list.