Arrays

Data Structures and Algorithms

This is part of my series of posts on Data Structures and Algorithms which I’ve created in order to consolidate my knowledge. You can find a collection of the posts here.

Arrays are a fundamental data structure and are used in just about every programming language out there. Because they are built in, they are considered to be very efficient and are a good choice for many operations.

So why use arrays? They’re great because they offer:

    - Fast lookups

    - Fast push/pop

    - Ordering (as arrays are ordered via an index and adjacent in memory space, they're really fast)

Arrays have some cons though as:

    - They have slow inserts and deletes as you have to shift all the items of an array when the inserted/deleted value isn't at the very start of end

    - When using a static array, you need to allocate memory ahead of time. A dynamic array removes this issue though as the language handles memory allocation for you.

Tip: Arrays have the smallest footprint of all the data structures.

Array Run Times

                | Operation | Runtime |
                | --------- | ------- |
                | Lookup    | O(1)    |
                | Push      | O(1)    |
                | Insert    | O(n)    |
                | Delete    | O(n)    |

Working with arrays

Note: I’ll be working with Javascript since it’s one of my 2019 goals.

Creating Arrays

To create an array in Javascript is simple. Just write:

let myArray = []

This create an array with a default value of zero. It’s empty. You can see this by running print (myArray.length).

You can also create an array from a set of values. Javascript doesn’t require you to keep the same types of value in an array. A single array can store an object, a string, another array, etc. For example:

let myArray = [1, "Ruairidh", true]

Manually implementing an array

So we know that arrays offer several different operations - if you’re not then you can find out more here.

As practice we can implement an array ourself:

class MyArray {
  constructor() {
    this.length = 0
    this.data = {}
  }

  get(index) {
    return this.data[index]
  }

  push(item) {
    this.data[this.length] = item
    this.length++
    return this.length
  }

  pop() {
    const lastItem = this.data[this.length - 1]
    delete this.data[this.length - 1]
    this.length--
    return lastItem
  }

  delete(index) {
    const item = this.data[index]
    this.shiftItems(index)
  }

  shiftItems(index) {
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i++]
    }
    delete this.data[this.length - 1]
  }
}

const newArray = new MyArray()
newArray.push("hi")
newArray.push("Coffee pls")
newArray.push("Delete me")

console.log(newArray)

newArray.delete(2)

console.log(newArray)

Strings as Arrays

Something that you often see in coding questions such as those on LeetCode or HackerRank are problems which require you to manipulate a string somehow. People struggle with this but when you think about it, a word is a bit like an array of letters. You can split the words or letters as you need and then manipulate them as you would any other array element.

For example, let’s say that we wanted to make a little function that reversed a string. Perhaps something like this would work:

reverse = str => {
  if (!str || str.length < 2 || typeof str !== "string") {
    return "You need to enter a string."
  }
  const backwards = []
  const totalItems = str.length - 1

  for (let i = totalItems; i >= 0; i--) {
    backwards.push(str[i])
  }

  return backwards.join("")
}

So if we then ran:

reverse('Hello')

You would get:

olleH

Easy, right?