1

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!

8
  • 1
    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. May 22, 2014 at 13:12
  • 1
  • 1
    You might also want to read about double-ended queues 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. May 22, 2014 at 13:19
  • 1
    LinkedList in java is doubly-linked. Yours is only single.
    – Bathsheba
    May 22, 2014 at 13:19
  • 1
    Java linked lists allow you to go forwards and back. (As does std::list in c++).
    – Bathsheba
    May 22, 2014 at 13:30

2 Answers 2

4

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.

3

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.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.