Linear Data Structures

lineardatastructures.md

Linear Data Structures

Understanding different data structures and when to use them essential as a computer programmer. While many data structures are often hidden away behind layers of abstraction everything we do is built upon these patterns. This knowledge will not only eventually allow you to understand the software layers underneath the abstraction but also help you understand the hardware layer. In addition, these structures introduce a whole new toolset to help you solve problems on a day to day basis. If you study the internals of frameworks like Express and Angular you will find these patterns are relevant and powerful.

A linear data structure is a structure wherein all data elements are adjacent to each other. An array is an example of a linear data structure.

Stack

A stack is one of the most foundational yet simplest data structures. A stack is a linear data structure which is used to store data, it uses LIFO ordering, that is the last item into the stack is the first item out.

Imagine a stack of plates: every time you insert a plate into the stack of dishes you put it on the top. Every time you take a plate off the stack of dishes you take it off the top.

Likewise, every time you push data on to a stack, it is put on the top. Every time you pop data off the stack, it is taken off the top.

Traditionally, a stack has the following methods:

pop() // remove and return the top item from the stack
push(value) // add an item to the top of the stack
peek() // return the top item of the stack
isEmpty() // returns true if the stack is empty

Here is a simple example of a stack:

var dishes = new Stack();

dishes.push('dirty dish');
console.log(dishes.peek()); // prints dirty dish

dishes.push('clean dish');
var dish = dishes.pop();
console.log(dish); // prints clean dish

console.log(dishes.peek()); // prints dirty dish
dishes.pop();
dishes.isEmpty(); // true

• You Do: Build a stack! Use the example above to test it. Here is a shell program to get you started:

// Stack constructor
// properties:
//  values: some way of storing data.
var Stack = function(){

};

// pop
// description:
//  removes and returns the value at the top of the stack.
// returns:
//  the removed value.
Stack.prototype.pop = function(){

};

// push
// parameters:
//  value: the data to add to the stack.
// description:
//  adds the value to the top of the stack.
Stack.prototype.push = function(value){

};

// peek
// description:
//  returns the value at the top of the stack
Stack.prototype.peek = function(){

};

// isEmpty
// description:
//  returns true if the stack has no data in it
Stack.prototype.isEmpty = function(){

};

Why is a stack useful? A stack offers constant time adds and removes, making it very efficient for solving certain problems in a performant manner. In addition, it is a great companion to recursive logic, because it allows one to push data onto the stack while recursing, and pop the data off the stack while backtracking. CPU registers are stacks, so essentially every program you've ever used is built on top of them.

• Bonus Problems:

  • Towers of Hanoi is a puzzle in which requires the player to utilize 3 stacks of disks. Use the stack you implemented and the linked Wikipedia entry to write a program that solves Towers of Hanoi using 8 discs and 3 stacks. Note: This is a problem that could come up in an interview. In addition, it is a great opportunity to practice recursion as well.

• You Now Know:

  • Stacks are LIFO.
  • Stacks offer constant time adds and removes.
  • Stacks are useful with recursion.

• Further Reading: Stacks & Queues

• Solution: Stack Solution

Queue

A queue is a linear data structure. It is much like a stack but instead it is FIFO, the first item put in the stack is the first item out.

Take for example a queue or line of people waiting to go on a ride at an amusement park. The order people stand in line, is the order they get to go on the ride. The first person to stand in line is the first person on the ride.

Likewise, the order in which you add items to the queue is the order in which they are removed from the queue.

Traditionally, a queue has the following methods:

add() //adds an item to the back of the queue
remove() //removes and returns the item at the front of the queue
peek() //returns the item at the front of the queue
isEmpty() //returns true if the queue is empty

Here is a simple example of a queue:

var myQueue = new Queue();

myQueue.add('Roger');
console.log(myQueue.peek());//prints 'Roger'

myQueue.add('Logan');
console.log(myQueue.peek());//prints 'Roger'

var person = myQueue.remove();
console.log(person);//prints 'Roger'

console.log(myQueue.peek());// prints 'Logan'

myQueue.add('Jordan');
console.log(myQueue.peek());// prints 'Logan'

myQueue.remove();
console.log(myQueue.peek());// prints 'Jordan'

myQueue.isEmpty(); //false

• You Do: Implement your own queue here.

