18

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 a concrete explanation of why a linked list should be used rather than an array. I'm not very experienced with programming, so I haven't got much (if any) real-world experience.

Improve this question
2
  • 3
    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
    Commented Jan 5, 2012 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
    Commented Jan 5, 2012 at 14:43

4 Answers 4

Reset to default
36

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.

Improve this answer
11
  • 4
    According to Bjarne Stroustrup, LLs may not be as quick and easy for copying the whole list as you think.
    – Dennis
    Commented May 21, 2014 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
    Commented May 22, 2014 at 1:38
  • 2
    @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
    Commented May 22, 2014 at 14:23
  • 1
    @Ray: A linked list can outperform a tree structure if you expect there to be on the order of 4 elements and comparisons are relatively cheap. I do not know exactly where the cut-off is where this is not the case. Also, a tree structure requires that your data can be sorted, whereas a list structure allows you to maintain insertion order (or any arbitrary order).
    – David Stone
    Commented May 7, 2015 at 1:00
  • 2
    I don't think that this analogy is very accurate. As humans, we can (at least for such a short list) find an element in O(1). But if you want to do a random insert in a linked list, you'll have to traverse half the elements on average which costs you O(n) only to find the position where you want to insert. The actual insert then only costs O(1) but with an array, your cost is also “only” O(n). So the reason is not only due to move semantics but algorithmic. The constant factor hidden by the big-O is much larger for the liked list, however, due to the non-contiguous memory access.
    – 5gon12eder
    Commented Nov 11, 2015 at 17:57
18
  • 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.
Improve this answer
12

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.

Improve this answer
0
2

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

Improve this answer
0