20

I am very puzzled about this. Everywhere there is written "linked lists are faster than arrays" but no one makes the effort to say WHY. Using plain logic I can't understand how a linked list can be faster. In an array all cells are next to each other so as long as you know the size of each cell it's easy to reach one cell instantly. For example if there is a list of 10 integers and I want to get the value in the fourth cell then I just go directly to the start of the array+24 bytes and read 8 bytes from there.

In the other hand when you have a linked list and you want to get the element in the fourth place then you have to start from the beginning or end of the list(depending on if it's a single or double list) and go from one node to the other until you find what you're looking for.

So how the heck can going step by step be faster than going directly to an element?

ckittel
  • 6,478
  • 3
  • 41
  • 71
Pithikos
  • 18,827
  • 15
  • 113
  • 136
  • 15
    It depends on what you're trying to accomplish. If you want to search or access a specific element, arrays are faster, but if you want to insert or delete an element, a linked list is faster. – Nathan Fellman Mar 26 '11 at 20:38
  • 3
    I would very much like to see a link to somewhere that makes this claim. – Joe Mar 26 '11 at 20:48
  • @x3ro As some answered, fast is relevant. So in some places it's written that arrays are faster than linked lists and in some places it is written that linked lists are faster than arrays. I googled and didn't find any results on that and that's the reason I posted the question here as I was puzzled. Now with my question topped anyone else who wonders about the same will get their mind straight. – Pithikos Mar 28 '11 at 17:12
  • @Pithikos: What about http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays ? – fresskoma Mar 28 '11 at 18:07
  • 1
    @x3ro as a beginner I prefer a more straighforward answer than reading the whole wikipedeia and not understanding anything. Not everyone is comfortable with format language afterall. – Pithikos Mar 31 '11 at 07:28
  • Linked lists are *...soooo sloooooooow...* at indexing/traversing, but they're insanely fast at insertion/deletion, compared to dynamic arrays. – Mateen Ulhaq Aug 05 '11 at 02:11

6 Answers6

22

This question title is misleading.

It asserts that linked lists are faster than arrays without limiting the scope well. There are a number of times when arrays can be significantly faster and there are a number of times when a linked list can be significantly faster: the particular case of linked lists "being faster" does not appear to be supported.

There are two things to consider:

  1. The theoretical bounds of linked-lists vs. arrays in a particular operation; and
  2. the real-world implementation and usage pattern including cache-locality and allocations.

As far as the access of an indexed element: The operation is O(1) in an array and as pointed out, is very fast (just an offset). The operation is O(k) in a linked list (where k is the index and may always be << n, depending) but if the linked list is already being traversed then this is O(1) per step which is "the same" as an array. If an array traversal (for(i=0;i<len;i++) is faster (or slower) depends upon particular implementation/language/run-time.

However, if there is a specific case where the array is not faster for either of the above operations (seek or traversal), it would be interesting to see to be dissected in more detail. (I am sure it is possible to find a language with a very degenerate implementation of arrays over lists cough Haskell cough)

Happy coding.

My simple usage summary: Arrays are good for indexed access and operations which involve swapping elements. The non-amortized re-size operation and extra slack (if required), however, may be rather costly. Linked lists amortize the re-sizing (and trade slack for a "pointer" per-cell) and can often excel at operations like "chopping out or inserting a bunch of elements". In the end they are different data-structures and should be treated as such.

10

Like most problems in programming, context is everything. You need to think about the expected access patterns of your data, and then design your storage system appropriately. If you insert something once, and then access it 1,000,000 times, then who cares what the insert cost is? On the other hand, if you insert/delete as often as you read, then those costs drive the decision.

Peter Rowell
  • 17,605
  • 2
  • 49
  • 65
6

Depends on which operation you are referring to. Adding or removing elements is a lot faster in a linked list than in an array.

Iterating sequentially over the list one by one is more or less the same speed in a linked list and an array.

Getting one specific element in the middle is a lot faster in an array.

And the array might waste space, because very often when expanding the array, more elements are allocated than needed at that point in time (think ArrayList in Java).

So you need to choose your data structure depending on what you want to do:

many insertions and iterating sequentially --> use a LinkedList

random access and ideally a predefined size --> use an array

  • In reference to iterating sequentially, it may be that a linked list will slightly edge out over arrays. Your assertion that iterating sequentially over the list is more or less the same speed is probably correct, but can be difficult to measure on modern computers. I believe that in the purest context, linked lists edge out arrays on iteration speed, as moving to the next node does not require calculating the address to the next memory offset, as is with arrays, since the linked list holds the address to the next node. – Scott Forbes Jan 16 '19 at 13:39
  • 1
    That being said, calculating where the next element is and accessing it is a simple addition and an access to memory that is likely already in the cache; for a linked list it requires pointer-chasing which is often slow. Computers usually have efficient addressing modes for doing array indexing, anyhow. – saagarjha Jul 26 '20 at 06:07
5

Linked lists are preferable over arrays when:

a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

c) you don't need random access to any elements

d) you want to be able to insert items in the middle of the list (such as a priority queue)

