There aren't a lot of things in life that only let you move one direction. Sure, supermarkets might try to tell you which doors are meant to bring you in and take you out, but anyone who's ever played a game of chicken with the automatic door sensor knows that the door's going to let you go in either way…unless you're running too fast for it to catch.

Pro tip: never run faster than your opponent in a game of chicken unless you're ready to take some bruises.

If we ignore our history of concussions from the business end of a glass door, revolving doors also tend to go one way, except they always follow through on their promise. Think about it: there aren't even bars on the opposite side of the doors.

(Although, sometimes if you're desperate…)

Just like revolving doors, linked lists promise to go one way and follow through on their promise. At their core, linked lists are made up of elements that have a one-way door to the following element. If you follow each one-way door from the head (the beginning) to the tail (the end) like a string of pearls, you'll find a list of items hidden behind pointers through the memory.

Wait, what?

Every element of a linked list has two parts: the value (just like the value in an array) and a pointer to the next element. (BTW: A pointer is a variable that points to a place in memory.) That means your programming language has the freedom to put the elements in a linked list wherever it wants to in memory. Since it can put the elements anywhere, though, you can't just call them by index because…the computer has no idea what the index will be. Instead, you have to start at the head and move through each element until hitting the one you're looking for.

Whenever you have that value-pointer pair for an element, you have a node in a linked list. Because each node has that reference to the next node, the nodes can be scattered throughout computer memory without getting boxed into one big block like arrays do.

Say we have a linked list of Shmoop's favorite non-chocolate chocolate-flavored candies. It would look something like this.

What's up with that null as Chocolate Twizzlers reference? Did Twizzlers transgress against a sacred covenant between people and chocolate, forced to live out its days without anything to follow it? Probably, but there's another reason. On a mechanical level, the fourth element is the tail, meaning no other nodes come after it, making it point to nothing. (Null is the computer science version of nothing, FYI.)

This unholy list of chocolate-flavored non-chocolate candies can be called an abstract data type (or ADT) because its existence as a data type is entirely theoretical. The computer doesn't really come built-in with this kind of structure, but it's useful for programmers once you abstract to the level of a list.

It's also called a singly linked list, since each node has, at most, one link to another node.

You can also think of it like this:

 

Doubly Linked Lists

Using one-way doors sounds all well and good until you're in a hurry to reach the dentist in a big city and can't find any roads that go more than one direction. It gets old quick.

In the same way, traversing (going through) singly-linked lists can take way too much time if the element you're looking for is at the end of the list.

Enter: the doubly-linked list.

 

Now each element has two directions it can head, not just one. Sure, it takes up a little more memory, but (especially if you have a large, sorted list) it can save a boatload of time. Because each link can connect to the elements on either side, moving forward is as easy as moving backward.

Less time spent running code means more time spent eating faux-chocolate candies.

Circular Lists

If you've ever seen Scooby Doo (like on one of those four hour marathons they show on Saturday mornings on Cartoon Network), you might have seen a scene where all the characters run from one door to another in a hallway, except the doors they run to never seem to match the doors they run out of.

Circular lists are just like that…except without breaking the laws of physics. A circular list just makes the last node link back to the first node and vice versa, like…a circle. That way, if you need to cycle through a list multiple times at once or avoid NullPointer Exceptions, you can do it.

If you want to make a linked list act like this, it's surprisingly easy (but you'll have to provide your own montage music). Instead of having the pointer to the next node be null, have it loop back around to the head. If your list happens to be a doubly-linked list, you'll also need to connect the pointer to the previous element to the tail, too.

Our advice? If you're going to use a circular linked list, don't worry about making it doubly linked. The whole point of these data structures is to be able to access all the nodes in a list without starting at the beginning of said list. If you have things both doubly linked and circularly linked, you're repeating yourself in code. That sounds like a waste of code if we've ever heard one.