In this video we explore common data structures in computer science. Before we get going, however, please understand that these things have been abstracted by languages and platforms and there are differences.
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?
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:
this.value = val;
this.next = null;
this.next = new Node(val);
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?
Popular Interview Questions
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.
Stacks and Queues are basically linked lists with abstractions built in that let you retrieve data in a particular way. A stack, for instance, lets you "stack" data on to it but will only let you pull data off of the top - just like a stack of plates. The methods that you associate with a stack are
pop: you "push" something onto the stack and "pop" off the top of the stack. This is also known as "Last In, First Out" or LIFO.
A queue has the same kind of data access rule, but instead of popping off the top you can only pull from the bottom of the queue, also known as "dequeuing". The two methods associated with a queue are
dequeue - just like waiting in line (or a queue) for a movie.
Trees, Binary Trees and Graphs
The bread and butter of technical interview questions. If you're going for a job at Google, Microsoft, Amazon or Facebook - you can be almost guaranteed to be asked a question that used a binary tree of some kind.
The simplest graph is known as a tree and you likely know exactly what that is because you're used to looking for files in your computer - which are stored in a tree data structure.
There are different kinds of trees with different rules to them. We'll explore the common ones including the plain old tree and the binary tree - one that you'll probably have to use in your interview.
I'm a big fan of testing, but I get lazy sometimes and it ends up costing me money, directly.
TDD is one of those things that people talk about, argue about, and think is interesting. I'm one of those people, so I asked Brad Wilson to clear it all up for me.