When it comes to the topics of algorithms and data structures, the concept of linked lists is a common requirement. 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.

A Real World Example of Linked Lists

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.

Practical Code Example of Linked List

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:

• It needs to store mapping coordinates.
• 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. These commands are creating a list that store a set of map coordinates. Once we have these created we can build 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.