When to use a linked list over an array/array list?

Question

I use a lot of lists and arrays but I have yet to come across a scenario in which the array list couldn't be used just as easily as, if not easier than, the linked list. I was hoping someone could give me some examples of when the linked list is notably better.

Tarango

In Java, ArrayList and LinkedList use exactly the same code other than the constructor. Your "array list...used as easily as or easier than the linked list" doesn't make sense. Please provide an example of an ArrayList being "easier" than a LinkedList. – Yuk

Check this as well, #323215 – Typify

Possible duplicate of Array versus linked-list – Russianize

S.Lott That is not true. The Java ArrayList is a wrapper around an Array, with some utility functions added. A linked list is, obviously, a linked list. developer.classpath.org/doc/java/util/ArrayList-source.html – Sphery

Answer 1

Linked lists are preferable over arrays when:

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

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

3. you don't need random access to any elements

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

Arrays are preferable when:

1. you need indexed/random access to elements

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

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

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

Gigantes

Good start, but this leaves out important things: lists support structure sharing, arrays are denser and have better locality. – Multifold

Practically, the performance difference between arraylists and arrays is negligible. This assumes you compare comparable and, for example, when you know the size beforehand, you tell the arraylist about it. – Macknair

Since when does LinkedList has O(1) inserts/deletes (which is what I suppose you mean when you say constant time inserts/deletes)? Inserting stuff into the middle of a LinkedList is always O(n) – Facilitate

LinkedLists do have O(1) inserts if you already happen to be in the location of the insertion (via an iterator). Not always, though. – Diabolo

Using linked lists for priority queues is a very stupid idea. Dynamic array-backed heaps allow for O(lg n) amortized insertion and worst-case logarithmic delete-min, and are among the fastest practical priority queue structures. – Volatilize

@Gigantes Can you give me a real world example about constant-time insertions/deletions ? I don't understand very well. – Sainthood

@İsmailKocacan Imagine a traversal algorithm that only ever cares about a "current" item and the neighboring items and you need to be able to insert a new item next to the current item, or you need to delete an item from this narrow window, then you don't need the random access provided array. Think about how an array is like a dictionary with int keys; whereas a LinkedList is like audio tape running through a magnetic tape head. In the olden days, an audio editor could splice/delete part of the tape at a given point. It would make sense for that point to be near where the tape head is – Frap

The best example I can think of a real-world use would be a Rolodex sorted by last name. If you needed to add new entries, edit old entries, delete old entries, it might make the most sense to do all of these tasks in the order of the Rolodex, so you would go through each card and insert/edit/delete as needed. – Frap

After reading my professor's code, I think I can see some reason in your explanation. In a linked list, you don't necessarily store the object or a pointer to it, you have a bunch of node objects that store pointers to each other and to the corresponding object. For example, If I have three Person objects - Tom, Dick, and Harry - and I wanted a linked list, I'd create a node that stores Tom - or a pointer to him - and a pointer to another node, which stores both Dick - or a pointer to him - and a pointer to another node that stores Harry - or a pointer to him. – Joses

That sounds like a deque? – Dellinger

@Facilitate In the case of a doubly linked list you could have a custom implementation with a reference to the element in the middle and have the reference adjust its position per inserts/deletes. This will achieve a O(1) for inserts exactly in the middle. – Rotterdam

@Pacerier, Inserting stuff into the middle of a LinkedList is only O(n) if you include the cost of a linear search. In an array you also need to do a search if you didn't already have the index, which would also be a linear search if it's unsorted. If you already have the index, then the linked list equivalent is that you already have the pointer or iterator to the location, and then insertion is O(1). – Disbelief

Answer 2

Arrays have O(1) random access, but are really expensive to add stuff onto or remove stuff from.

Linked lists are really cheap to add or remove items anywhere and to iterate, but random access is O(n).

Scrappy

Removing items from the end of an array is contant-time, as is inserting/removing items from either end of a linked list. In the middle ... not so much for either. – Obligato

@Obligato isn't insertion/deletion at the end of a Linked List O(n)? Unless you're already positioned at the penultimate link, you'll still need O(n) steps to find the last element, no? – Riverine

@AlexMoore-Niemi: For a singly-linked list, yes. But many have links forward and back, and thus keep pointers to either end. – Obligato

Having a doubly linked lists will cause you to do searching forward and backward, unless your LL has ordered values ... and still the worst case scenario is O(n) – Brazenfaced

"Linked lists are really cheap to add or remove items anywhere and to iterate" is not entirely true. If I want to remove an item which is in the middle of a linked list, I will have to iterate from the start till I reach that item in the list. Its O(n/2) time where n = number of items in the list. From your answer it sounds like you are suggesting its constant time O(1) like it is in array. It is constant time to add/remove from a linked list’s head / root node. – Medeiros

