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

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 2

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 3

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 4

A chain:

Especially the roller chain:

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

Answer 5

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 6

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.