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

Question

I understand the definition of a Linked List, but how can it be represented and related to a common concept or item?

For example, 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.

Answer 1

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.

Answer 2

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).

Answer 3

I like to think of a circular linked list like a pearl necklace, with each pearl containing a bit of data. You just follow the string to the next pearl of data, and eventually you end up at the beginning again.

Answer 4

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.

For example:

• 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.

Answer 5

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.

Answer 6

In the .NET BCL, the class System.Exception has a property called InnerException, which points to another exception or else is null. This forms a linked list.

In System.Type, the BaseType property points to another type in the same way.

Answer 7

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.

Answer 8

Inside the make program, you will often find that the dependency lists for a particular file that needs to be built are defined as linked lists of pointers to other files which also need to be built and in turn have dependencies in linked lists.

Answer 9

Giving travel directions: With each step in the directions being a node, and the travel instruction between each node as your link.

Example:

Node 1: Start at Home

Link: Walk 3 blocks South to Bob's House

Node 2: Bob's house

Link: Walk 2 blocks North to Alice's House.

Node 3: Alice's house

If you want to get one place to another you have to follow the links(instructions) from each intermediate place(node), you can't just skip from home to Alice's.

Answer 10

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 ;) )

Answer 11

Look at Linked List as a data structure. It's mechanism to represent self-aggregation in OOD. And you may think of it as real world object (for some people it is reality)

Answer 12

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.

Answer 13

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.

Answer 14

My first reaction to this question was "Look around! This stuff is everywhere!" But after thinking about it for a bit, I couldn't think of any example that isn't contrived.

The concept of a linked list is a compound concept, a two-fer. You have the notion of a list, which is no problem. A grocery list, for example. Then you get to the link part. One grocery item doesn't know about the next grocery item, so the model breaks down.

I think that the reason you are having trouble with finding a real world eample is that the link part is a programming artifact, an implementation detail. There are many ways to implement lists programatically and one good way is to have each list item know about its neighbors. Another way is to have a List object that keeps track of the items and their order. This is how most lists work in real life. In the example above, the List object for the grocery list would be the paper (or whatever) it's written on.

Maybe it's more useful to think about lists in general and view linked lists as just a specific implementation of a list.

Answer 15

Look at a linked list :

[A]=> [B]=> [C]=> [D]=>

It's a ... Train ! Each railroad car contain something and is attached to another railroad car (or nothing for the last one). You can only add a railroad car at the end and if you want to get rid of one you must attach the previous one with the next one.

Answer 16

A telephone chain is implemented directly as a linked list. Here's how it works:

1. A group organizer collects the phone numbers of all members.

2. The organizer assigns each member the number of one other member to call. (Sometimes they will assign their own number so that they know the message got through, but this is optional.)

3. When a message needs to be sent, the organizer calls the head of the list and delivers the message.

4. The head calls the number they were assigned and delivers the message.

5. Step 4 is repeated until everyone has heard the message.

Obviously care must be taken to set up the list in step 2 so that everyone is linked. Also, the list is usually public so that if someone gets an answering machine or busy tone, they can call the next number down and keep the chain moving.

Answer 17

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. :-)

Answer 18

A linked list is very similar to a stack of papers, each with one item on it. (As opposed to arrays, which are like pegboards.) It's generally used to solve a problem with these characteristics:

• There are an unknown or changeable number of items
• The items are in an order, like a list
• Items might be rearranged, added in mid-list, deleted in mid-list, etc.

Rearranging a plain array is a pain, adding an element somewhere in the middle while making sure the array has enough memory etc. is a pain. With linked list these operations are simple. Say you wanted to move item #10 to be between item #2 and item #3. With papers, you could just pick it up and move it. With an array, you would have to move items 3 through 9 over a slot, then put it in. With a linked list, you do this: Tell 9 that the one after it is 11, tell 2 the one after it is 10, tell 10 the one after it is 3.

I am using several of them right now, because of how easy it is to add items, and to programmatically say "do this action to every item in the list". One of them is a list of entries, like in a spreadsheet. The other, I make by going through that first list and adding a reference to every item that has a particular value, so that I can do batch operations on them. Being able to pluck items from the middle, or add them to the middle, and not having to worry about array length. Those are the main advantages in my experience.

Answer 19

Your DNA molecules are double-linked lists.

Answer 20

In operating systems ... one may use a linked list to keep track of what processes are running and what processes are sleeping ... a process that is running and wants to sleep ... gets removed from the LinkedList that keeps track of running processes and once the sleep time is over adds it back to the active process LinkedList

Maybe newer OS are using some funky data structures ... linked lists can be used there

Answer 21

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...

Answer 22

A chain:

Especially the roller chain:

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

Answer 23

Check out the examples at http://www.leanrcs.net