Comparison of Linked Lists with

Arrays and Dynamic Arrays

 Arra
• One memory block is allocated for the entire array to hold the elements
of the array. y
• The array elements can be accessed in constant time by using the index
of the particular element as the subscript.
• Constant Time for Accessing Array Elements:
 To access an array element, the address of an element is computed
as an offset from the base address of the array and one
multiplication is needed to compute offset and it is added to the
base address to get the memory address of the element.
 First the size of an element of that data type is calculated and then it
is multiplied with the index of the element to get the value to be
added(offset) to the base address.
 This process takes one multiplication and one addition. Since these
two operations take constant time. Thus we can say that the array
access can be performed in constant time.
 Example

Index
• An element of an array say “A[ i ]” is calculated using the following
formula:
Address of A [ i ] = Base_Address + Width * ( i– LB )
• Where,
WidthStorage Size of one element in the array (in byte)
i Subscript (or) Index of element whose address is to be
found
LB Lower Bound of subscript, if not specified assume 0 (zero)

• Example:
print A[3]
address of A[3]= 1100 + 4 * 3 = 1100 +12 = 1112
hence, print A[3]  print A[1112]  44(output)
 Insertion on Array- at front
Insert 99 at the front of the Array
Given array X
A 10 34 26 17 29 8 12 99
0 1 2 3 6 7
4 5

Shift the array element to make place at index-0

A 10 34 26 17 29 8 12
0 3 4 5 6 7

A 2
99 10 34 26 17 29 8 12
0 1 2 3 4 5
Now copy 99 to array index-0 6 7
In general, Time Complexity required to insert the element at
front of the array= O(n), if the array is not full
 Insertion on Array- at end
Insert 99 at the end of the Array

Given array
X
A 10 34 26 17 29 8 12 99
0 1 2 3 4 5 6
7

Compute address of index-7 and place the value 99 at that address

A 10 34 26 17 29 8 12 99
0 1 2 3 4 5 6 7

We know that address calculation from index position requires constant

time
In general, Time Complexity required to insert the element at
end of the array= O(1) , if array is not full
 Insertion on Array- in middle
Insert 99 at index-2 in the Array

Given array
X
A 10 34 26 17 29 8 12 99
0 1 2 3 6 7
4 5

Shift the array element to make place at index-2

A 10 34 26 17 29 8 12
0 3 4 5 6 7

1
A 10 34 99 26 17 29 8 12
2 0 1 2 3 4 5
Now copy 99 to array index-2 6 7
In general, Time Complexity required to insert the element in the
middle (at any position) of the array= O(n) , if array is not full
 Deletion on Array- at front
Delete value 10 from the Array
Given array Value to be
Deleted
A 10 34 26 17 29 8 12 10
0 1 2 3 4 5 6 7
Remove value at index-0

A 34 26 17 29 8 12
0 1 2 3 4 5
6 7
Shift the array element to adjust the values to start from index-0
34 26 17 29 8 12
A
0 1 2 3 4
Ingeneral, Time Complexity required
5 6 to delete
7 the element at
front of the array= O(n)
 Deletion on Array- at end
Delete value 12 from the Array

Given array Value to be

Deleted
10 34 26 17 29 8 12
A 12
0 1 2 3 4 5 6 7

Remove value at index-6

A 10 34 26 17 29 8
0 1 2 3 4 5 6 7

We know that address calculation from index position requires constant time

In general, Time Complexity required to delete the element at

end of the array= O(1)
 Deletion on Array- in the middle
Delete value 26 from the Array
Given array Value to be
Deleted
A 10 34 26 17 29 8 12 26
0 1 2 3 4 5 6 7
Remove value at index-2

A 10 34 17 29 8 12
0 1 2 3 4 7
5 6
Shift the array 10
element34
to adjust
17 the 29
empty space
8 at12index-2
A
0 1 2 3 4 5
6 7
In general, Time Complexity required to delete the element in the
middle (at any position) of the array= O(n)
Advantages of Arrays
 Simple and easy to use
 Faster access to the elements (constant access)
Disadvantages of Arrays
 Pre-allocates all needed memory and wastes memory space for
indices in the array that are empty.
 Fixed size: The size of the array is static (specify the array size
before using it).
 One block allocation (contiguous memory allocation): To allocate
the array itself at the beginning, sometimes it may not be possible
to get the memory for the complete array (if the array size is big).
 Data must be shifted during insertions and deletions
 Dynamic Arrays

• Dynamic array (also called as growable array, resizable array,

dynamic table) is a random access, variable-size list data
structure that allows elements to be added or removed.
• One simple way of implementing dynamic arrays is to initially
start with some fixed size array. As soon as that array becomes
full, create the new array double the size of the original array.
(growing)
• Reduce the array size to half if the elements in the array are less
than half. (shrinking)
 Insertion on Dynamic Array- at front
