Arrays vs. Linked Lists

I honestly can’t recall the number of times I’ve been asked about the differences between arrays and linked lists. There has been countless times when people have come up to me and asked “When should I use arrays and when should I use linked lists?” Since I’m getting tired of answering this so many times I felt I should write down my answer here :P

I’ll go into a little detail of each data type and then I’ll explain when to use which

Arrays in C (as well as other languages) are used to store related data in one container. This container can be of any basic data type (ints, chars, etc) or any user defined data structures. The basic syntax is as follows:

 //General Example
datatype variablename[size];
//Array named 'var' with 10 ints (currently not initialized)
int var[10]; 
//Array named 'var' with 4 ints all initialized to 0
int var[] = {0,0,0,0}; 
//Syntax error (you need to declare the size)
char var[];

The way to read this would be “variablename has size elements of datatypes” or “var has 10 elements of ints”.

Here are some basic tidbits for arrays:

  1. The size is also called the index of the array
  2. In C, index values start from 0 and go up. They can be any unsigned integer (no doubles, floats, chars, etc…).
  3. Accessing an out of bounds element is always dangerous because sometimes the compiler will throw an error and sometimes it’ll just run along happily accessing garbage values. To make sure this doesn’t happen always use the following loop structure
int x;
int array[]= { 3, 6, 9, 12, 15 };
for (x=0; x < (sizeof(array)/sizeof(int)); x++)
     //Do your code

Now finally I’ll talk about arrays and the memory they’re stored in. Array elements are stored in contiguous memory (for those that don’t know contiguous memory just means memory thats next to each other).

Lets say you declare an array as follows

int array[2] = {1,3};

So you have two elements array[0] = 1 and array[1] = 3. Now lets say that the element 0 is stored in memory at location 0x700000 this means that element 1 would be stored at location 0x700004 since ints are 4 bytes. With this example you can see what I mean by contiguous memory.

Linked Lists
Linked lists are a series of nodes containing arbitrary data fields, linked together by pointers. Linked lists can be linked in one of two ways: 1) Singly linked or 2) Doubly linked. In both types the next node is connected by a pointer pointing to its location in memory. In the doubly linked list each node also has a pointer pointing to the location in memory of the previous node.

Linked lists can become much more complex than arrays because of the need for memory management. Below is a simple structure of a node.

struct node {
     int data;
     node* next;
} node;

As you can see each node has two fields. The first field is the data field, this could be any data type. The second field is a pointer to another node structure. This will be used as the next pointer. Here’s how you would declare a new pointer.

struct node* head = NULL;
head = malloc(sizeof(struct node));

You’ll see that I’ve created a pointer to a node called “head” and assigned it NULL. Now why did I assign it null instead of just leaving it blank. Well, mainly because it’s good practice. When you don’t assign it anything “head” would be pointing to a garbage value in memory and could cause problems. Now because of the next step it really doesn’t matter but its always good practice to assign all pointers the value of NULL initially.

So now that you have the node pointer “head” initialized how do I add data to it?

head->data = 1;
head->node = secondNode;

Here secondNode is an already initialized node.

Here’s a sample program on making a linked list

struct node
     int data;
     node* next;
} node;
void main() {
     struct node * curr, *head;
     int i;
     head  =  NULL;
     for(i = 1; i < 10; i++){
          curr =  malloc(sizeof(struct node));
          curr->data = i;
          curr->next = head;
          head = cur;
     curr = head;
          printf("%dn", curr->data);
          curr = curr->next;

This program loops 10 times each time creating a new node (called curr) and placing it as the new head. If you wanted to place it at the tail you’d just just do the loop this way:

for(i = 1; i < 10; i++){
     curr = malloc(sizeof(struct node));
     head->data = i;
     head->next = curr;
     head = curr;

So now that you know what arrays are and what linked lists are when should you use one another and what are their strengths and weaknesses


  1. Easy to use
  2. No memory management needed
  3. Can access any element by index
  4. Fairly quick to loop


  1. Static size (can’t increase the size)
  2. Most likely not enough or too much memory (you never know how many elements are needed)

Linked Lists

  1. Dynamic size (can increase or decrease the list)
  2. No memory is wasted


  1. Lots of overhead code (lots of malloc calls and assigning pointers)
  2. Must traverse entire list to go to the nth node.

Now I know that other languages such as C# and Java have better data structures than arrays and linked lists (like ArrayLists and Vectors), but this is for the C language and it doesn’t have those. So based on what you’ve read above you can decide which is better for the job needed. Neither arrays nor linked lists are better but they do have their specific purposes.

If you like this post than why not add devjargon( ); to your Free RSS Updates, or sign up for Free Email Updates.


  1. 1 06.30.08
    1:17 pm

    cur->data = i;
    cur->next = head;
    head = cur;

    Shouldn’t that be curr?

  2. 2 06.30.08
    1:22 pm

    Thanks Lamonte.

    I guess thats why you should spell check eh? :P

  3. 3 07.09.08
    9:56 am

    Very cool - an interesting follow-up would be singly-linked versus doubly-linked lists, and some examples of when/why you would do each - a discussion of the trade-offs.

    One thing on your array code:

    You should (especially for large arrays) take the sizeOf(array)/sizeOf(int) out of the for() loop and compute it as a variable immediately before the for() loop. The values are not being changed as part of walking the loop, so why recompute them each time?

    Also, and I apologize, I haven’t touched C code since college - is there a way to say sizeOf(typeOf(x)) instead of sizeOf(int)?

    It doesn’t matter since the index is always an int, but it just looks better to me. Only real impact is in establishing a coding style, so that you (or someone maintaining your code later) writes it more consistently in a situation where it does matter.

    Regardless, good article.

  4. 4 07.10.08
    10:48 am

    Thanks Scott, thats a very good point about taking the “sizeOf(array)/sizeOf(int)” out of the for loop. For small loops it wouldn’t make much of a difference but as the loop gets larger you would notice a large hit in efficiency and speed.

    AFAIK, you can use sizeOf(typeOf(x)) as a substitute to sizeof(int), but I have never used it.

    A follow-up article on singly vs doubly linked list will be coming soon.

Leave a Comment