difference between array and list

Question

what is the difference between array and list?

Answer 1

In C, an array is a fixed-size region of contiguous storage containing multiple objects, one after the other. This array is an "object" in the meaning which C gives to the word - basically just some memory that represents something. An object could just be an int.

You can distinguish slightly between array objects, and array types. Often people use array objects which are allocated with malloc, and used via a pointer to the first element. But C does also have specific types for arrays of different sizes, and also for variable-length-arrays, whose size is set when they are created. VLAs have a slightly misleading name: the size is only "variable" in the sense that it isn't fixed at compile time. It can't change during the lifetime of the object.

So, when I say an array is fixed-size I mean that the size cannot change once the array is created, and this includes VLAs. There is realloc, which logically returns a pointer to a new array that replaces the old one, but can sometimes return the same address passed in, having changed the size of the array in place. realloc operates on memory allocations, not on arrays in general.

That's what an array is. The C programming language doesn't define anything called a list. Can't really compare something which is well defined, with something that isn't defined ;-) Usually "list" would mean a linked list, but in some contexts or in other languages it means other things.

For that matter, in other languages "array" could mean other things, although I can't immediately think of a language where it means anything very different from a C array.

If your question really has nothing to do with C, and is a language-agnostic data-structures question, "what is the difference between an array and a linked list?", then it's a duplicate of this:

Array versus linked-list

Answer 2

There is no such thing as a standard list in C. There is such a thing in C++, where it is implemented as a double-linked list.

The main differences are that arrays have random access - you can access any member of the array in O(1) time (i.e. if a was an array, a[4]) and have a pre-set size at compile time. Linked lists have sequential access - to access an element, you have to loop through the list until you get to the element you want (i.e. if b was a linked list, to get to the 5th element of b you would have to iterate through elements 0, 1, 2, 3 and 4), and the size can be grown and shrunk dynamically.