Data Structures and Algorithms: 0 to 60
Tags: computerscience, datastructures
Published: 2018-01-16 22:58:45

---
title: "Data Structures and Algorithms: 0 to 60"
published: true
tags: #computer-science, #datastructures
canonical_url: https://medium.com/acm-ucr/data-structures-and-algorithms-0-to-60-8413dc3b33b1
---

Whether for homework or interviews, Data Structures and Algorithms will be **foundational** to your early career. This article is to help you go from nothing to practical knowledge in this crucial area of Computer&nbsp;Science.

### Linked Lists

**A Linked List** is, as the name suggests, a list of items. Each item points to the next node in the list. Think of a linked list as a scavenger hunt.

You start with a clue (the head of the list), and each clue leads you to the next clue (the next pointer), until you’re at the end (the tail of the list). Can you think of a list implementation?

![](https://cdn-images-1.medium.com/max/730/1*gVHT0d3SFpvYjiwNj9FcJg.png)<figcaption>Every Node is the start of its own Linked List!</figcaption>

Some common reasons to use Linked Lists&nbsp;include:

- **Inserting elements in the middle of your data** : You can insert anywhere in your list as long as you know the Node before the insertion index. O(n) in a Vector, O(1) in a Linked&nbsp;List.
- **Quicker at expanding space for your data:** Because Linked Lists focus on this idea of using pointers, you don’t have to allocate contiguous blocks of memory for your data. This saves you O(n) time compared to a naive implementation of a&nbsp;Vector.

One major drawback of Linked Lists is that **you don’t have random access of an element** in the list by its index. For example: If you wanted to retrieve the 5th element in a list, you would have to iterate through the list until you ran into&nbsp;it.

### Stacks/Queues

A Stack and a Queue are pretty much the same data structure, the only difference being how they order their information. We can implement both with our Node struct from&nbsp;earlier!

**A Stack** operates last in, first out (LIFO). Think of a stack of cafeteria trays. The last tray you put on the stack will be the first one you pick up off the stack. A stack exposes three main functions: one to see the top, one to push to the top, and one to pop off the&nbsp;top.

**A Queue** operates first in, first out. Think of a queue of people waiting in line. If you were first in line, you would be helped first. Similarly, if you’re last in line, you will be helped last. A queue exposes the same functions as a stack, with the implementation of push being slightly different. (We want to push to the _end_ of a&nbsp;queue.)

![](https://cdn-images-1.medium.com/max/1024/1*2rSzCebGeD2Hk0bdCvEvMw.png)<figcaption>Basic Stack and Queue implementations based off our Node from earlier</figcaption>

Stacks and Queues are great for **maintaining order based on insertion time:** Use a Stack if you want to keep track of the most recent item. Use a Queue if you want to keep track of the oldest&nbsp;item.

Don’t use either if you care about anything other than the most recent or oldest&nbsp;items.

### Trees

**A Tree** is a data structure that is very suited to parent-child relationships in data. It can be implemented by a simple Node class as we defined above, with the exception of having multiple children pointers instead of one next&nbsp;pointer.

![](https://cdn-images-1.medium.com/max/730/1*0-7UYg7UUY79Zl6NGp300Q.png)<figcaption>A simple implementation of a tree. Note how every node is the “start” of it’s own subtree!</figcaption>

Trees require a different type of thinking than Vectors, Linked Lists, or even Stacks/Queues. They introduce a concept of **traversing a tree.** Because there is no set way to go from a parent to a child, you can choose between three main traversal methods:

#### Pre-Order Traversal

Use a Pre-Order Traversal if you want to calculate something on the parent before doing the same on the children.

Given our tree representation from&nbsp;above:

![](https://cdn-images-1.medium.com/max/590/1*682N3EB9dBWURYPvHlegBA.png)

#### In-Order Traversal

Use an In-Order Traversal if you want to calculate something on the left child, then the parent, and finally the right child. This is typically only used for binary trees, trees with only a max of two children per&nbsp;Node.

Given our tree representation from&nbsp;above:

![](https://cdn-images-1.medium.com/max/590/1*jxPrzsO0IpZxRhPB5sf20g.png)

#### Post-Order Traversal

Use a Post-Order Traversal if you want to calculate something on the children before doing the same on the&nbsp;parent.

Given our tree representation from&nbsp;above:

![](https://cdn-images-1.medium.com/max/590/1*WNe5ibhftL0ltNluyIAaWA.png)

### Maps

**A Map** is a way to represent data in terms of a key and a value. A proper implementation offers very quick insertion, lookup, and removal&nbsp;times.

The base of a good map implementation is it’s hash function. The purpose of this hash is&nbsp;to:

- Provide a hashed, or encoded, output given any valid&nbsp;input
- Always return the same output given the same&nbsp;input
- Minimize collisions, when two inputs returns the same&nbsp;output

![](https://cdn-images-1.medium.com/max/856/1*4y-A-qQZyD6EzcmIaOrT2Q.png)

Maps are incredibly powerful because of how quickly you can manipulate them. (O(1) for insertion, deletion, and lookup!) This speed lends itself very well for most interview questions, to the point of making them&nbsp;trivial.

Get to know Maps very&nbsp;well.

### Graphs

**A Graph** is a flexible data structure that can be used to represent data with complex relationships between Nodes. It is most similar to a Linked List, but every Node can have n number of pointers to other Nodes. A Graph is also not guaranteed to be free of cycles. (A cycle is when you can start and end at the same Node while traversing the&nbsp;graph.)

A Graph implementation is actually quite&nbsp;simple:

![](https://cdn-images-1.medium.com/max/730/1*7q-5bKXDNySNL2JpWvGPug.png)<figcaption>Notice how you can get to a OR c from b, but not necessarily the other way around!</figcaption>

We can model a lot of situations using graphs, such as: friendships between users, airplane routes, etc. Graphs can make any problem with complex relationships quite simple, and going from one Node to another is as simple as traversing through its neighbors. (Examples are mentioned in the Appendix: Path-finding and Dijkstra’s.)

### Appendix

These were some of the basic data structures that can be found in course curricula and interview questions. If you want to expand your knowledge further (and go from 60 to 120!), here are some advanced Data Structures and Algorithms:

- [Cycles in Linked&nbsp;Lists](https://blog.ostermiller.org/find-loop-singly-linked-list)
- [Using a Stack to evaluate mathematical expressions](http://faculty.cs.niu.edu/~hutchins/csci241/eval.htm)
- [Tries: a fancy tree that allows efficient path&nbsp;lookup](https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/)
- [Sets: when you only want to remember if you’ve seen an element before](https://en.wikipedia.org/wiki/Set_(abstract_data_type))(great replacement for map\<[anything], bool\>)
- Path-finding algorithms ([Kruskal’s](http://blog.hackerearth.com/kruskal-algorithm-minimum-spanning-tree-example) and [Prim’s](https://www.tutorialspoint.com/data_structures_algorithms/prims_spanning_tree_algorithm.htm)), for when you want to find a path between two nodes in a&nbsp;graph
- [Dijkstra’s Algorithm: find the path of least resistance between two&nbsp;nodes](https://dev.to/vaidehijoshi/finding-the-shortest-path-with-a-little-help-from-dijkstra-cmi)

### Further Resources

If you prefer books over blog posts, I highly recommend (in order of readability):

- [Algorithms to Live By: The Computer Science of Human Decisions](http://amzn.to/2D0owJL): A great read on how you can apply algorithms in your daily life. Not a very academic&nbsp;read.
- [Grokking Algorithms](http://amzn.to/2FvQ5fB): An incredible book for not only its simple explanations and relation to real world examples, but also PICTURES!
- [Introduction to Algorithms, 3rd Edition](http://amzn.to/2CYIPHh): A great reference book, used for Intermediate Data Structures and Algorithms at&nbsp;UCR.
- [Algorithms, 4th Edition](http://amzn.to/2Ds0NDo): Written by the legendary Robert Sedgewick, super informative. (Sedgewick has been teaching algorithms since the peak of Fortran!)

* * *