Array vs Linked List

Array and Linked list are the two ways of organizing the data in the memory. Before
understanding the differences between the Array and the Linked List, we first look at
an array and a linked list.

What is an array?
An array is a data structure that contains the elements of the same type. A data
structure is a way of organizing the data; an array is a data structure because it
sequentially organizes the data. An array is a big chunk of memory in which memory is
divided into small-small blocks, and each block is capable of storing some value.

Suppose we have created an array that consists of 10 values, then each block will store
the value of an integer type. If we try to store the value in an array of different types,
then it is not a correct array and will throw a compile-time error.

Declaration of array
An array can be declared as:fference between JDK, JRE, and JVM

NextStay
1. data_type name of the array[no of elements]   

To declare an array, we first need to specify the type of the array and then the array's
name. Inside the square brackets, we need to specify the number of elements that our
array should contain.

Let's understand through an example.

1. int a[5];  

In the above case, we have declared an array of 5 elements with 'a' name of
an integer data type.

What is Linked list?

A linked list is the collection of nodes that are randomly stored. Each node consists of
two fields, i.e., data and link. Here, data is the value stored at that particular node, and
the link is the pointer that holds the address of the next node.

Differences between Array and Linked list

We cannot say which data structure is better, i.e., array or linked list. There can be a
possibility that one data structure is better for one kind of requirement, while the other
data structure is better for another kind of requirement. There are various factors like
what are the frequent operations performed on the data structure or the size of the
data, and other factors also on which basis the data structure is selected. Now we will
see some differences between the array and the linked list based on some parameters.

1. Cost of accessing an element

In case of an array, irrespective of the size of an array, an array takes a constant time for
accessing an element. In an array, the elements are stored in a contiguous manner, so if
we know the base address of the element, then we can easily get the address of any
element in an array. We need to perform a simple calculation to obtain the address of
any element in an array. So, accessing the element in an array is O(1) in terms of time
complexity.
In the linked list, the elements are not stored in a contiguous manner. It consists of
multiple blocks, and each block is represented as a node. Each node has two fields, i.e.,
one is for the data field, and another one stores the address of the next node. To find
any node in the linked list, we first need to determine the first node known as the head
node. If we have to find the second node in the list, then we need to traverse from the
first node, and in the worst case, to find the last node, we will be traversing all the
nodes. The average case for accessing the element is O(n).

We conclude that the cost of accessing an element in array is less than the linked list.
Therefore, if we have any requirement for accessing the elements, then array is a better
choice.

2. Cost of inserting an element

There can be three scenarios in the insertion:

o Inserting the element at the beginning: To insert the new element at the
beginning, we first need to shift the element towards the right to create a space
in the first position. So, the time complexity will be proportional to the size of the
list. If n is the size of the array, the time complexity would be O(n).

In the case of a linked list, to insert an element at the starting of the linked list, we will
create a new node, and the address of the first node is added to the new node. In this
way, the new node becomes the first node. So, the time complexity is not proportional
to the size of the list. The time complexity would be constant, i.e., O(1).
 o Inserting an element at the end

If the array is not full, then we can directly add the new element through the index. In
this case, the time complexity would be constant, i.e., O(1). If the array is full, we first
need to copy the array into another array and add a new element. In this case, the time
complexity would be O(n).

To insert an element at the end of the linked list, we have to traverse the whole list. If
the linked list consists of n elements, then the time complexity would be O(n).

o Inserting an element at the mid

Suppose we want to insert the element at the i th position of the array; we need to shift
the n/2 elements towards the right. Therefore, the time complexity is proportional to the
number of the elements. The time complexity would be O(n) for the average case.

In the case of linked list, we have to traverse to that position where we have to insert the
new element. Even though, we do not have to perform any kind of shifting, but we have
to traverse to n/2 position. The time taken is proportional to the n number of elements,
and the time complexity for the average case would be O(n).
The resultant linked list is:

o Ease of use

The implementation of an array is easy as compared to the linked list. While creating a
program using a linked list, the program is more prone to errors like segmentation fault
or memory leak. So, lots of care need to be taken while creating a program in the linked
list.

o Dynamic in size

The linked list is dynamic in size whereas the array is static. Here, static doesn't mean
that we cannot decide the size at the run time, but we cannot change it once the size is
decided.

3. Memory requirements
As the elements in an array store in one contiguous block of memory, so array is of fixed
size. Suppose we have an array of size 7, and the array consists of 4 elements then the
rest of the space is unused. The memory occupied by the 7 elements:
Memory space = 7*4 = 28 bytes

Where 7 is the number of elements in an array and 4 is the number of bytes of an

integer type.

In case of linked list, there is no unused memory but the extra memory is occupied by
the pointer variables. If the data is of integer type, then total memory occupied by one
node is 8 bytes, i.e., 4 bytes for data and 4 bytes for pointer variable. If the linked list
consists of 4 elements, then the memory space occupied by the linked list would be:

Memory space = 8*4 = 32 bytes

The linked list would be a better choice if the data part is larger in size. Suppose the
data is of 16 bytes. The memory space occupied by the array would be 16*7=112 bytes
while the linked list occupies 20*4=80, here we have specified 20 bytes as 16 bytes for
the size of the data plus 4 bytes for the pointer variable. If we are choosing the larger
size of data, then the linked list would consume a less memory; otherwise, it depends on
the factors that we are adopting to determine the size.

Let's look at the differences between the array and linked list in a tabular form.

Array Linked list

An array is a collection of elements of a A linked list is a collection of objects

similar data type. known as a node where node consists of
two parts, i.e., data and address.

Array elements store in a contiguous Linked list elements can be stored

memory location. anywhere in the memory or randomly
stored.

Array works with a static memory. Here The Linked list works with dynamic
static memory means that the memory memory. Here, dynamic memory means
size is fixed and cannot be changed at that the memory size can be changed at
the run time. the run time according to our
requirements.

Array elements are independent of each Linked list elements are dependent on
other. each other. As each node contains the
address of the next node so to access the
next node, we need to access its previous
node.

Array takes more time while performing Linked list takes less time while
any operation like insertion, deletion, etc. performing any operation like insertion,
deletion, etc.

Accessing any element in an array is Accessing an element in a linked list is

faster as the element in an array can be slower as it starts traversing from the first
directly accessed through the index. element of the linked list.

In the case of an array, memory is In the case of a linked list, memory is

allocated at compile-time. allocated at run time.

Memory utilization is inefficient in the Memory utilization is efficient in the case

array. For example, if the size of the array of a linked list as the memory can be
is 6, and array consists of 3 elements allocated or deallocated at the run time
only then the rest of the space will be according to our requirement.
unused.