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

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

Answer 2

Best and straight forward example of doubly linked list is Train!

Here Each coach is connected to its previous and next coach(Except first and last)

In terms of programming consider coach body as data(value) node and connector as reference node.

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

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 5

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 6

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.