Jun 252011
 
linked-list

This question has been bugging me for the last few days. Why would anyone use a linked-list instead of arrays? I argue that linked lists have become irrelevant in the context of a modern computer system. I have asked around a few colleagues and I include their counter arguments and my rebuttal for your reference. Please point out if I am missing something.

Lists have several disadvantages that did not exist in traditional systems:

1. They reduce the benefit of out-of-order execution. Out-of-order execution gains a lot of benefit by parallelizing independent memory accesses. Accesses in  linked lists are dependent as the address of each node is only know after the current element has been loaded into the cache. This effectively eliminates the benefit of out-of-order executing when traversing the list.

2. They throw off hardware prefetching. Most processors today employ hardware prefetchers. Hardware prefetchers are good at prefetching regular data such as arrays but they are unable to prefetch linked data structures.

3. They reduce DRAM and TLB locality. Linked lists spread data elements all over the memory. Consecutive elements can be in different DRAM pages. Since modern DRAMs take 3x more cycles to fetch random memory locations, each memory access of a linked list is potentially more expensive (Explained in my post on What every programmer should know about the DRAM memory). For the same reason, a more dispersed memory footprint require more pages to be brought into the DRAM memory which increases the usage of physical memory. Lastly, if the list is dispersed across more pages, there are a larger number of TLB misses with a list.

4. They cannot leverage SIMD. In operations like lookup, multiple elements of an array can be compared to a value using a single SIMD instruction. Since elements in a linked list have to be fetched one at a time, it is unable to use the power-efficient SIMD model.

5. They are harder to send of GPUs.  Todays GPUs have a different memory address space than the CPU. Thus, when sending a data over to the GPU, all pointers have to converted from one memory space  to the other. Linked lists have lots of pointers which makes it considerable expensive to send then to the GPU. Note: This advantage will go away once GPUs share the virtual memory with the CPU.

When I gave the above reasons to my colleagues, they gave me some counter arguments about why linked lists are better. Below is their list and my rebuttal to each point.

1.  Resizable

Linked lists can be sized dynamically.
My argument: Array with amortized doubling has solved this problem.

2. Different element types

Linked lists are superior to arrays as they allow each node to be of a different type.
My argument: I agree except that this property is rarely exploited.

3. Cheaper insertions at the ends

It is cheaper to insert an element at the head or tail of a list.
My argument: Arrays can be used with a head and tail pointers and buffers at both ends for faster insertions.

4. Cheaper insertions in the middle

In ordered lists, inserts are often needed in the middle of the data structure. A link list insert is cheaper as on average it requires traversing only 1/2 of the list, finding the right spot, and inserting the node. Inserting in an array seems expensive because it requires traversing half of the array to find the insertion point and then shifting the other half of the array to make space for the incoming element.
My argument: The analysis is naive. Arrays are actually faster. The improved memory-level parallelism, locality, prefetching, and the ability to use SIMD far offsets the fact that arrays requires 2x the operations.

5. Pointers in the middle

We can have jump pointers to make list accesses faster.
My argument: This is called a hash table, not a list.

Do you have any other arguments that support the linked lists?

 

Do you still use linked lists?

View Results

