difference between array and list

Question

what is the difference between array and list?

Answer 1

Although there is nothing like a list in C per se but you sure could be talking about a linked lists implementation.

Array: Random access, predefine size.
Linked List: Sequential access, size at runtime.

Other languages like, say Python, may have have both lists and arrays inbuilt and their meaning may differ.

Useful comments from below:

You could add array lists. Lists which internally is an array which is doubled when needed and halved when only 1/4 full. This gives O(1) for add, remove, get(index) amortized. – lasseespeholt

Python's list is not a linked list. And the distinction between Python list and array is list can store anything while array can only store primitive types (int, float, etc). – KennyTM

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.

Answer 3

In C, an array is a fixed-size region of contiguous storage containing multiple objects, one after the other. This is "object" in the meaning which C gives to the word - basically just some memory that represents something, so 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 compiled time. It can't change during the lifetime of the object.

So, by fixed-size I mean that the size basically cannot be changed once the array is created. There is realloc, which can sometimes change the size of the array in place, or might have to copy the contents to a new location and return a (pointer to a) new array which replaces the old one. realloc operates on memory allocations, though, 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:

http://stackoverflow.com/questions/166884/array-vs-linked-list