# Coding Interview Guide to Understanding Linked Lists

0
817

When it comes to coding interviews the topic of understanding linked lists is a common question. However if you’ve come from a scripting language background, such as Python or Ruby you may have little to no experience working with them.

Typically in languages like Ruby you’ll spend the majority of your time working with the Array or Hash data structures. However in compiled languages, such as Scala you will work extensively with variations of linked lists. Therefore they are important to know what they are and how they can be used.

## Understanding Linked Lists: A Real World Example

As I’ve done with most of the algorithm guides I’m going to start off with a real world example of linked lists. Like other data structures, linked lists represent a collection of objects.

My favorite example of linked lists is a train. A train is made up of a collection of railroad cars. And the key to a train working properly is that each car is connected to the car in front of it. This means that the cars are not only carrying goods or people. They are also holding a connection to another car.

## Understanding Linked Lists: Practical Example

Now that you have a high level view of what linked lists are, let’s walk through how they can be used in a program.

While this particular data structure is utilized extensively, my favorite example is when it comes to building a mapping application.

If you want to build an application that stores a user route your data structure choice will have a few requirements:

1. It needs to store mapping coordinates.
2. Each coordinate needs to be point to the next next coordinate.

For example, if you are traveling from your house to a coffee shop downtown, your data structure needs to not only contain the route coordinates, but every one of the coordinates needs to know which set of coordinates to go to next. Without this `pointer` the mapping application wouldn’t work.

## Mapping Application

So let’s build a simple mapping data structure in Scala.

We’ll start with creating points on the map (I’m using shortened coordinates so they are easier to read).

`scala> val point_a = 5.5 :: -8.5 :: Nil`

`scala> val point_b = 6.8 :: -9.2 :: Nil`

`scala> val point_c = 7.2 :: -9.4 :: Nil`

This isn’t a guide specifically on the Scala programming language. So don’t let the syntax scare you off. Each of these commands are simply creating a list that store a set of map coordinates. Once we have these created we can create another list that will hold our coordinates. We’ll call it `route`:

`scala> val route = point_a :: point_b :: point_c :: Nil`

And that’s it! We have a linked list that stores our coordinates. By utilizing the `List` data structure in Scala it gives us some nice built in behavior. For example each of our coordinates will automatically know which coordinate they’re connected to.

To test this out let’s iterate over the route to see if it prints each element out in order.

`scala> route.foreach { println }`

The output of this command will be:

`List(5.5, -8.5)`

`List(6.8, -9.2)`

`List(7.2, -9.4)`

As you can see our route is working properly and is in order.