Linked lists are rather expensive to iterate actually. Following all those pointers all over the memory absolutely kills cache-locality. – Facetious

Answer 3

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists are good for write-once-read-many or appenders, but bad at add/remove from the front or middle.

Bendicty

Note that O(1) for insert after an item in linked list is true only if you already have the pointer to the element after which you have to insert the new node. Otherwise, you will have to iterate the linked list until you find the correct position and that would be O(N). – Virgule

Pretty sure O(1) for arraylist end insertion is only true if there is an index available. If an open location is not available, the array will have to be resized and the existing elements copied over, which is O(n) time – Denationalize

Inseting after an item (simply said "insert") is O(n) in linked list, not O(1)! – Unfortunate

Answer 4

To add to the other answers, most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O(1) time. When the capacity of an array list is exceeded, a new, larger array is allocated internally, and all the old elements are copied over. Usually, the new array is double the size of the old one. This means that on average, adding new elements to the end of an array list is an O(1) operation in these implementations. So even if you don't know the number of elements in advance, an array list may still be faster than a linked list for adding elements, as long as you are adding them at the end. Obviously, inserting new elements at arbitrary locations in an array list is still an O(n) operation.

Accessing elements in an array list is also faster than a linked list, even if the accesses are sequential. This is because array elements are stored in contiguous memory and can be cached easily. Linked list nodes can potentially be scattered over many different pages.

I would recommend only using a linked list if you know that you're going to be inserting or deleting items at arbitrary locations. Array lists will be faster for pretty much everything else.

Battery

In addition, you can also implement linked lists (in the Abstract Data Type sense) using dynamic arrays. In this way you can leverage the computer cache while having amortized constant time insertions and deletions at the head of the list and also amortized constant time insertions and deletions in the middle of the list when you have the index of the element after which the insertion must be done or the index of the element to delete (no shifts/unshifts needed). A good reference for this is CLRS 10.3. – Abb

Answer 5

The advantage of lists appears if you need to insert items in the middle and don't want to start resizing the array and shifting things around.

You're correct in that this is typically not the case. I've had a few very specific cases like that, but not too many.

Joker

Shifting and the resizing the array is what actually happens when you do inversions in the middle. You will only need shifting without resizing if you don't hit the amortization bound. – Brazenfaced

Answer 6

It all depends what type of operation you are doing while iterating , all data structures have trade off between time and memory and depending on our needs we should choose the right DS. So there are some cases where LinkedList are faster then array and vice versa . Consider the three basic operation on data structures.

• Searching

Since array is index based data structure searching array.get(index) will take O(1) time while linkedlist is not index DS so you will need to traverse up to index , where index <=n , n is size of linked list , so array is faster the linked list when have random access of elements.

Q.So what's the beauty behind this ?

As Arrays are contiguous memory blocks, large chunks of them will be loaded into the cache upon first access this makes it comparatively quick to access remaining elements of the array,as much as we access the elements in array locality of reference also increases thus less catch misses, Cache locality refers to the operations being in the cache and thus execute much faster as compared to in memory,basically In array we maximize the chances of sequential element access being in the cache. While Linked lists aren't necessarily in contiguous blocks of memory, there's no guarantee that items which appear sequentially in the list are actually arranged near each-other in memory, this means fewer cache hits e.g. more cache misses because we need to read from memory for every access of linked list element which increases the time it takes to access them and degraded performance so if we are doing more random access operation aka searching , array will be fast as explained below.

• Insertion

This is easy and fast in LinkedList as insertion is O(1) operation in LinkedList (in Java) as compared to array, consider the case when array is full, we need to copy contents to new array if array gets full which makes inserting an element into ArrayList of O(n) in worst case, while ArrayList also needs to update its index if you insert something anywhere except at the end of array , in case of linked list we needn't to be resize it, you just need to update pointers.

• Deletion

It works like insertions and better in LinkedList than array.

Cannibalize

inserting in a list is also O(n) worst case... – Schofield

Arrays don't have O(1) search. Access isn't the same as search. – Disbelief

Answer 7

In reality memory locality has a huge performance influence in real processing.

The increased use of disk streaming in "big data" processing vs random access shows how structuring your application around this can dramatically improve performance on a larger scale.

If there is any way to access an array sequentially that is by far the best performing. Designing with this as a goal should be at least considered if performance is important.

Pintsize

Answer 8

Those are the most common used implementations of Collection.

ArrayList:

• insert/delete at the end generally O(1) worst case O(n)

• insert/delete in the middle O(n)

• retrieve any position O(1)

LinkedList:

• insert/delete in any position O(1) (note if you have a reference to the element)

• retrieve in the middle O(n)

• retrieve first or last element O(1)

