Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

A linked list can be used when you want cheap insertion and deletion of elements and when it doesn't matter that the elements aren't next to each other in memory.

This is very abstract and I would like to see some concrete examples of when a linked list is used rather than an array. I'm not very experienced with programming, so I haven't got much (if any) real-world experience.

share|improve this question
2  
Honestly, I don't think examples will mean that much to you until you have some experience of writing something, and then seeing the effect that changing data structures has on your code. Either try writing something you're interested in, and figure out what data structures and containers are the best fit, or look at some existing code and think about why each container was selected, and what effect changing it would have. –  Useless Jan 5 '12 at 12:39
    
I just don't think it's possible usefully to communicate the trade-offs and side-effects of data structure selection to the (inexperienced) OP without a much longer-form worked example than is reasonable here. The examples given as answers are fine, and do answer the question as asked, but not (what I read as) an implied request for actual understanding. –  Useless Jan 5 '12 at 14:43
    
Once you have a list, you can have LISP ;) –  Job Jan 5 '12 at 16:10
    
@Job - tempted to flag that comment :-) –  Ross Patterson Jan 7 '12 at 1:34

6 Answers 6

up vote 26 down vote accepted

Here is something part way between an example and an analogy. You have some errands to do, so you grab a piece of paper and write:

  • bank
  • groceries
  • drop off drycleaning

Then you remember that you also need to buy stamps. Because of the geography of your town, you need to do that after the bank. You could copy your whole list onto a new piece of paper:

  • bank
  • stamps
  • groceries
  • drop off drycleaning

or you could scribble on the one you had:

  • bank ....... STAMPS
  • groceries
  • drop off drycleaning

As you thought of other errands, you might write them at the bottom of the list, but with arrows reminding yourself what order to do them in. This is a linked list. It's quicker and easier than copying the whole list around every time you add something.

Then your cell phone rings while you're at the bank "hey, I got the stamps, don't pick up any more". You just cross STAMPS off the list, you don't rewrite a whole new one without STAMPS in it.

Now you could actually implement an errands list in code (maybe an app that puts your errands in order based on your geography) and there's a reasonable chance you would actually use a linked list for that in code. You want to add and remove lots of items, order matters, but you don't want to recopy the whole list after each insertion or deletion.

share|improve this answer
    
nicely explained! thank you –  Rat-a-tat-a-tat Ratatouille Feb 24 at 6:24
    
According to Bjarne Stroustrup, LLs may not be as quick and easy for copying the whole list as you think. –  Dennis May 21 at 23:54
    
@Dennis yes, I know, thanks to move semantics. However this is not true for all languages so the example stands. –  Kate Gregory May 22 at 1:38
1  
@KateGregory fair enough, but it's still good to point out that "basic" data structures are often better than the cool data structures we learn about in school (or elsewhere). I don't want new grads to use LLs everywhere because it's theoretically appropriate while possibly being a poor choice realistically. Using the right data structure is important, and sometimes people overcomplicate it. Slightly related is this talk by Jonathan Blow (creator of "Braid") on data structures. –  Dennis May 22 at 14:23

There are loads of examples out there. Google up "linked lists". Off the top of my head, dictionaries, hash tables, clusters of composite data (different data types), cases requiring dynamic allocation, etc.

share|improve this answer
    
And how can I forget... Trees, stacks, queues can all be implemented using linked lists... –  Arpith Jan 5 '12 at 12:15
    
They can be, but nobody does. Stacks and queues are usually implemented as arrays or deques under the hood. –  DeadMG Jan 5 '12 at 12:48
    
@DeadMG: and what is a deque exactly? –  Michael Borgwardt Jan 5 '12 at 12:51
    
@Michael: A double-ended queue. It is a fairly complex structure but offers very good complexity on many operations and also very good memory performance in terms of contiguity. –  DeadMG Jan 5 '12 at 12:56
3  
@DeadMG: "fairly complex" in this case meaning "doubly linked list with heand and tail pointer"? –  Michael Borgwardt Jan 5 '12 at 13:01

A linked list can be used to implement a message queue.

A message queue is a structure in which we store information about events for later processing. For example, when the user presses a key or moves the mouse, this is an event. An application might be busy at the moment when the event occurs, so it cannot be expected to process the event at the precise moment when it occurs. So, the event is placed in a message queue, (information about which key was pressed, or where the mouse has moved,) and when the application has some time to spare, it checks its message queue, fetches events from it, and process them. (This happens within a time frame of milliseconds, so it is not noticeable.)

From the usage scenario that I just described, it should be obvious that we never care to have random access to events stored in the message queue; we only care to be able to store messages in it, and retrieve them. So, it makes sense to use a linked list, which provides optimal insertion/removal time.

(Please do not butt in to point out that a message queue is likely, or more likely, or almost as likely, to be implemented using a circular array-list; that's a technical detail, and it has a limitation: you can only store a limited number of messages in it.)

share|improve this answer
2  
But a message queue is more likely to be implemented using a circular array-list! –  Yannis Rizos Jan 5 '12 at 13:42
    
@YannisRizos ... q(-.-)p ... –  Mike Nakis Jan 5 '12 at 13:48
  • Hashtables that use chaining to resolve hash collisions typically have one linked list per bucket for the elements in that bucket.
  • Simple memory allocators use a free list of unused memory regions, basically a linked list with the list pointer inside the free memory itself
  • In a FAT filesystem, the metadata of a large file is organized as a linked list of FAT entries.
share|improve this answer

The C-language "call stack" is implemented as a linked list in the x86 (and most other) binary APIs.

That is, C-language procedure calling follows a first-in, last-out discipline. The result of executing (possibly recursive) function calls gets referred to as a "call stack", or sometimes even just "the stack".

The CALL x86 instruction ends up implmenting a linked list using the "call stack". A CALL instruction pushes the contents of %EIP register, the address of the instruction after the CALL onto stack memory. The called-fuction prolog pushes the contents of the %EBP register, the lowest address of local variables in the calling functio, onto stack memory. Then the called function prolog sets %EBP to the current function's stack base.

That means that %EBP is a pointer to a memory location that holds the address of the calling function's %EBP value. That's nothing more than a linked list, implemented partially in hardware via CALL.

As far as what this is good for, it's how x86 CPUs implement function calls, particularly function calls where the function has it's own copy of arguments, and variables local to the function. Every function call pushes some information on the "call stack" that allows the CPU to pick up where it left off in the calling function, without interference from the called function or the calling function.

share|improve this answer
    
would you mind explaining more on what it does and what it's good for? "Link-only answers" are not quite welcome at Stack Exchange –  gnat Aug 31 '13 at 16:13
1  
@gnat - better, or does it need even more flesh on its bones? I feel that call stack as linked list isn't at all obvious, and deserves a mention. –  Bruce Ediger Sep 3 '13 at 3:07

Linked lists are useful for many things. The simplest case would be as a more powerful array. You can grow and shrink dynamically(super important), you don't need to allocate a contiguous block of memory(which you might not have), and you can store arbitrary items(instead of all the same types).

Everywhere that you could use an array, a linked list gives you more power. It just has more overhead, which is rarely an issue these days.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.