What is a practical, real world example of the Linked List?

I understand the definition of a Linked List, but how can it be represented and related to a common concept or item? For example, composition (EDIT: originally said 'inheritance') in OOP can be related to automobiles. All (most) automobiles in real life are the essentially same thing; an automobile has an Engine, you can start() it, you can make the car go(), stop() and so on. An automobile would typically have a maximum passenger capacity but it would differ between a Bus and a SportsCar, which are both automobiles. Is there some real life, intuitive example of the plain ole' singly Linked List like we have with inheritance? The typical textbook Linked List example shows a node with an integer and a pointer to the next, and it just doesn't seem very useful. Your input is appreciated.

You are confusing inheritance with composition. You said it yourself: an Automobile has_an Engine, not is_an Engine.

I am not confused. The engine would be declared in the Automobile class and inherited in the Bus or SportsCar class. Besides, this post is not about inheritance.

If you are not confused, your text is. You mention the textbook example of composition, not inheritance. You add an example of inheritance of attributes later. I understand what the question is about, though, and it's interesting. That's why I'm not downvoting it.

The example means that the Automobile interface has a getEngine() method and a start() method. This is an example of interface/inheritence.

Are you asking for an analogy, similar to the common (but flawed, I think) cars <->inheritance? Or a programming problem where you'd use a linked list?

35 Answers 35

A linked list is like a conga line. Everyone holds the hips of the person in front of them and their hips are held in turn by the person to their rear, excepting only those in the front and the back. The only way to add people to the line is to find the right spot and decouple that connection, then insert the new person or people.

I think their hands would be the pointer, and instead of pointing to the next person, they'd point to what we would consider the previous person, but that works really well. +1

I worry that that would encourage people to walk backwards, which is a bad scene if most of the conga participants are drunk (as is so often the case).

I'm assuming you want a more metaphorical explanation than the book definition, instead of examples of how you could use a linked list.

A linked list is kind of like a scavenger hunt. You have a clue, and that clue has a pointer to place to find the next clue. So you go to the next place and get another piece of data, and another pointer. To get something in the middle, or at the end, the only way to get to it is to follow this list from the beginning (or to cheat ;) )

Lutz: to cheat, you'd store an iterator from a previous operation, so you don't have to loop again the next time. :)

What is a practical, real world example of the Linked List?

The simplest and most straightforward is a train.

Train cars are linked in a specific order so that they may be loaded, unloaded, transferred, dropped off, and picked up in the most efficient manner possible.

For instance, the Jiffy Mix plant needs sugar, flour, cornmeal, etc. Just around the bend might be a paper processing plant that needs chlorine, sulfuric acid, and hydrogen.

Now, we can stop the train, unload each car of its contents, then let the train go on, but then everything else on the train has to sit while flour is sucked out of the caisson, then the sugar, etc.

Instead, the cars are loaded on the train in order so that a whole chunk of it can be detached, and the remainder of the train moves on.

The end of the train is easier to detach than a portion in the middle, and vastly easier than detaching a few cars in one spot, and a few cars in another spot.

If needed, however, you can insert and remove items at any point in the train.

Much like a linked list.

First thing to understand is that a linked list is conceptually the same as an array.

The only difference is in the efficiency of various operations. Most importantly:

• Insertion in the middle: O(1) for list, O(n) for array.
• Direct access to an element in the middle: O(n) for list, O(1) for array.

Thus any analogy that can be used for an array (all the engines of a plane, all the items on a shopping list. ) also applies to a linked list, but the efficiency consideration could make it appropriate to make another analogy:

An array would be boxes in a bookcase. When you remove the box from from the n-th row, all boxes from n+1 up need to be moved one shelf down (so you don't have a troublesome empty shelf).

A linked list, conversely, would be a necklace. When you find you don't like that blue jewel anymore, take it out of the sequence and tie the resulting two ends together. No need to loop through each pearl and displace it just so you can fix your necklace.

Waiting line at a teller/cashier, etc.

A series of orders which must be executed in order.

Any FIFO structure can be implemented as a linked list.

+1: Each person is the head of a list, with a list behind them. Except the last person, who is the head of an empty list.

Hmm. What about the pointer? If I'm standing in line, I really don't care about the person behind me and the cashier is not going to ask me where the next person is. I'm trying to think of a real-world model here.

The pointer doesn't really matter. The important part of a linked list is that it's really easy to add an element to the end, or the beginning, or anywhere in the list. Try doing that with a conventional array. Imagine someone in the line decides to cut, or someone steps out to go to the bathroom.

The pointer is implicit in real life. Imaging a line so long you don't see the teller. The only way you know to advance is when the person in front of you walks up.

. Both situations are very difficult to model using a normal array, because they involve copying large chunks of the array to a different part. But with a linked list, they're very simple.

Real life example for:

**1) Singly linked list **

1. Human brain of a child(In order to remember something eg . poem he has to link it , if you will ask him the last line he will have to read from the first line)
2. message delivery on network (message is broken into packets and each packet has a key of the next one so that at the receiver's end , it will be easy to club them)

2) Doubly linked list

1. DNA molecules
2. Browser cache which allows to use BACK button.
3. Train coaches are connected with the next and the previous ones.
4. Roller chain of bicycle(doubly circular linked list)

3) Circular linked list

