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

Question

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

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.

-Adam

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.

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.

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.

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.