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

User · Answer

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   -

User · Answer

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

User · Answer

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

User · Answer

A chain     Especially the roller chain     Each element of the chain is connected to its successor and predecessor

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

Your DNA molecules are double-linked lists

User · Answer

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

User · Answer

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

User · Answer

well if a teacher took his students to a cartoon movie but she couldn t get the seats together  she ll ask students to remember the address seat number  of next student and so on    so that she wouldn t have to face the trouble while going back

User · Answer

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

User · Answer

A good example of a linked list is your text message  wherein a certain packet a message may be divided into several packets  Each packet holds a key which connects to the next key and to the n-th key to make the whole text message wherein it contains the key and the data

User · Answer

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

User · Answer

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

User · Answer

They do this in kids pre-school all the time  When they are outdoors on a road or something similar  each kid is asked to hold couple of other kids hand  Each kid knows whose hand he or she is supposed to hold  That s how they cross the road  I think this is a classic example of a doubly-linked list

User · Answer

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

User · Answer

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

User · Answer

Some example of single linked list     Undo button of any application like Microsoft Word  Paint  etc  A linked list of states  GPS Navigation  A linked list of map data  Travelling from origin to destination is example of traversing through all nodes  Rerouting by a GPS is an example of Add and Remove operations of map data     Some example of double linked list     Browser s Next and Previous Button  a linked list of URLs Microsoft Image Viewer s Next and Previous Button  a linked list of images  Undo and Redo button of Photoshop  a linked list of states

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

He did ask for a practical example  so I ll give it a shot   Lets say you are writing a firewall  in this firewall you have an IP whitelist and an IP blacklist   You know that your IP  your jobs IP  and some testing IP s need to be whitelisted  So  you add all of the IP s to the whitelist   Now  you also have a list of known IP s that should be blocked  So  you add those IPs to the blacklist   Why might use LinkedList for this    The operation is fast for adding removing an item from the list  You do not know how many IP s are going to blocked whitelisted  Thus  revealing one of the main advantages to a LinkedList  it s resizable

User · Answer

I don t think there is a good analogy that could highlight the two important characteristics as opposed to an array  1  efficient to insert after current item and 2  inefficient to find a specific item by index   There s nothing like that because normally people don t deal with very large number of items where you need to insert or locate specific items  For example  if you have a bag of sand  that would be hundreds of millions of grains  but you don t need to locate a specific grain  and the order of grains isn t important   When you deal with smaller collections  you can locate the needed item visually  or  in case of books in a library  you will have a dictinary-like organization   The closest analogy is having a blind man who goes through linked items like links of chain  beads on a necklace  train cars  etc  He may be looking for specific item or needing to insert an item after current one  It might be good to add that the blind man can go through them very quickly  e g  one million beads per second  but can only feel one link at a time  and cannot see the whole chain or part of it   Note that this analogy is similar to a double-linked list  I can t think of a similar analogy with singly linked one  because having a physical connection implies ability to backtrack

User · Answer

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

User · Answer

Real life example for     1  Singly linked list      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  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   DNA molecules Browser cache which allows to use BACK button  Train coaches are connected with the next and the previous ones  Roller chain of bicycle doubly circular linked list    3  Circular linked list   Escalator Time sharing problem used by the scheduler during the scheduling of the processes in the Operating system  Multiple Player board game

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

A telephone chain is implemented directly as a linked list   Here s how it works    A group organizer collects the phone numbers of all members  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   When a message needs to be sent  the organizer calls the head of the list and delivers the message  The head calls the number they were assigned and delivers the message  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

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

Examples related to collections

Examples related to linked-list

Examples related to car-analogy