Vector: don't use it. It is an old implementation similar to ArrayList but with all methods synchronized. It is not the correct approach for a shared list in a multithreading environment.

HashMap

insert/delete/retrieve by key in O(1)

TreeSet insert/delete/contains in O(log N)

HashSet insert/remove/contains/size in O(1)

Jackknife

Answer 9

I think that main difference is whether you frequently need to insert or remove stuff from the top of the list.

With an array, if you remove something from the top of list than the complexity is o(n) because all of the indices of the array elements will have to shift.

With a linked list, it is o(1) because you need only create the node, reassign the head and assign the reference to next as the previous head.

When frequently inserting or removing at the end of the list, arrays are preferable because the complexity will be o(1), no reindexing is required, but for a linked list it will be o(n) because you need to go from the head to the last node.

I think that searching in both linked list and arrays will be o(log n) because you will be probably be using a binary search.

Silvio

Answer 10

Hmm, Arraylist can be used in cases like follows I guess:

1. you are not sure how many elements will be present
2. but you need to access all the elements randomly through indexing

For eg, you need to import and access all elements in a contact list (the size of which is unknown to you)

Cateyed

Answer 11

Use linked list for Radix Sort over arrays and for polynomial operations.

Halfhearted

Answer 12

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

2) Search (get method) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

Errata

Answer 13

I did some benchmarking, and found that the list class is actually faster than LinkedList for random inserting:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

It takes 900 ms for the linked list and 100ms for the list class.

It creates lists of subsequent integer numbers. Each new integer is inserted after a random number which is already in the list. Maybe the List class uses something better than just an array.

Pinkeye

List is an interface, not a class – Memorable

This doesn't just do insert. Your linked list benchmark is dominated by searching time. – Disbelief

My test did the same searching with the list class though. I assume that you usually need to find the place where something needs to be inserted. Ok, the linked list would work better if you already have somehow a pointer to the element where you want to insert something. Anyway, the point is, List is doing very well for inserts, much better than an error or c++ vector. And @borgmater, of course List is a class, implementing interfaces such as IList – Pinkeye

Answer 14

Arrays, by far, are the most widely used data structures. However, linked lists prove useful in their own unique way where arrays are clumsy - or expensive, to say the least.

Linked lists are useful to implement stacks and queues in situations where their size is subject to vary. Each node in the linked list can be pushed or popped without disturbing the majority of the nodes. Same goes for insertion/deletion of nodes somewhere in the middle. In arrays, however, all the elements have to be shifted, which is an expensive job in terms of execution time.

Binary trees and binary search trees, hash tables, and tries are some of the data structures wherein - at least in C - you need linked lists as a fundamental ingredient for building them up.

However, linked lists should be avoided in situations where it is expected to be able to call any arbitrary element by its index.

Jamille

Answer 15

A simple answer to the question can be given using these points:

1. Arrays are to be used when a collection of similar type data elements is required. Whereas, linked list is a collection of mixed type data linked elements known as nodes.

2. In array, one can visit any element in O(1) time. Whereas, in linked list we would need to traverse entire linked list from head to the required node taking O(n) time.

3. For arrays, a specific size needs to be declared initially. But linked lists are dynamic in size.

Hammad

Answer 16

"I was hoping someone could give me some examples of when the linked list is notably better (than arrays)."

I'm going to assume dynamic arrays with exponential expansion policy so we aren't limited to fixed size, and have efficient append. Basically the linked list is going to be better when inserting/removing any sequence of elements anywhere except at the back. Search in an array is only better complexity wise if elements are sorted and you use a binary search.

The table below makes the linked list look very good indeed, but the big O complexity ignores effects of the cache (for a small enough dynamic array, the O(N) operations may even be faster than the equivalent operation on the linked list). The (dynamic) array is a lot more cache friendly and therefore faster (as already explained by others) when traversing elements, accessing them one by one. This may weigh heavier on your application than other aspects, biasing you toward (dynamic) arrays.

Operation                       DynamicArray   LinkedList
=========================================================
access front                    O(1)           O(1)
access back                     O(1)           O(1)
access using iterator           O(1)           O(1)
advance iterator by k           O(1)           O(k)
search unsorted,sorted          O(N),O(log(N)) O(N),O(N)
insert/remove at front          O(N)           O(1)
insert/remove at back           O(1)           O(1)
insert before/after iterator    O(N)           O(1)
remove at/before/after iterator O(N)           O(1)
concatenate other of size M     O(M)           O(1)
extract range [it1,it2] to new  O(N)           O(1)

I also often see the argument that dynamic arrays invalidate references and linked lists don't. If that's an issue, you can use a (dynamic) array of pointers to elements. Same goes if the elements are huge and you want to avoid copying them.

Disbelief