Loading ... Loading ...

  55 Responses to “Quick Post: Should you ever use Linked-Lists?”

  1. I agree with the general tone of this post — programmers need to understand hardware better, and in a broad algorithmic sense, not just a narrow implementation one.

    Still, I disagree with some of your arguments. Overall, you seem to have narrowly restricted what constitutes a ‘linked list’ while allow ‘arrays’ to be rather broadly interpreted.

    Furthermore, you are performing your analysis with what seems to be a fairly narrow usage model; perhaps the data structure access/traversal cost is insignificant compared to the work actually done at each list entry. Hardware considerations are important, but the rule of optimizing bottlenecks is still essential!

    Comments on your individual points:

    1. The out-of-order execution argument is somewhat lacking; first of all, not all modern architectures use out-of-order execution; in particular, some of the lower-end ARM processors, Intel’s Atom processor, and the individual cores in the forthcoming Intel Many Integrated Core architecture.

    2. Where hardware prefetching fails, there are software prefetching instructions (and intrinsics) that can be used. This can even be necessary with an array (say, of pointers).

    3. The TLB/DRAM locality argument assumes that you have no indirection in your array (no arrays of pointers) and your that linked list cannot take advantage of pooled allocations. It depends greatly the usage model, but the cost of a TLB miss for a single element being added to a list vs. 100s of misses as you copy a gigantic array to insert into the middle is worth considering.

    4. Again, this depends on the usage. Most people probably don’t use SIMD for their vector traversal anyway. Notwithstanding, it should be possible to traverse multiple linked lists at once in SIMD given gather support (announced in the AVX2 instructions to appear in the upcoming Haswell microarchtecture)

    You argument against ‘cheaper insertions in the middle’ is missing a lot of details. Clearly inserting into the middle of a linked list (given the position) is O(1) while inserting into the middle of a vector is O(n). Searching is a different matter; at least separate the two notions in your analysis. Where does the ’2x the operations’ argument come from?

    The argument about ‘Pointers in the middle’ is nonsensical to me. What you’ve described _isn’t_ a hash table, it’s more like Pugh’s ‘Skip lists’.

    You’ve also omitted all of the interesting things you can do with lists, like have them be circular, or element be members of multiple lists. I agree that these are unusual methods of use, but they are still interesting and potentially useful.

    I think a more interesting angle is ‘how to do you implement linked lists (or linked list behavior) in a way that is architecture-friendly?’. Things like B-Trees can be viewed as sort of hybrid arrays/lists.

    Anyway, thanks for the interesting post; just thought I’d weigh in.

    Jason

    • Hi Jason,

      Thanks for an excellent comment This is exactly what I was hoping that someone will add some sense to my arguments as I was sure I was missing some details. I agree with most of what you have said. Individual responses follow:

      I do not think I have restricted the list as such. I just added amortized doubling and a head/tail pointer to the array which are both present in the linked list already (it does mallocs are has head/tail pointers). It just makes the comparison a bit fair to arrays. What do you think?

      I agree with your comment about the traversal being a minor cost in some. It may not matter at all in many cases. However, if an optimization comes for free, then I would argue that it should be done even if it does not always benefit and does not increase code’s complexity.

      Now the points:

      1. I agree that out-of-order is not in every core but the list does restrict opportunities to increase memory-level parallelism (MLP). Some in-order cores like Sun Rock employ techniques to get MLP and lists are still bad for those.

      2. In my experience, software prefetching a linked list is actually a lot harder than an array. Letting software prefetches get ahead of the actual stream requires a lot more ninja. Also, the null pointer at the end makes prefetching a bit tricky as well.

      By the way, I think we should not not compare an array of pointers to a linked list unless the link list is also a list of pointers, in which case they will be equally bad.

      3. Totally agreed with the pooled allocation argument. However, as I said, pointers of arrays should be kept out of the picture (as it is unfair to compare it with a list of data values). See my response below to the insertion being O(1).

      4. I agree SIMD is not used commonly but that trends is changing. Intel C compiler 10 is pretty good at auto vectorizing which makes it pretty automatic. I think gcc is getting better as well. ARM’s compiler is already good at it. Thus, I think arrays do win this argument. While it is possible to do multiple lists as SIMD, it requires more programmer effort. Also, I want to clarify that a gather still pretty expensive compared to a vector load. nVdia has the best implementation of gather out there and yet they discourage its use.

      Inserting in the middle of a list is O(1) in theory but only if you already know where to insert. Most likely I am missing something but I am thinking that it is almost always preceded by a a traversal of some sort. I think I need a correction here so please let me know what I am missing.

      Lastly, skip lists vs. Hash tables: Nah! it is more like a hash table and not a skip list. Perhaps we disagree on the definition of jump pointers. To me, it is a _direct_ shortcut pointer to the middle of a data structure in order to reduce traversal. Although short, a skip list still requires traversal to get to the part of the list where you think your data is. I see your point about a skip list and again an array can also have jump pointers and skip list like optimizations.

      I have indeed omitted the whacky lists. I was just thinking about a traditional list for the most part.

      I agree that we should think more about how a list should be build rather than whats wrong with it. Based on our discussion, I am thinking that a list of small array chunks can be pretty good. What say?

      Thanks for your excellent insights and correcting me. I enjoyed reading your comment and have now enjoyed writing this response. I really hope to hear from you again on this topic as I am sure I am again biased and need to be corrected:-).

      Aater

      • Don’t forget that allocating arrays with extra space (eg, doubling the size when you run out of space) can sometimes give you pooled memory for free – insertions into the array already have their memory allocated.

        The only time I’d normally (abnormal situations would be where the data is distributed across machines, for example, or where fine-grained low level performance isn’t as important as the time complexity) consider using a linked lists is when I want to avoid false sharing between nodes in multithreaded code and cache-line aligning each array element would be too memory wasteful. Of course, this will only work if there is other data that the linked list nodes can share cache lines with and the memory is carefully managed to allow this… and of course, this only really makes sense if accessing individual nodes is more common than traversing or manipulating the list itself.

        • Dan,

          Excellent point about pool memory and also about distributed machines. I do not write distributed code generally which is why it did not occur to me. Thanks for teaching me something new.

          Aater

          • No problem. This is something I’ve been thinking about recently, so I really enjoyed your post.

            I’ve been doing a bunch of multithreaded programming with Intel’s Threading Building Blocks and for that, linked list based structures are pretty inefficient, because processing linked lists generally requires sequential traversal, while array based structures can be more easily be split into chunks to process in parallel. (Sure, you can walk a linked list once and split it into chunks and then walk the chunks in parallel as they are processed, but that just creates more complexity). From a multithreaded point of view (which is my main interest in this discussion), linked lists and other inherently sequential data structures, as you know, are often a bad idea. I guess for the same reasons you gave regarding GPU’s.

            But I don’t think that linked lists are useless either – they do have their uses, its just that there are fewer of them than a lot of people think (and, sadly, are taught in computer science courses…)

          • “But I don’t think that linked lists are useless either – they do have their uses, its just that there are fewer of them than a lot of people think (and, sadly, are taught in computer science courses…)”

            I think you hit the nail here. It is less useful than it seems like. By the way, if you talking about the queue structures in TBB, I know that they are slow. I wrote my own for that reason. I can share some code if it will help.

          • “I wrote my own for that reason. I can share some code if it will help.”

            If you feel like making them the topic of a future blog posts, I would be very interested to hear about it! I would be interested in taking a look at code too :)

        • Nice discussion – just a quick reply;

          0) I think Aater mentioned how arrays-of-pointers aren’t ‘fair’ for comparison, but what happens when you have huge records to handle? With arrays that directly store them, you pay a lot to copy those big entries around, while lists can stay ‘where they are’. This is a big deal when inserting into the middle of an array. Furthermore, the persistence of pointers is pretty handy. If I give a pointer to someone, it’s going to remain valid for a linked list. If you have to move data around, as in an array, you’ll have to find some other way to make id that data.

          For that matter, it’s pretty handy to be able to have a pointer – just one – to be able to traverse a list. You can start right in the middle and traverse until you hit the sentinel/tail value. You need a sizes and a base pointer in addition to an index for arrays.

          1) Much talk has been made of exponential array allocation, which is also taught in CS courses. It’s a very useful technique, but it can also waste memory. There are some situations where you need to be very careful about space, and having 2x the space allocated than you need can be a problem – for example, on huge datasets on workstations, or even modest-sized problems on embedded devices.

          2) Linked lists can be modified (inserts, deletds, etc) by multiple threads asynchronously (with some pain, locks, etc), without much contention, while arrays generally cannot. Sometimes quite useful!

          3) Much of what we are taught in CS is based on theory of computation, and asympototic analysis. This blog, and our discussion, is very motivated by modern hardware considerations. I think that is a good thing, and that CS classes should do more to inform students about how hardware informs algorithm design/implementation, but I don’t think that should be added to the curriculum to /replace/ the theoretical model. That stuff is useful. Even with hardware considerations, there is a point at which the asymptotic complexity of some linked list operations outperform arrays.

          I’m really just playing devil’s advocate here — I honestly haven’t had to use linked lists for a while. I have done some stuff with trees, which can sometimes be interpreted as hybrid array/lists. For short to medium sequences of scalar data where performance is key, arrays are absolutely the way to go. I’m just calling you out on the ‘never’ generalization in this post :)

          • Jason,

            I agree with most of what you say. Specific answers below:

            1) True, I have always wondered if there is a better middle ground, something that isn’t exponential. Just for completion, I want to add two facts: (a) lists also waste space by saving points, (2) memory wastage for “unused” memory is can actually be zero overhead because it is in virtual memory which may never be pages if its never used. This is even more true for 64-bit addressing.

            2) Hmm.. I could argue that you can also optimize arrays but from a practical standpoint, I totally agree.

            3) I could not agree more. It shouldn’t replace the theory (my blog also has many analytic models:-) ) but it should make theory more realism aware. In fact, CS theory is actually tied to hardware IMO even today, but its tied to old hardware. The whole computes and memory concept is from hardware but when they were first generated, hardware used to be a lot simpler.

            Thanks for the great comment. I really enjoy learning new insights.

          • If doubling an array takes too much RAM or address space, you can also scale it by a smaller factor. You will get proportionally more allocations, but big O is unaffected. Factors > 2 work just as well. Doubling is still a good trade-off that works for most purposes, almost certainly better than wasting time bothering. But if it doesn’t work for you, you can still reap the benefits of exponential scaling with a different factor.

            And yeah, linked lists have their uses. Although I rarely use them, indeed.

  2. A correction in 5: this is called a “skip list” and they are useful sometimes.

  3. For hardware prefetching I think a counter example would be if you have a garbage collector that iterates through used memory. It will probably compact the linked list and put all the nodes sequentially, so the prefetchers would catch it just fine. It’s still an inefficient use of memory though, and if the data is primitives it will force a traversal for the garbage collector when it wouldn’t for the array (I guess if you care about garbage collector traversals you should have stopped caring about the performance of the data structure a long time ago).

    Disagree with the different data type argument. You can just have an array of pointers to handle different data types, so linked lists don’t make something possible that would otherwise have been impossible.

    One use I can think of for using linked lists is in a text editor. Each node handles a page or so of text. Adding in a character only requires playing with the current page. You don’t have to touch the next million characters. Using a skip list or some other data structure would be helpful but in general it’s a form of linked list. Another use I can think of is that it keeps you from using huge chunks of memory. That may or may not be acceptable, but from what I understand most file systems use linked lists because it’s harder to provide contiguous memory at all times. A linked list may also be considered for having better real-time properties than amortized doubling.

    Another use I was thinking was something like a game, in which you have to iterate over a list of missiles in flight anyway and update their state, but some missiles in the middle may explode and are removed from the list, but for all we know, it may be faster to mark for removal in the first iteration, and copy the remaining missiles in the next iteration, or when the number of active missiles to tracked missiles drops below a certain ratio garbage collect.

    Agree on the general point behind the post, for the most part just use an array and thank you to you, and both Dan and Jason for the valuable insights.

    I’d guess there would be more use cases for programs getting user input, because it really is useful over an array only when you know a position that you want to insert or remove from out of order, while preserving the order (if order does not matter then use an array and swap with the last element). In HPC too many things are just a stream in which you just iterate from front to back and definitely in those cases a linked list will be expensive.

  4. I think you’re coming at it from one very specific angle, e.g., thinking about GPUs. Those of us doing symbolic computation use linked lists all the time. I’ve got entire programs that basically do nothing but manipulate heterogeneous linked lists — not a rare case at all. This really is the killer feature: exploratory symbolic programming. I don’t care about CPU performance 99.9% of the time.

    A natural extension of heterogeneity is that I can also make it out of more lists — thus promoting an algorithm that works on a list to one that works on a tree, with almost no work. Promoting an array algorithm to work on trees, either by storing the tree in the array, or by writing a new class, seems like a lot more work to me.

    Insertion in the middle of an array isn’t 2x more operations. It’s O(N) times more operations. I don’t know where you got 2x.

    Another advantage: they have a simpler mutability model. I can declare that my lists are immutable (or use a language which enforces this), and when I want to prepend something and share the tail, I can do it safely, even with threads. I’m sure this is possible with arrays and there’s got to be some libraries out there to help with this, but I’m not familiar with any.

    • I agree with you regarding this article, and it very much reflects my usage of lists, at least when I’m programming in Scheme/Erlang/Lisp/Haskell/Prolog/etc… Heck, even when I program in python I do a ton of symbolic computation.

      I almost always use homogeneous lists though, and use vectors or tuples for heterogeneous values.

    • I’d also add that the performance of lists is not that bad if you know how to use them properly. For the stuff that I do, that I assume you do as well, the performance is actually better, for the reasons that you noted as well as reasons that I noted.

      • Guys, sorry I am late to the party. Thanks for reading and commenting.

        Alex, heterogeneity is certainly a good reason to use Lists. Agreed. I don’t use it that often, perhaps, because of the coding I typically do. Lists aren’t all bad and there are many cases where they improve performance as well, but there are downside one needs to be aware of.

        Tim, I have noticed that performance results for lists are usually good in cases where lists are used more like arrays, nodes allocated in consecutive locations and not too many insertions/deletion in the middle. Thus, prefetching can fetch the next nodes as a side effect and caches still provide spatial locality. Randomly allocated and connected nodes, where lists are considered good, are actually very poor performant. In my field, computer architecture and core design, people get entire PhDs on how make hardware that can make linked structures perform reasonable.

        Aater

  5. Anyway, your article was interesting and thought-provoking, although I don’t really agree with your point, overall.

    I use lists as my bread and butter data structure, along with tuples. (immutable arrays) I assume most of the programmers commenting are system level programmers, because they seem to not use them very much at all.

    Lists are an inductive data structure, trivial to make immutable implementations, with O(1) cons/insert at the front, O(1) first and O(1) “rest”/”tail”. Since they enable tail-sharing, it is trivial to fold over a list and produce a new one without throwing the original away, while sharing many contents with the original. Lists are not intended for random access, so I don’t think that is a fair criticism at all since no advocates of lists insist on them being used for such.

    Cons/append to any part of an array is extremely expensive, since you have to copy the entire array, except to the end of a vector or array”list”, (the worst terminology ever) and folding or recursing over an array persistently requires a lot of extra copying. Besides that, folding over an array is going to require a non O(n) append to front operation, which makes it prohibitively expensive.

    In contrast to what you say, the cost of resizing a linked list is much cheaper than an array, unless you have some special array. I think you’re comparing special array structures, which still have drawbacks relative to lists, while comparing them against literally regular mutable linked lists.

    Even appending to the end of an array isn’t necessarily free, since you might have to pay the amortized cost, which would make resizeable arrays completely unsuitable for real-time applications, which I assume many of the people on this blog would care about.

    Operations over lists are not very hard to parallelize. (and trees work even better for this purpose) For example, in the programming language Erlang, I wrote an email client, and to compute the summary view, I process a list of several thousand email data. Since I use higher order functions fold/map/filter/etc, I simply used a parallel list library, (eg. using plists:map vs lists:map) and it was able to compute much of the mail data using all of the cores on my machine, without making me change my algorithm at all.

    Finally, for random access. Arrays are obviously king here, but there are “Random Access Lists” librarires available (based on a datastructure designed by Chris Okasaki) for Erlang, Scheme and Emacs Lisp, which essentially treat the lists internally as a tree like structure, which has O(1) for cons, first/rest, and O(log(n)) for append, search, etc… So basically I have no idea why this library does not replace linked lists in every language, (except that every language it is used in would use pattern matching, and so the pattern matching syntax would have to be changed to pretend that this tree structure is a list) because unlike arrays, it has O(1) for the operations that lists are heralded for.

    From a high level perspective, it is extremely rare that I actually say “gee, I wish I could have the 4th element in that set, not the 5th”. If I want that, I probably really want a tree, hash table, or a dictionary. In the case of a collection, unless I’m searching for something, I want to apply a function or predicate to the elements of a collection, since they would most likely be the same type, and a linked list is just much better than an array for that. It really depends on what programming language you are programming in, though. In C, I use arrays for almost everything. Same thing for C++.

    In a java game project I’ve worked on, although I find the java linked list library absolutely atrocious, (because it has no way that I know of to get the rest of the list without destroying the head, iterators notwithstanding) the programmers I worked with used them a lot, and used them where they were appropriate.

    So, I’m not saying that lists are an end all data structure, but lists are definitely not a replacement for them, or at least they are not as good at the things lists do well. The “random access lists” actually provides a superset of the advantages of lists, however. I’m also a big fan of trees. (I wrote a red-black tree library earlier this year)

  6. Oops! Typo… When I said

    “but lists are definitely not a replacement for them, or at least they are not as good at the things lists do well.”

    I meant to say “but arrays are definitely not a replacement for them, or at least they are not as good at the things lists do well.”

  7. Also when I said “a non O(n) append to front operation”, I meant to say “an O(n) append to front operation”.

  8. One point I want to highlight here. Linux, which is one of most portable operating system uses linked lists extensively in its internal data structures.

    • Trs,

      Yup. Point well taken. Doesn’t mean its good. There a lot of people who think Linux leaves a lot of performance on the table. Lists are not evil, they are often used sub-optimally.

      Thanks.

  9. Hi

    For real-time systems, a linked list may be useful when you need to ensure that an insert will take a bounded length of time. If the time constraints on an insert are such that the time to create/copy the elements in the existing array fits within your time bounds, then an array would be acceptable.

    • Mike, thanks for the comment and sorry for my late reply.

      Very interesting point about real-time systems. I didn’t think about it. Actually, the RT systems are also impact by cache, DRAM, disk variabilities so the programmer has to be ultra conscious to begin with even with lists.

      Aater

  10. Write a simple benchmark of an array vs a linked list.

    Now insert 10 million items at the start of the array / list and see who wins.

    • James,

      Thanks for reading.

      The experiment you are suggesting is for a list of 10M element, with unknown size, without knowing the type of operations being performed. The answer will be a very specific result, not a generally applicable conclusion. For example, if you ever have to traverse your 10M element list, the array can be up to 20x faster. If you insert in the middle, the list will be faster but will make your traversals even slower as the memory access pattern will become more random. The idea is to raise awareness of the trade-offs.

      Aater

      • This time I agree, Array elements can be accessed faster than linked list. Lists are always need to be traversed from either very beginning or very end. :( but array can definitely be accessed from anywhere. Once my professor gave me such a program, where I had to find which element is present at the given position. obviously linked list was taking longer than array because I had to traverse it from beginning ( though it was doubly linked list ). but with array , it was simple using subscripts of it. also ,linked lists sometimes eat a lot of memory as they grow larger. array remains according to only element size.

  11. Haskell uses lists a lot, but the usual goal is to optimise them away so that you get a loop that is similar to the one an imperative programmer would have written.

    The standard “String” type is a linked list of characters, which is exactly as efficient as it sounds. To get around this libraries like “Text” and “Bytestring” have been written which have linked lists of chunks of text or bytes. This avoids the memory architecture problems you highlight.

  12. You seem to be ignorant of intrusive data structures.

    If I want to delete an object that is currently in multiple linked lists, I have O(1) deletion from each intrusive doubly-linked list. Without any dynamic allocation overhead and without searching anything.

    If I want to delete an object that is pointed by multiple arrays, I have a whole lot more of O(N) work to do.

    Inserting/replacing in the middle is O(1) with lists, not O(N). Your assumption that you need to traverse the list is false: you often have the element you want to delete from lists already, and you often have a position you want to insert that element at.

    I am suspicious that the author here used libraries like C++’s STL that do not expose the actual power of these data structures because they are not (so-called) intrusive. Thus, people who learn about these structures via use of the STL have a false idea of the properties of these basic computer scientific structures.

    • Eyal,

      Actually, I am well aware:-) I am a hardware architect, so I have programmer these structures in assembly, let alone C.

      Your point is well taken. Question is: How common is that case? In fact, many would argue that its bad practice to use intrusive data structures because of maintenance overheads, scaling, security etc but that isn’t my point at all. My goal in this article is to raise awareness that there is a lot more than the O notation in computing. O notation, as discussed in algorithms’ courses, is entirely misleading since O means nothing until N is big and it misses so many details like caching, memory, disk, and prefetching. Lists lead to random accesses, which throws memory prefetching, spacial locality, worst of all, disk locality out of the door. Combined, these effects can amount to one to two orders of magnitude slowdown. Ignoring these for no good reason is bad; ignoring these for a good reason like it can save me 3 million memory access is good. The decision is case specific, but the analysis needs to in the back of programmer’s head.

      Aater

      • In my C work, that case is *extremely* common. Almost every asynchronous operation we have (and we have plenty) is represented by objects with intrusive linked lists in them.
        I don’t believe that they introduce “maintenance overheads” or “scaling overheads”. See Linux’s list.h.

        If I have a pointer to an asynchronous request I am processing, removing and adding it to/from lists is going to touch only a few pointers. If I do the same with dynamic arrays I’m going to be messing a lot more cache lines.

        Also consider that growing arrays require a lot more dynamic memory management. With linked lists, you can often get away with no allocations at all. Once you use arrays, you necessarily have an external pointer store that besides for messing your cache lines, will also require dynamic growth/shrinkage, or a lot of waste (each possible container array will have to be as large as the worst case).

        These dynamic allocations are going to harm performance even more.

        In my particular line of work, and the kind of (soft) real time C code that I have to write, intrusive linked lists are more commonly useful than arrays, and using arrays where the lists are used would be detrimental to performance.

  13. Show me the numbers to back up these claims. Without performance testing of various scenarios you cannot say for certain.

    Jose

  14. My 2c:
    1) There’s a lot more embedded programming going on these days due to stuff like arduino. for most embedded apps, linked lists are still going to retain their historical use cases.

    2) Linked Lists can be a /simpler/ solution for some problems. Tuning at this level is premature optimization for like 90% of software which needs to a) work and b) be simple for maintenance. Most software out there is not performance critical, doesn’t need parallelisim, and should be tuned for clarity to ease maintenance. For this sofware, the data structure that makes for the simplest implementation is probably what should be used.

    • Hi Devon,

      Thank for reading and taking the time to comment. Both points are very well-taken. My responses are below:

      1. I think there are tons of cases where linked-lists make sense. My point is that there use is not harm-free and caution shall be used. On the side, I do not know if embedded specifically requires linked lists though. I must be missing something. Can you point me to some use cases?

      2. I am afraid I do not agree with just using the easiest tool for the job. I believe in using the right tool for the job. Using a different data structure is one such decision whose complexity can often be hidden behind an abstraction layer but making the right choice goes a long way. However, using the easiest tool at every step can lead to disasters as well. For example, if you look at Hadoop framework you may be shocked at how much performance they leave on the table. That software can be times faster but the programmers always used the greedy methodology of taking the easiest approach. I am not a purist and realize not all software needs to be fast, and most of my programming posts are for power coders, who write software that is used either in critical solutions or used enough times to make their performance important. I personally still use linked lists either in cases where they are the right tool or in cases where performance doesn’t matter.

      Thanks again,
      Aater

  15. Hi,
    Nice article!! You have kept a much valid points to prove your point. Even I agree with you, Most importantly Linked Lists will reduce DRAM and TLB locality

  16. Here is a counter argument for you for the second counter argument you get from your colleagues.

    It is possible to implement a singly linked list in an array.With it,you get the benefit of an array as stated in this post and the benefit of a linked list since each node can have its own size( the important part of a data type is the size it takes).

    An example implementation is here: https://raw.github.com/mhogomchungu/lxqt_wallet/master/backend/lxqtwallet.c

    Basically,the underlying data structure is an array of char and on top of it,there are nodes of variable lengths and what makes them linked list structures is the fact that the information on where the next node is is found in the current node.

  17. I’ve been browsing online more than 3 hours today, yet
    I never found any interesting article like yours.
    It is pretty worth enough for me. In my opinion, if all site
    owners and bloggers made good content as you did, the web will be much more useful than
    ever before.|
    I couldn’t resist commenting. Exceptionally well written!|
    I will immediately clutch your rss as I can’t to
    find your email subscription link or newsletter
    service. Do you have any? Kindly allow me know so that I could subscribe.

    Thanks.|
    It’s appropriate time to make some plans for the future annd
    it is time to be happy. I’ve read this post and if I could I wish to suggest you some interesting things or tips.
    Maybe you can write next articles referring to this article.
    I want to read more things about it!|
    It is perfect time to make a few plans for the longer term and it is time to be happy.
    I have read this submit and if I could I desire to recommend you
    few interesting issues or advice. Maybe you could write subsequent articles regarding
    this article. I want to learn more things about it!|
    I’ve bsen surfing on-line greater than three hours
    today, but I by no means discovered any fascinating article like yours.
    It’s beautiful worth sufficient for me. Personally, if all
    website owners and bloggers made good content material
    as you probably did, the web might be much more helpful than ever before.|
    Ahaa, its fastidious conversation about this post here at this blog, I have
    read all that, so now me also commenting here.|
    I am sure this article has touched all the internet people, its really really nice article on building up new weblog.|
    Wow, this post is fastidious, my sister is analyzing such things,
    so I am going to tell her.|
    Saved as a favorite, I like your site!|
    Way cool! Some extremely valid points! I appreciate you writing this article plus the rest of the website is very
    good.|
    Hi, I do believe this is an excellent website. I stumbledupon it ;) I’m
    goingto return yet again since I bookmarked it. Money
    and freedom is thhe beszt wway to change, may yoou be rich and continue to guide others.|
    Woah! I’m really digging the template/theme of this
    blog. It’s simple, yet effective. A loot of times it’s difficult to get that
    “perfect balance” between superb usability and appearance.
    I must say that you’ve done a superb job with this.
    Also, the blog loads extremely quick for me on Chrome.

    Excellent Blog!|
    These are in fact fantastic ideas in on the topic of blogging.
    You have touched some nice points here. Any way
    keep up wrinting.|
    I like what you gujys tend to be up too. Such clevsr work and reporting!

    Keep up the great works uys I’ve incorporated you guys to
    blogroll.|
    Hey! Someone in my Myspace group shared this website with us so I came to give it a look.
    I’m definitely loving the information. I’m bookmarking and will be
    tweeting this to my followers! Wonderful blog and outstanding design.|
    I love what you guys are up too. This kind of clever work and coverage!
    Keep up the awesome works guys I’ve inclkuded you
    guys too our blogroll.|
    Howdy would you mijd sharing which blog platform you’re working with?
    I’m planning to start my own blog soon butt I’m having a difficult
    time deciding between BlogEngine/Wordpress/B2evolution and Drupal.

    The reason I ask is because your design and style seems different then most blogs and I’m looking for
    something unique. P.S My apologies for getting off-topic but I had to ask!|
    Hi would you mind letting me know which web host you’re working
    with? I’ve loaded your blog iin 3 different browsers aand I must say
    this blog loads a lot quicker theen most. Can youu suggest a
    good web hosting provider at a reasonable price?
    Thanks a lot, I appreciate it!|
    Everyone loves it when folks come together andd share views.
    Great website, keep it up!|
    Thank you for the auspicious writeup. It iin fact
    was a amusement account it. Loook advanced to more added agreeable from you!
    By the way, how could we communicate?|
    Hey just wanted to give you a quic herads up. The words in your content seem to be running off the screen in Chrome.
    I’m not sure if this is a formatting issue or something to do
    with internet browser compatibility but I thought I’d post to
    let you know. The layout look great though! Hope you get the issue fixed soon.
    Thanks|
    This is a topic thwt is near to my heart… Thank you!
    Exactly where are your contact details though?|
    It’s very straightforward to find out any matter on net as compared to textbooks, as I found this article at this website.|
    Does your blog have a contact page? I’m having trouble locatin it but, I’d like to send you an email.
    I’ve got some creative ideas foor your blog you might
    be interested in hearing. Either way, great site and
    I look forward to seeing it improve over time.|
    Hello! I’ve been reading your web site for a while now and finally got
    the bravery to go ahead and give you a shout out
    from Porter Texas! Just wanted to say keep up the excellent work!|
    Greetings from California! I’m bored too death at work so I decided to check out your website onn
    my iphone during lunch break. I love the knowledge you present here
    and can’t wait to take a look when I get home. I’m shocked att how
    fast yur blog loaded on my phone .. I’m not even using
    WIFI, just 3G .. Anyways, wonderful site!|
    Its such as you read my thoughts! You seem to know so much approximately this, such
    as you wrote the book in it or something. I feel that you could do with some % to power the message home
    a bit, however other than that, this is magnificent blog.
    A great read. I’ll definitely be back.|
    I visited multiple sites however the audio quality for audio songs present
    at this web page is genuinely superb.|
    Hello, i reasd your blog occasionally and i own a similar onee and i was
    just curious if you gget a lot of soam remarks? If so how do you prevent it, anny plpugin or anything you can recommend?
    I get so much lately it’s driving me mad so any assistance is very much appreciated.|
    Greetings! Very useful advice within this post! It is the little changes that
    produce the most important changes. Many thanks for sharing!|
    I truly love your site.. Pleasant colors & theme. Did you develop this amazing site yourself?
    Please reply back as I’m hoping to create my very own
    website and woupd like to find out where you got this from or exactly
    what the theme is named. Appreciate it!|
    Howdy! This blog post couldn’t be written any better!

    Going through this post reminds me of my previous roommate!
    He continually kept preaching about this. I most certainly will forward this information
    to him. Pretty sure he will have a great read. Thanks for sharing!|
    Whoa! This blog looks exactly like my old one! It’s on a entirely different
    subject but it has pretty much the same page layout and design.
    Superb choice oof colors!|
    There is certainly a lot to know about this subject.
    I likke all off the points you have made.|
    You have made some really gokd points there. I looked on the net for
    additional information about the issue and found most individuals will go along with
    your views on this site.|
    Hello, I check your blog onn a regular basis. Your humoristic style is awesome, keep up
    the good work!|
    I just couldn’t depart your site prior to suggesting
    that I actually loved the standard info an individual supply on
    your guests? Is going to be again incessantly to check out new posts|
    I needed to thank you for this very good read!!
    I certainly enjoyed every little bit of it. I have you book-marked to check out new things you post…|
    What’s up, just wanted to say, I liked this article.
    It was helpful. Keep on posting!|
    I drop a leave a response each time I like a article on a site or if I have something to contribute to the discussion.
    It’s caused by the sincerness communicated
    in the article I browsed. And after this post Quick Post:
    Should you ever use Linked-Lists? | Future Chips.
    I was actually excited enough to leave a comment :-P I do have a couple of questions
    for you if it’s allright. Could it be simply me or does it look like like
    a few of these comments appear like they are left by brain dead people?
    :-P And, if you are posting at other sites, I would like
    to keep upp with eeverything fresh you have to post. Could you make a list thee complete urls of all your public pages like your twitter feed, Facebook page
    or linkedin profile?|
    Hello, I enjoy reading through your post. I wanted to write a little comment to support you.|
    I every ime spent myy half an hour to reqd this weblog’s articles everyday along with a cup
    of coffee.|
    I always emailed this blog post page to all my contacts, as if like to read it afterward my links will too.|
    My developer is trying to persuade me to move to .net from PHP.

    I have always disliked the idea because of the expenses.
    But he’s tryiong none the less. I’ve been using Movable-type on a variety of websites for about a year and am worried about switching to another platform.
    I have heard very good things about blogengine.net.
    Is there a way I can import all my wordpress
    content into it? Any help would be really appreciated!|
    Howdy! I could have sworn I’ve been to your blog before but after going through some of
    the posts I realized it’s new to me. Anyhow, I’m definitely happy I came across it and I’ll
    be bookmarking it and checking back frequently!|
    Great article! This is the kind of information that are meant to be shared across the web.
    Disgrace on Google for not positioning this submit
    higher! Come on over and consult with my web site . Thank you =)|
    Heya i am for the first time here. I found this board and I find
    It really useful & it helped me out a lot. I hope to give something back and aid others
    like you helped me.|
    Greetings, There’s no doubt thgat your web site could
    be having internet browser compatibility problems.
    Whenever I take a look at your blog in Safari, it looks fine but when opening in Internet Explorer,
    it has some overlapping issues. I simply wanted to provide you with a
    quick heads up! Aside from that, wonderful website!|
    Someone essentially help to make significantly articles I might
    state. That is the very first timke I frequented your website pagge and thus far?

    I surprised with the research you made to make this actual post amazing.
    Excellent job!|
    Heyya i am for the primary time here. I found
    this board and I to ind It truly useful & iit helped me
    out much. I hope to present onne thing back and help others such as you aided me.|
    Hi! I simply would like to offewr you a big thumbs up for your
    great info youu have got right here on this post.

    I will be coming back to your blog forr more soon.|
    I always used to study article in news papers but now
    as I am a user of internet so from now I am usung net for content, thanks to web.|
    Your way of tellling the whole thing inn this paragraph is actually nice, every one be capable of without difficulty bee aware of it,
    Thanks a lot.|
    Hello there, I found your site by way off Google at the same time
    as searching for a similar matter, your web site came up, it appears to be lke good.
    I’ve bookmarked it in my google bookmarks.
    Hi there, just became aware of your blog through Google,
    and located that it’s really informative. I’m going to be careful for brussels.
    I’ll be grateful in the event you continue this inn future.
    Numerous people will likely be benefioted from your
    writing. Cheers!|
    I’m curious to find out what blog platform you have been using?
    I’m experiencing some minor sefurity problems wigh my latewst site and
    I would like tto find something more safeguarded. Do you have any solutions?|
    I am really impressed with your writing skills as well as with the layout
    on your weblog. Is this a paid theme oor did you modify it yourself?

    Eithger way kep up the excellent quality writing, it is rrare to see a great blog like this
    one these days.|
    I am really inspired with your writing talents and also with the
    structure to your blog. Is that this a paid theme or didd yyou customize it yourself?

    Either way keep up the excellent quality writing,
    it is uncommon to look a great blog like this one nowadays..|
    Hi, Neat post. There is aan issue together with your site iin internet explorer, might check this?
    IE nonetheless is the market ledader and a huge component of other people will miss your
    great writing due to this problem.|
    I am not sure where you’re getting your information, but great topic.
    I needs to spend some time learning more or understanding
    more. Thanks for magnificent info I was looking for this info
    for my mission.|
    Hi, i think that i saw you visited my web site thus i came to “return the favor”.I am trying to find things to
    improve my web site!I suppose its ok to use a few of your ideas!!

    \

  18. [...] came across this article: Should you ever use Linked List. It cites that given the technological advances in available memory and RAM structures, using [...]

  19. While I agree with your article, there is one (and the only one I’ve found so far) important feature of a linked list which an array does not have and that is memory persistence. I can store something in a linked list and then have external pointers to it. If I try to do this with an array then as soon as the array gets resized, those pointers become invalidated.

    For this reason I find myself still using linked lists sometimes for things like memory allocators (e.g. maintain a linked list of memory pages).

  20. Hi there, just wanted to tell you, I liked this
    article. It was funny. Keep on posting!

    Review my web page … N

  21. Every weekend i used to go to see this site, for the
    reason that i wish for enjoyment, for the reason that this this web site conations really
    fastidious funny data too.

  22. Do you have a spam problem on this site; I also am
    a blogger, and I was wondering your situation; we have created some nice
    methods and we are looking to exchange strategies with others, be sure to
    shoot me an e-mail if interested.

    Also visit my blog; telecharger pdf creator

  23. Oh my goodness! Incredible article dude! Thanks, However I am encountering troubles with your
    RSS. I don’t know why I am unable to subscribe to it. Is there anybody having identical RSS issues?

    Anyone that knows the solution can you kindly respond? Thanks!!

    Feel free to visit my web page creative writing exercises

  24. Est-il possible de vous reprendre deux trois phrases pour mon site web ?

  25. Watch Maleficent Online Free Full Movie
    Watch Maleficent Online explores the untold story of Disney’s most iconic villain from the 1959 classic Sleeping Beauty and the elements of her betrayal that ultimately turned her pure heart to stone. Driven by revenge and a fierce desire to protect the moors over which she presides, Maleficent (Angelina Jolie) cruelly places an irrevocable curse upon the human king’s newborn infant Aurora. As the child grows, Aurora (Elle Fanning) is caught in the middle of the seething conflict between the forest kingdom she has grown to love and the human kingdom that holds her legacy. Maleficent realizes that Aurora may hold the key to peace in the land and is forced to take drastic actions that will change.

    So you can Watch Maleficent Online Viooz

  26. Ребят, так все-таки это действенный метод или нет?

    Взгляните на мою личную страничку …
    все о форекс

  27. naturally like your website but you have to take a look at the spelling on several
    of your posts. A number of them are rife with spelling issues and I find it very troublesome to inform
    the truth however I’ll surely come again again.

  28. Je terminerai de voir tout cela plus tard

  29. Good information. Lucky me I came across your blog by accident (stumbleupon).
    I have saved as a favorite for later!

 Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>