Array V/s Linked List

Although both Arrays and Linked List implement List interface, they have some differences between them. The performance and internal working nature of both vary significantly. There are also some similarities between them.

ARRAY:

An Array is a default datatype used to store sequential data of a specific type. There are few key properties of an array when compared to a linked list data structure.

Array Properties:

• Contiguous: An array takes up a block of memory, where each element in the array is situated beside another element within the array.
• Random Access: Because an array is contiguous, each element can be accessed directly by its index within the array. In the example above the element with the value “4” can be accessed by array[3].
• Static: An array takes up a static block of memory, containing its starting point, its size, and the value of each element. Because it is static, an array cannot grow or shrink. If an element is added to an array, in actuality a whole new array must be made.
• Smaller memory allocation: Because each element within an array only needs to store its value, compared to a linked list, an array takes up less memory.

Linked List Data Structure:

A linked list is a collection of nodes, where each node contains the value of the node as well as a pointer (connection) to another node in the linked list.

• Non-contiguous: Each node within a linked list does not have to be stored next to any other node within the linked list. A node can be stored in any free piece of memory.
• Sequential Access: Because a linked list is not contiguous, it does not support random access. In order to access a particular node within the linked list, the entire linked list must be traversed until the node is found. In the example above, to access the node with a value of “4”: first, the “1”, “2” and “3” node must be traversed sequentially.
• Dynamic: A linked list can be dynamically altered without a new linked list needing to be created. For example, a node can be added easily by inserting the node and adding a reference to it within the linked list.
• Larger memory allocation: Unlike an array, each node within a linked list needs to store both its value and a reference to another node; therefore, it takes up more memory.

When to Use a Linked List? : Arrays are a default data-type, support random access, and take less memory than a linked list, so a logical question to ask is “why would you use a linked list”?

The main consideration when deciding to use a linked list over an array is the volatility of the data, in other words, how much the data will change. If the data is highly volatile, a linked list may be a superior data structure.

TLDR: (TOO LONG TO READ)?

ARRAYS

A default data type which contains similarly typed data.

• Contiguous support
• Random Access
• Static

Linked lists:

A data structure made of nodes containing similarly typed values and a reference to another node within the linked list. 

• non-contiguous
• support sequential access (no random access)
• dynamic

Linked lists are beneficial when:

• Data is highly volatile
• Random access is not needed

IN-FORM OF IMAGE: