What is a practical, real world example of the Lin

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

Answer 1

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 2

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 3

consider 2 or more boxes which have 2 or more compartments. (in this example each box will have 2 compartments) the first compartment will contain some information. a number or a word. the second compartment will hold an arrow pointing to the next box and so on.

note that each box can contain multipale compartments which containt arrows(pointers) and information(data).

Answer 4

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

Answer 5

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.

Answer 6

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