Arrays are preferable when:

a) you need indexed/random access to elements

b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.

Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

Reference: Lamar answer https://stackoverflow.com/a/393578/6249148

Ahmed Abdelkarim
  • 277
  • 2
  • 10
4

Because no memory is moved when insertion is made in the middle of the array. For the case you presented, its true - arrays are faster, you need arithmetic only to go from one element to another. Linked list require indirection and fragments memory. The key is to know what structure to use and when.

Iharob Al Asimi
  • 52,653
  • 6
  • 59
  • 97
cprogrammer
  • 5,503
  • 3
  • 36
  • 56
  • 2
    Worth noting that INSERTION is faster (as is deletion), but not indexed access, which was Pithikos' source of confusion. – Jollymorphic Mar 26 '11 at 20:39
  • So you mean in the case where there is a full array and you want to add a new element? Then sure you have to resize the whole array. But what if the array is empty? – Pithikos Mar 26 '11 at 20:43
  • for simple access nothing beats arrays. The question is "Why are linked lists faster than arrays?" and the answer address this question. In real-life application you are making many operations on array (consider sorting case), and this is the reason why are used more often than arrays; – cprogrammer Mar 26 '11 at 20:46
  • @Pithikos inserting one element in a single linked list -> just one alocation . inserting one element in a std:vector (array) **may** realloc memory and move all elements -> Time is not constant. May be smaller or bigger. – cprogrammer Mar 26 '11 at 20:50
0

LinkedList is Node-based meaning that data is randomly placed in memory and is linked together by nodes (objects that point to another, rather than being next to one another)

Array is a set of similar data objects stored in sequential memory locations

The advantage of a linked list is that data doesn’t have to be sequential in memory. When you add/remove an element, you are simply changing the pointer of a node to point to a different node, not actually moving elements around. If you don’t have to add elements towards the end of the list, then accessing data is faster, due to iterating over less elements. However there are variations to the LinkedList such as a DoublyLinkedList which point to previous and next nodes.

The advantage of an array is that yes you can access any element O(1) time if you know the index, but if you don’t know the index, then you will have to iterate over the data.

The down side of an array is the fact that its data is stored sequentially in memory. If you want to insert an element at index 1, then you have to move every single element to the right. Also, the array has to keep resizing itself as it grows, basically copying itself in order to make a new array with a larger capacity. If you want to remove an element in the begging, then you will have to move all the elements to left.

Arrays are good when you know the index, but are costly as they grow.

The reason why people talk highly about linked lists is because the most useful and efficient data structures are node based.

Papa Yev
  • 618
  • 7
  • 10
  • I have some trouble with this answer. In particular with your conclusion. In fact, the vast majority of basic data structures or algorithms are array-based and yield better performance in general purpose situations than non-array-based variants. A few examples: hashtables, arraylist, circular arrays/ring-buffers for queues/stacks. In terms of performance, the biggest benefit of arrays is cache locality. This benefit is so big that in most cases, even if arrays are theoretically at a downside, they are just plain out faster than anything else. – Zabuzard Jun 27 '22 at 14:29
  • Hence, the general approach to designing DS and algos often is that you always have to consider making an array-based variant - even if its at a heavy disadvantage complexity-wise. If you actually benchmark the array-based vs non-array-based variant, the array-based version often surprisingly is the better version for all input sizes occured in practice. – Zabuzard Jun 27 '22 at 14:31
  • A small example from my own career: For years, we have been researching for shortest-path algorithms that work well on public transport networks. Then, someone came up with creating an array-based algorithm (CSA) that is pretty straightforward and not that much clever at all. Complexity-wise its also worse. However, its absolutely superior than what we had before in practice. Simply due to the fact that it runs on arrays and hence can exploit cache locality. – Zabuzard Jun 27 '22 at 14:34