Insert 99 at the front of the Array
Given array
X
A 10 34 26 17 29 8 12 99
0 1 2 3 6 7
4 5

Shift the array element to make place at index-0

A 10 34 26 17 29 8 12
0 3 4 5 6 7

A 2
99 10 34 26 17 29 8 12
0 1 2 3 4 5
Now copy 99 to array index-0 6 7
In general, Time Complexity required to insert the element at
front of the array= O(n), if the array is full or not full
 Insertion on Dynamic Array- at end
Insert 99 at the end of the Array
Case-1 : array has space (array is not Full)
Given array X
A 10 34 26 17 29 8 12 99
0 1 2 3 4 5 6 7

Compute address of index-7 and place the value 99 at that address

A 10 34 26 17 29 8 12 99
0 1 2 3 4 5 6 7

We know that address calculation from index position requires constant

time
In general, Time Complexity required to insert the element at
end of the array= O(1) , if array is not full
 Insertion on Dynamic Array- at end
Insert 99 at the end of the Array
Case-2 : array has no space (array is FULL)
Given array size= 7 Given array X
A 10 34 26 17 29 8 12 99
0 1 2 3 4 5 6

!The given array is full and there is no space for a new element! So we will
create a new bigger array . Double the given array size
New array size= 14

B
0 1 2 3 4 5 6 7 10 11 12 13
8 9
Now copy the elements of the old array into new array
B 10 34 26 17 29 8 12
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Now insert 99 to new array at index- 7

B 10 34 26 17 29 8 12 99
0 1 2 3 4 5 6 7 8 9 10 11 12 13

In general, Time Complexity required to insert the element at end of

the array= O(n) , if array is full
 Insertion on Dynamic Array- in middle
Insert 99 at index-2 in the Array
Given array
X
A 10 34 26 17 29 8 12 99
0 1 2 3 6 7
4 5

Shift the array element to make place at index-2

A 10 34 26 17 29 8 12
0 3 4 5 6 7

1
A 10 34 99 26 17 29 8 12
20 1 2 3 4 5
Now copy 99 to array index-2 6 7
In general, Time Complexity required to insert the element in the
middle (at any position) of the array= O(n), if array is full or not full
 Deletion on Dynamic Array- at front
Delete value 10 from the Array
Given array Value to be
Deleted
A 10 34 26 17 29 8 12 10
0 1 2 3 4 5 6 7
Remove value at index-0

A 34 26 17 29 8 12
0 1 2 3 4 5
6 7
Shift the array element to adjust the values to start from index-0
34 26 17 29 8 12
A
0 1 2 3 4 5
Ingeneral, Time Complexity
6 required
7 to delete the element at
front of the array= O(n)
 Deletion on Dynamic Array- at end
Delete value 12 from the Array

Value to be
Given array Deleted
A 10 34 26 17 29 8 12 12
0 1 3 4 5 6 7
2

Remove value at index-6

A 10 34 26 17 29 8
0 1 2 3 4 5 6 7

We know that address calculation from index position requires constant time

In general, Time Complexity required to delete the element at

end of the array= O(1)
 Deletion on Dynamic Array- in the middle
Delete value 26 from the Array
Given array Value to be
Deleted
A 10 34 26 17 29 8 12 26
0 1 2 3 4 5 6 7
Remove value at index-2

A 10 34 17 29 8 12
0 1 2 3 4 7
5 6
Shift the array 10
element34
to adjust
17 the 29
empty space
8 at12index-2
A
0 1 2 3 4 5
6 7
In general, Time Complexity required to delete the element in the
middle (at any position) of the array= O(n)
• Advantages of Dynamic Array:
 Fast random access of elements.
 Efficient in terms of memory usage
 Variable size. You can add as many items as you want,
and the dynamic array will expand to hold them.

• Disadvantages of Dynamic Array:

 Data must be shifted during insertions and deletions
 Data must be copied from old array during the resizing
of the array
• Advantages of Linked List:
 Is able to grow in size as needed
Does not require the shifting of items during
insertions and deletions
• Disadvantage of Linked List:
Accessing an element does not take a constant
time
Need to store links to maintain the logical order of
the elements (memory overhead).
 Comparison of Linked Lists with Arrays and Dynamic Arrays
Operation Linked List Array Dynamic Array
Indexing O(n) O(1) O(1)
Insertion at the front O(1) O(n), if array is not O(n)
full(or shifting)
Deletion at the front O(1) O(n) O(n)

Insertion at the end O(n) O(1), if array is not O(1), if array is not
full full
O(n), if array is full
Deletion at the end O(n) O(1) O(1)
Insertion in Middle O(n) O(n), if array is not O(n)
full (for shifting)
Deletion in Middle O(n) O(n) O(n)