When to use a linked list over an array/array list?

Linked lists are preferable over arrays when:

1. you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

2. you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

3. you don't need random access to any elements

4. you want to be able to insert items in the middle of the list (such as a priority queue)

Arrays are preferable when:

1. you need indexed/random access to elements

2. you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

3. you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

4. memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.

Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

Arrays have O(1) random access, but are really expensive to add stuff onto or remove stuff from.

Linked lists are really cheap to add or remove items anywhere and to iterate, but random access is O(n).

To add to the other answers, most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O(1) time. When the capacity of an array list is exceeded, a new, larger array is allocated internally, and all the old elements are copied over. Usually, the new array is double the size of the old one. This means that on average, adding new elements to the end of an array list is an O(1) operation in these implementations. So even if you don't know the number of elements in advance, an array list may still be faster than a linked list for adding elements, as long as you are adding them at the end. Obviously, inserting new elements at arbitrary locations in an array list is still an O(n) operation.

Accessing elements in an array list is also faster than a linked list, even if the accesses are sequential. This is because array elements are stored in contiguous memory and can be cached easily. Linked list nodes can potentially be scattered over many different pages.

I would recommend only using a linked list if you know that you're going to be inserting or deleting items at arbitrary locations. Array lists will be faster for pretty much everything else.

The advantage of lists appears if you need to insert items in the middle and don't want to start resizing the array and shifting things around.

You're correct in that this is typically not the case. I've had a few very specific cases like that, but not too many.

In reality memory locality has a huge performance influence in real processing.

The increased use of disk streaming in "big data" processing vs random access shows how structuring your application around this can dramatically improve performance on a larger scale.

If there is any way to access an array sequentially that is by far the best performing. Designing with this as a goal should be at least considered if performance is important.

Hmm, Arraylist can be used in cases like follows I guess:

1. you are not sure how many elements will be present
2. but you need to access all the elements randomly through indexing

For eg, you need to import and access all elements in a contact list (the size of which is unknown to you)

Arrays, by far, are the most widely used data structures. However, linked lists prove useful in their own unique way where arrays are clumsy - or expensive, to say the least.

Linked lists are useful to implement stacks and queues in situations where their size is subject to vary. Each node in the linked list can be pushed or popped without disturbing the majority of the nodes. Same goes for insertion/deletion of nodes somewhere in the middle. In arrays, however, all the elements have to be shifted, which is an expensive job in terms of execution time.

Binary trees and binary search trees, hash tables, and tries are some of the data structures wherein - at least in C - you need linked lists as a fundamental ingredient for building them up.

However, linked lists should be avoided in situations where it is expected to be able to call any arbitrary element by its index.

A simple answer to the question can be given using these points:

1. Arrays are to be used when a collection of similar type data elements is required. Whereas, linked list is a collection of mixed type data linked elements known as nodes.

2. In array, one can visit any element in O(1) time. Whereas, in linked list we would need to traverse entire linked list from head to the required node taking O(n) time.

3. For arrays, a specific size needs to be declared initially. But linked lists are dynamic in size.