Arrays or linked-list for frequently random access?

Question

I'm using lists and arrays very often, I am wondering what is faster, array or list?

Let's say we have array of integers and linked-list, both hold same values.

int array_data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

typedef struct node_data{
    int data;
    struct node_data * next;
} list_data;

                  ____    ____    ____    ____    ____    ____    ____    ____    ____    ____
list_data *d = -> | 1| -> | 2| -> | 3| -> | 4| -> | 5| -> | 6| -> | 7| -> | 8| -> | 9| -> |10| -> NULL

If I want to get value of array_data on index 6, I'll use array_data[6] and get value of 7. But what if I want same data from list? Should I go from start and count hops till I reach asked index get_data(d,6)? Or there is better way to do this?

int get_data(list_data *l, int index){
    int i = 0;
    while(l != NULL){
        if(index == i){
            return l -> data;
        }
        i++;
        l = l -> next;
    }
    return 0;
}

How about using array of pointers to list elements? Will be this best solution in case I have more then 100,000 records or even more to save, and each record contains more then one data type. I'll mostly need insertion to the end, and very frequently access to elements.

Thanks!

An array of pointers will of course work. But it's a lot more work having both the array and the list and keeping them in sync. Think, for example, of what you have to do if you insert a new node in the middle of the list. You can of course do the opposite, have the data in the array, and a list with pointers (or indexes) to the array. — Some programmer dude, May 22 '14 at 13:12
[Array Vs. Linked List](http://stackoverflow.com/q/166884). [When to use LinkedList<> over ArrayList<>?](http://stackoverflow.com/q/322715) — Bernhard Barker, May 22 '14 at 13:14
Of course, I'll need to move each element of array for one and then add new node. But in my case I only need adding on the end of list. — Matjaž, May 22 '14 at 13:15
@Dukeling I just read first link, still can't decide what will be better and thanks for second link. But do `java` have implemented `LinkedList` and `ArrayList` same as C? — Matjaž, May 22 '14 at 13:18
You might also want to read about [double-ended queues](http://en.wikipedia.org/wiki/Double-ended_queue) if you only insert/remove nodes from the head or tail of the list. Then you have a list of fixed-size arrays and can easily simulate random-access. — Some programmer dude, May 22 '14 at 13:19
@Bathsheba Do you mean, you can go on next element or on previous? — Matjaž, May 22 '14 at 13:21
Java linked lists allow you to go forwards and back. (As does std::list in c++). — Bathsheba, May 22 '14 at 13:30

Mahonri Moriancumer · Accepted Answer · 2014-05-22T14:31:31.787

You are correct to consider the question each time; when deciding whether to implement an array, linked-list (or other) structure.

ARRAY

+ Fast random access.
+ Dynamically allocated arrays can be re-sized using `realloc()`.
+ Sorted using `qsort()`.
+ For sorted arrays, a specific record can be located using `bsearch()`

- Must occupy a contiguous block of memory.
- For a long-lived applications, frequent enlargement of the the array can eventually lead to a fragmented memory space, and perhaps even eventual failure of `realloc()`.
- Inserting and deleting elements is expensive. Inserting an element (in a sorted array) requires all elements of the array beyond the insertion point to be moved. A similar movement of elements is required when deleting an element.

LINKED-LIST

+ Does not require a contiguous block of memory.
+ Much more efficient than an array to re-size dynamically. Outperforms an array when it comes to fragmented memory usage
+ Sequential access is good, but perhaps still not as fast as an array (due to CPU cache misses, etc.).

- Random access is not really possible.
- Extra memory overhead for node pointers (priorNode, nextNode).

There are other structures that even combine arrays with linked list, such as hash tables, binary trees, n-trees, random-access-list, etc., each comes with various characteristics to consider.

score 3 · Answer 2 · answered May 22 '14 at 13:14

Arrays are constant in access time; i.e. it takes the same amount of time to access any element.

That's not true for lists: the average time taken is linear on the number of elements.

However, lists don't require a contiguous block of memory, unlike arrays. As such, appending to an array can cause memory reallocation which can wreak havoc with any pointers to array elements that you've stored.

These points are the principal considerations when choosing between an array and a list.

Arrays or linked-list for frequently random access?

2 Answers2

Linked