Quiz #1

Q.1 What are the advantages and disadvantages of using a linked list over an array in terms of memory usage
and performance?

Solution:

When comparing linked lists and arrays in terms of memory usage and performance, both data structures have their
advantages and disadvantages based on specific use cases. Here’s a detailed comparison:

Advantages of Using Linked Lists Over Arrays:

1. Dynamic Memory Allocation:

o Linked List: Nodes are dynamically allocated as needed, which means you don’t need to reserve
memory in advance. This avoids the problem of wasted space when an array is declared too large
or the problem of resizing when an array becomes too small.

o Array: Arrays require a fixed amount of memory to be allocated ahead of time. If the array needs
to grow beyond its initial size, it often requires the entire array to be copied to a new memory
location (costly operation).

2. Efficient Insertions and Deletions:

o Linked List: Insertions and deletions (especially at the beginning or middle of the list) are more
efficient because they only involve changing the pointers (O(1) time for the head, O(n) for the tail
or any position based on traversal). There’s no need to shift elements.

o Array: Insertions and deletions (except at the end) require shifting elements to make room or to
fill gaps. This leads to O(n) time complexity for inserting or deleting at arbitrary positions.

3. No Memory Wastage:

o Linked List: Since memory is allocated only when nodes are created, there is no unused memory
allocation. The list can grow or shrink dynamically.

o Array: Arrays can have unused space (if sized too large) or may require resizing (if too small), which
involves costly reallocation and copying operations.

4. No Memory Contiguity Requirement:

o Linked List: Nodes can be scattered in memory, and there’s no requirement for them to be
contiguous. This can be advantageous when working in environments with fragmented memory.

o Array: Arrays require contiguous memory allocation. In systems with limited memory, finding a
large enough contiguous block of memory can be problematic, leading to memory allocation
failures.

Disadvantages of Using Linked Lists Over Arrays:

1. Memory Overhead:
 o Linked List: Each node requires extra memory for storing a pointer to the next (or previous in the
case of doubly linked lists). This pointer can significantly increase memory usage, especially for
small data elements.

o Array: Arrays only store the elements, without any extra memory overhead for pointers.

2. Cache Locality and Performance:

o Linked List: Due to the non-contiguous allocation of nodes, linked lists have poor cache locality.
When traversing a linked list, memory access can be scattered, leading to cache misses and slower
performance.

o Array: Arrays have excellent cache locality because the elements are stored in contiguous memory.
This results in faster memory access, as arrays take full advantage of CPU caching mechanisms.

3. Random Access:

o Linked List: Random access (i.e., accessing an element at index i) is not possible in constant time.
To access the i-th element, you need to traverse the list from the head, which takes O(i) time.

o Array: Arrays support O(1) random access, meaning you can directly access any element by its
index without needing to traverse the structure.

4. Traversal Cost:

o Linked List: Traversing a linked list requires O(n) time, and each access involves dereferencing a
pointer, which can be relatively slow compared to indexing in arrays.

o Array: Arrays allow traversal in O(n) time, but each access is direct due to the contiguous memory
layout, making traversal faster compared to linked lists.

5. Memory Allocation and Fragmentation:

o Linked List: Frequent insertions and deletions can cause memory fragmentation, making it harder
for the system to allocate new memory blocks efficiently.

o Array: Arrays are allocated in a single contiguous block, which avoids memory fragmentation
issues. However, resizing can be costly in terms of performance.

Summary of Comparison:

Feature Linked List Array

Dynamic, but has overhead for Fixed size or requires resizing, no pointer
Memory Usage
pointers overhead

Insertion/Deletion O(1) at head, O(n) at arbitrary

Memory Wastage None (allocated as needed) Can have wasted space (over-allocated)

Cache Locality Poor (non-contiguous memory) Excellent (contiguous memory)

Random Access O(n) (requires traversal) O(1) (direct indexing)

Resizing Dynamic (no need to resize) Needs reallocation and copying on resize

Memory Fragmentation Possible due to scattered allocations None (single contiguous block)

Q.2 Write an algorithm to merge two sorted linked lists into one sorted list without using any extra memory, i.e.,
without using an additional array or linked list.

Solution:

Algorithm:

1. Initialize a Dummy Node: Create a dummy node to simplify handling of edge cases (like
when one of the lists is empty).

2. Iterate through Both Lists:

o Use two pointers, one for each linked list (l1 and l2).

o Compare the values of the current nodes of the two lists.

o Append the node with the smaller value to the merged list.

o Move the pointer of the selected list (either l1 or l2) to the next node.

3. Attach Remaining Nodes: If one of the lists is fully traversed, append the remaining part
of the other list to the merged list.

4. Return the Merged List: Return the list starting from the next node of the dummy (since
the dummy node is just a placeholder).