Coding Interview Guide to Understanding Linked Lists

0
933

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.

understanding linked lists

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

Creating the Linked List

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.

Creating the Linked List

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.

Linked Lists vs Arrays

This may seem a bit pointless. The first question I had when I learned about linked lists was: “Why wouldn’t I just use an array?”. And that’s a fair question. The main benefit to using a linked list is that it allows for efficient shuffling of values. Because each element in a linked list has a pointer, it’s relatively simple to change the pointer value so an element can be connected to another item.

Some languages also require you to declare the size of an array when it’s created. For languages with that requirements linked lists, that allow for dynamic sizing, can be especially helpful.

LEAVE A REPLY

Please enter your comment!
Please enter your name here