Why is a queue useful? Like a stack, a queue also offers constant time adds and removes. Queues are powerful while doing a breadth-first-search or implementing a cache. Certain types of Linked Lists are just fancy queues.

• Bonus Problems:

  • Priority Queues are a fun yet challenging problem to solve and also a somewhat popular interview question.

• You Now Know:

  • Queues are FIFO.
  • Queues offer constant time adds and removes.
  • Queues are useful for BFS and caches.

• Further Reading: Stacks & Queues

• Solution: Queue Solution

Singly-Linked List

Linked Lists are a linear data structure in which data is stored in a chain of nodes. A node is just an object that holds data and certain properties.

The first node in a list is known as the head and the last node in a list is known as the tail. The node currently examined is known as current or cur. Each node holds a value, or piece of data. Each node holds a reference to the next node in the list.

What the hell does that mean?

• We Do: Everyone in the class is given value and a next.
  • The head node becomes cur. cur states their value and their next.
  • The next becomes the cur. cur states their value and their next.
  • etc...
  • We remove the 3rd element by updated the 2nd elements next to the 4th element.

Example:

var classList = new LinkedList();
classList.append('Luke');
classList.append('David');
classList.append('Jared');
classList.append('Ian');
classList.append('Saundie');
classList.append('Matt');
classList.append('Micah');
classList.get(3); // Ian
classList.remove(3);
classList.get(3); // Saundie

• You Do: Implement your own linked-list and node.

// LinkedList constructor
// properties:
//  head: the first node in the list.
//  tail (optional): the last node in the list.
//  length (optional): the length of the list.
var LinkedList = function(){

};

// append
// description:
//  Creates a node with the passed in value and appends the node to the end of the LinkedList.
// parameters:
//  value: some data to be held by the appended node.
LinkedList.prototype.append = function(value){

};

// remove
// description:
//  Using 0 based indexing, remove the nth element from the LinkedList.
// parameters:
//  n: an integer
// notes:
//  update n's previous node.next to point to n's next node.
LinkedList.prototype.remove = function(n){

};

// get
// description
//  Using 0 based indexing, return the nth element from the LinkedList.
// parameters:
//  n: an integer
LinkedList.prototype.get = function(n){

};

// Node constructor:
// parameters:
//  _next: a Node, undefined or null.
//  _value: data
// properties:
//  next: a reference to the next node in a list, null if no nodes remaining.
//  value: data held by the node.
var Node = function(_value, _next){

};

Why is a linked list useful? Just like stacks and queues, a linked list also offers constant time adds and removes. Linked lists are useful in statically typed languages for storing lists of items which size and length are unknown. They are also useful for creating immutable data structures in functional and multithreaded languages. Recursion plays well with linked lists, since you can easily recursively iterate through all the nodes.

• Bonus Problems:

  • Tail. Add a tail to optimize appending to the end of the list.
  • Length. Add a length property to the LinkedList and use it for to check if n is within bounds on get and remove.
  • InsertBefore. Write a function to add a new node at before the nth element.
  • InsertAfter. Write a function to add a new node at after the nth element.
  • Reverse. Write a function to reverse the order of a linked list.
  • toArray. Write a function that returns an array from the linkedlist.
  • Palindrome. Implement a function to check if a linked-list is a palindrome.
  • Functional (Immutable) Linked List

• You Now Know:

  • Linked Lists offer constant time adds and removes.
  • Linked lists are great for dynamic length lists and memory allocation

• Further Reading: Linked Lists

Doubly-Linked List

A doubly linked list is very similar to a singly linked list. Instead of a node just having a next, a node also has a prev - which is a reference to the previous node in a list. This allows us to do certain things more efficiently, previously if we wanted to access the nth and n - 1th node we would have to traverse the list twice. Now we only need to do it once.

• You Do: Implement a doubly linked-list.

  • Tip: Remember in your remove to not only update the previous nodes next but also update the next nodes previous.

• Bonus Problems:

  • Implement a Queue using your doubly linked list.
  • Implement a Stack using your doubly linked list.
  • Circular Linked-List. Extend your linked list to have tail.next point to head, and head.prev point to tail.

• You Now Know:

  • Doubly Linked Lists are a specific type of linked lists that allows for us to do more complicated operations with less traversal.

• Further Reading: Linked Lists