DS & A (Lists - Array Lists v/s Pointer Lists)

| CHAPTER 11 |

List Comparison: 

Array List vs Pointer List (Structure Comparison)

• Array List

• Pointer List

Array List vs Pointer List (Overall Comparison)

Array List	Linked(Pointer) List
Insertion and deletion are easy.	Insertion and deletion are complicated as elements cannot be accessed through indices.
Prev and Next element access are easier.	Prev and Next element access are comparatively complicated.
The list array must be allocated in advance.	The list grows with the increase in the number of elements.
No overhead if all array positions are full.	Every element has overheads.
Memory allocated for the Array List must be a contiguous block of memory.	Memory allocated for the Linked List doesn't need to be contiguous.
If we wanna store 100 elements in a List array then the memory required to store it must be a single big block of memory.	If we wanna store 100 elements in a Linked list then the total memory needed to store the list consists of chunks of memory from different memory locations.
Memory usage is not efficient as free space between used memory cannot be put to use if it's less than the total memory needed by the list.	Memory usage is more efficient as the free space between used memory can be put to use as long as it's not smaller than the size of an individual element.

Array List vs Pointer List (Memory Requirement)

Key Terms:

E: Data value size/Data size

P: Pointer Size

D: Size of array
n: number of elements stored in the list

Array Lists:

In the case of Array Lists, n ≤ D

Required memory space = D * E [D is constant] {* here means multipication}

Linked Lists:

In the case of Linked Lists, n = D [D increments with the addition of new elements]

Required memory space = D (E+P) = n (E+P)

Space Efficiency Comparision:

In general, the Linked List requires less space compared to an Array List. Conversely, the Array List requires less space if the array is nearly full. But those are all general statements, In case you want to find the better of the two in a specific situation, the following formula can be used to determine that.

We can say an Array List to be more space efficient if, DE < n(P+E) ⇒ n > E∕(P+E)

Therefore, as long as n > E∕(P+E) is maintained, Array List will be more space efficient compared to Linked List and vice-versa is true as well.

NOTE: Generally Linked Lists tend to be more space efficient while implementing a list with an unknown or varying number of elements. While on the other hand, Array-based lists tend to be more space efficient in case the required size of the list is known beforehand.

Singly Linked List vs Doubly Linked List (Overall Comparision)

Singly Linked List	Doubly Linked List
Allows direct access from a list node to the next node.	Allows direct access from a list node to both the previous and the next node.
Less overhead.	Larger overhead compared to singly linked list.
Efficient reverse iteration is not possible.	Reverse iteration is possible and is efficient.

( If you like the content here, follow TSP on social media to get notified on future updates)