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 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 4

1. For array, it has a fixed size like we write, new int [100] but list does not have a fixed size...it can go on and on

2. Insertion and Deletion is easier in list than in array Reason: we can simply use to change the pointers to insert and delete for linked list but for array insert and deletion needs shiftRight and shiftLeft

3. Linked List uses a dummy head node to avoid special cases of inserting into an empty list, or removing the last node from a list of unit size; and, it uses double links to allow iterating in both directions. The cost of course is the extra space needed to hold the dummy node (minimal cost), and the extra previous link in addition the usual next link for each node (much more significant cost). In array, we can add with the help of its random access

4. In Linked list, reference to the tail node is simply header.prev, which gives us ability to append to the list in constant time (without having to iterate to find the tail reference, or having to maintain a separate tail reference). But in array, we need to re-size the array before inserting.

5. Array has the flexibility to attain random access unlike Linked List.

Linked list has problems like,

It consumes extra memory storage for the pointer we are using!

Time complexity of O(n) instead of O(1) like in array

Reverse traversing is difficult for singly linked list and if we use doubly linked list, another pointer means more of extra memory storage

Heap Restriction as well! Memory is allocated only if there is space available in the heap. If insufficient memory then memory won't be created.

Array has problems like,

a chance of memory wastage or shortage.

Hope this helps ! :)

Answer 5

An often under appreciated characteristic of Linked data structures is that you can use them in situations where memory is highly fragmented due to there being no contiguous memory guarantee between elements. For example you could have 100MB of free space but only say a maximum run of free memory of length 10MB. In this case you can only create an an array of size 10MB but perhaps a potentially larger linked list since you would be able to make use of every run of free memory which was large enough to contain a single node.

Answer 6

array has only similar data types(i.e.,) they are homogeneous in nature. we can only have an array of strings , integers etc. also the size of array is predefined. but in the case of list we can have any type of elements. let it be a string integer or combination of both.Also null or duplicate elements are allowed in list. example of list include arraylist , linkedlist.here in list the size can grow or shrink at any time.