Array vs Linked List

A data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. One of the most important application design decisions involves which data structure to use. Arrays and linked lists are among the most common data structures, and each is applicable in different situations, both are used for storage of elements, but both are different techniques.

So, let's find out how both are different from each other. It will help you to determine which one is best for your application.

Array

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Differences between Array and Linked List

They both have some advantages and disadvantages over each other.

• In an array, elements are one after the another(successive memory allocation). But in a linked list, memory is not contiguous.

• Coding a linked-list is a bit more work than using an array and one may wonder what would justify the additional effort.

• Insertion of new elements is trivial in a linked-list but it's a major chore in an array.

• It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.

• It's easier for a linked list to grow organically. On the other hand, an array's size needs to be known ahead of time or re-created when it needs to grow.

• Shuffling a linked list is just a matter of changing what points to what. In contrast, shuffling an array is more complicated and/or takes more memory.

• Linked lists lend themselves nicely to efficient multi-threaded implementations. The reason for this is that changes tend to be local - affecting only a pointer or two for insert and remove at a localized part of the data structure. So, you can have many threads working on the same linked list. Even more, it's possible to create lock-free versions using CAS-type operations and avoid heavy-weight locks altogether.

• With a linked list, iterators can also traverse the list while modifications are occurring. In the optimistic case where modifications don't collide, iterators can continue without contention.

• With an array, any change that modifies the size of the array is likely to require locking a large portion of the array and in fact, it's rare that this is done without a global lock across the whole array so modifications become to stop the world affairs.

• In the linked list, random access is not allowed. You have to access elements sequentially starting from the first node. So, you cannot do the binary search with linked lists.

• Arrays have better cache locality that can make a pretty big difference in performance.

• Arrays allow random access, while linked lists allow only sequential access to elements.

• Sequential access on arrays is also faster than on linked lists on many machines due to the locality of reference and data caches. Linked lists receive almost no benefit from the cache.

• It's much easier to delete from the middle of a linked list than an array.

• Debugging an ArrayList will reveal a very easy to understand structure. But, linked lists are uncomfortable while debugging.

• The size of Linked lists is dynamic by nature. On the other hand, the size of the array is restricted to the declaration.

• A linked list is especially useful when the collection is constantly growing & shrinking.

• Linked List better from multithreading point of view.

• Caching is better in Arrays as all elements are allocated contiguous memory space.

• Array class can act as a list only because it implements List only. On the other side, linked list class can act as a list and queue both because it implements List and Deque interfaces.

• In the array, each element is independent and can be accessed using its index value. In case of a linked list, each node/element points to the next, previous, or maybe both nodes.

• An array can single dimensional, two dimensional or multidimensional, while the linked list can be Linear(Single), Doubly or Circular linked list.

• Array gets memory allocated in the Stack section. Whereas, the linked list gets memory allocated in Heap section.

• LinkedList is better for manipulating data.

• ArrayList is better for storing and accessing data.

Get more information about Linked List from our another article.

 

Lastly saying that it's really a matter of efficiency, the overhead to insert, remove or move elements inside a linked list is minimal, i.e. the operation itself is O(1), versus O(n) for an array. This can make a significant difference if you are operating heavily on a list of data. It's up to you, chose your data-types based on how you will be operating on them and choose the most efficient for the algorithm you are using. You can share your thought with us about these two data structure in the comments below. Thank you!