List ADT: Data Structures & Algorithms in JavaScript P.1

I’m learning about data structures and algorithms in JavaScript. I’m using various online resources and going to be sharing my notes as a series of blog posts. The topics are below:
  • Data Structures: List ADT | Linked Lists | Trees, Tries & Graphs | Stacks & Queues Heaps | Hash Tables
  • Algorithms: Breadth-First Search | Depth-First Search | Binary Search | Merge Sort | Quick Sort
  • Concepts: Memory (Stack vs. Heap) | Recursion | Big O Time & Space
Why even learn Data Structures & Algorithms?
  • Quite simply because Algorithms + Data Structures = Programs (Niklau)
  • Any program is going to need some type of data structure to store and manage the data that it is manipulating and one or more algorithms for translating that data from its input form to its output form.
  • There is always more than one data structure or algorithm for a particular problem so studying the pros and cons of each type is a critical skill for a programmer.

So, first up…

1. List ADT (Abstract Data Type)

  • Lists are the most ubiquitous organizing tool that we all have.
  • Computers also use lists to organize and store data.
  • Lists are good especially if we have small number of items to store and don’t need the data to be sorted. Or if we don’t need to perform long searches on them.
  • A list is simply an ordered sequence of data.
  • Each data item stored is called an element and can be of any data type.
  • You can append an element to the end of a list, or you can insert an element after an existing element or at the beginning of a list. You can remove elements by using a remove operation.
  • A list has a front and an end. The next operation moves you to the next element while the prev operation moves you one back. The currPos property indicates the current position in a list.
  • Below is the List class implementation

https://gist.github.com/tamg/26bb38ddf26c013597860b3dbbc553c7

 

  • Methods of the List class

https://gist.github.com/tamg/637114105b8bc17e5be172b36170b606

 

  • Creating a List class instance and traversing through it

https://gist.github.com/tamg/a3f9e601ab16ee79536de7046b9ac403

 

Next up: Linked Lists!