1. Escalator
2. Time sharing problem used by the scheduler during the scheduling of the processes in the Operating system.
3. Multiple Player board game

I remember, many years ago, in one of my first college classes, wondering where I would ever , ever use a linked list. Today, I don't think there is a single project I work on where I haven't used one, and in many places. It's an incredibly fundamental data structure, and believe me, it's used heavily in the real world.

• A list of images that need to be burned to a CD in a medical imaging application
• A list of users of a website that need to be emailed some notification
• A list of objects in a 3D game that need to be rendered to the screen

It may seem slightly useless to you now, but a few years from now, ask yourself the same question, you'll find yourself surprised that you ever wondered where it would be used.

Edit: I noticed in one of your comments you asked about why the pointer matters. Someone rightly answered that the pointer doesn't really matter to a user of a linked list. A user just wants a list that contains a, well, list of things. How that list "contains" that list of things doesn't really matter to the user. The pointer is part of that "how". Imagine a line, drawn on the floor, that leads to a teller. People need to be standing on that line to be able to get to the teller. That line is a (and I admit, this is a bit of a stretch) analogy for the pointer a linked list uses. The first person, at the teller, on the line, is the head of the list. The person directly behind them on the line is the next in the list. And finally, the last person in the line, on the line, is the tail of the list.

of course, for those applications you could have easily used a queue, stack or even just a vector. The point of lists is the ability to easily insert into the middle of them.

Internally, when you don't have C++ and boost, queues and stacks (and maybe vectors) are specific cases of linked lists. It's nice to understand that, even if you never have to know this to use them.

Plenty of reasons. In the case of images that need to be burned to a CD, consider a UI where you're choosing multiple images. As you select / deselect images, it would be rather silly to resize an array, or copy over an old array to a new array with the necessary size - a list is a cleaner abstraction.

The way Blame moves around a bunch of software engineers working on different modules in a project.

First, the GUI guy gets blamed for the product not working. He checks his code and sees it's not his fault: the API is screwing up. The API guy checks his code: not his fault, it's a problem with the logger module. Logger module guy now blames database guy, who blames installer guy, who blames.

Your DNA molecules are double-linked lists.

A chain:

Especially the roller chain:

Each element of the chain is connected to its successor and predecessor.

If you think about it, a "Link" is simply a way of identifying a "Next", "Previous", "Child" or "Parent" relationship among data instances. So, among real world applications you'll find a broad variety of applications. Think of a simple List (e.g. Grocery List) for basic Linked Lists. But consider too the uses to which we can place Graphs (plotting distances between cities on a map, interactions among species in biology) or Trees (hierarchies in an organization or data in an index of a database for two very diverse examples).

He's not saying they're similar, just that there's a textbook example of inheritance, and asking if there are similar easy-to-get examples of the use of a linked list

Good point! I removed the line about OOP as it wasn't really needed. I scanned the question pretty quickly and thought that there was some confusion.

+1 Agreed. The real world equivalent is any list that you may write on paper. The "linked" part is merely the internal code mechanisms that a program would use to navigate the list. For our example, that would be the paper.

Well, the reason I voted down is because your Grocery List example doesn't explain why a linked list is superior to an array implementation.

A linked list can be used to implement a queue. The canonical real life example would be a line for a cashier.

A linked list can also be used to implement a stack. The cononical real ife example would be one of those plate dispensers at a buffet restaurant where pull the top plate off the top of the stack.

In the general case, linked lists are one of the most devilishly useful things you will encounter.

Real world examples:

• A bunch of people waiting in line for something or other - a special kind of LL called a "queue".
• The stack of dishes in your china cabinet - a special kind of LL called a "stack".
• The "take a number" lines (where the numbers have to start over again at "1" at some point) - a special kind of LL called a "circular queue".

Generally the metaphor I like to use for almost all linked data structures though is a deck of cards. Just about anything you can do with linked lists, you can use a deck of cards to visualise. This is particularly handy to show yourself what is going on in some of the more esoteric sorting algorithms.

My personal favorite: Bogosort = play 52 card pickup until your deck is sorted. :-)

Human brain can be a good example of singly linked list. In the initial stages of learning something by heart, the natural process is to link one item to next. It's a subconscious act. Let's take an example of mugging up 8 lines of Wordsworth's Solitary Reaper:

Behold her, single in the field, Yon solitary Highland Lass! Reaping and singing by herself; Stop here, or gently pass! Alone she cuts and binds the grain, And sings a melancholy strain; O listen! for the Vale profound Is overflowing with the sound. 

Our mind doesn't work well like an array that facilitates random access. If you ask the guy what's the last line, it will be harder for him to tell. He will have to go from line one to reach there. It's even harder if you ask him what's the fifth line.

At the same time if you give him a pointer, he will go forward. Ok start from Reaping and singing by herself; ?. It becomes easier now. It's even easier if you could give him two lines, Alone she cuts and binds the grain, And sings a melancholy strain; because he gets the flow better. Similarly, if you give him nothing at all, he will have to start from the start to get the lines. This is classic linked list.

There should be few anomalies in the analogy which might not fit well, but this somewhat explains how linked list works. Once you become somewhat proficient or know the poem inside-out, the linked list rolls (brain) into a hash table or array which facilitates O(1) lookup where you will be able to pick the lines from anywhere.