CP25C01 Advanced Data Structures and Algorithms
Linear data structures, like arrays and linked lists, organize data sequentially and are
memory-efficient due to their contiguous or sequential storage, though arrays have fixed
sizes while linked lists use node-based allocation. Memory optimization in linear data
structures is achieved through efficient use of space via contiguous allocation (arrays)
or dynamic node-based allocation (linked lists), careful size management, and selecting
the right structure for the data's growth pattern to avoid unnecessary memory overhead
or fragmentation.
How Linear Data Structures Optimize Memory
Contiguous Memory (Arrays):
Arrays allocate a single, fixed-size block of memory, which is very efficient for
accessing elements directly by index. However, this can lead to wasted space if the
array is not fully utilized, and it doesn't accommodate data that grows beyond its initial
size.
Dynamic Allocation (Linked Lists):
Linked lists allocate memory for each node individually, allowing them to grow and
shrink dynamically as data is added or removed. This makes them more flexible for
unpredictable data sizes, but each node requires extra memory for pointers to the next
element, creating some overhead.
Memory Optimization Strategies
Choose the Right Structure:
Select an array for static data sizes where memory efficiency is paramount, and a
linked list for dynamically changing data where flexibility is more important than
predictable performance.
Efficient Sizing (for Arrays):
Pre-allocate arrays with a size that is neither too small (causing frequent reallocations)
nor too large (wasting memory).
Avoid Memory Leaks:
Ensure that any dynamic memory allocated for nodes in a linked list is properly
deallocated when it's no longer needed.
Data Structure Choice based on Access Patterns:
For tasks requiring sequential access, linear structures offer efficient memory use. For
complex, non-sequential relationships, non-linear structures may be more
appropriate.
Examples
Arrays: Good for fixed-size lists where direct access is frequent.
Linked Lists: Ideal for situations where data size is unknown and insertions/deletions
are frequent.
Stacks and Queues: Often built upon arrays or linked lists, they manage memory
according to their underlying implementation.
A sparse array or sparse matrix is an array in which most of the elements
are zero.
Characteristics of Sparse array:
The sparse array is an array in which most of the elements have the same
value(the default value is zero or null).
Sparse matrices are those array that has the majority of their elements
equal to zero.
A sparse array is an array in which elements do not have contiguous
indexes starting at zero.
Sparse arrays are used over arrays when there are lesser non-zero
elements. Sparse arrays require lesser memory to store the elements and
the computation time can be saved.
Why sparse array is required over simple arrays to store the
elements:
Storage: When there is the maximum number of zero elements and the
minimum number of non-zero elements then we use a sparse array over a
simple array as it requires less memory to store the elements. In the
sparse array, we only store the non-zero elements.
Computation Time: In the sparse array we only store non-zero elements
and hence, traversing only non-zero elements takes less computation
time.
Representation of Sparse Array:
Sparse arrays can be represented in two ways:
Array Representation
Linked List Representation
1. Array Representation:
To represent a sparse array 2-D array is used with three rows namely: Row,
Column, and Value.
Row: Index of the row where non-zero elements are present.
Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.
2. Linked List Representation:
To represent a sparse array using linked lists, each node has four fields
namely: Row, Column, Value, and Next node.
Row: Index of the row where non-zero elements are present.
Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.
Next node: It stores the address of the next node.
Implementation of array representation of the sparse array:
A Dynamic array (vector in C++, ArrayList in Java) automatically grows when
we try to make an insertion and there is no more space left for the new item.
Usually the area doubles in size. A simple dynamic array can be constructed
by allocating an array of fixed-size, typically larger than the number of
elements immediately required. The elements of the dynamic array are
stored contiguously at the start of the underlying array, and the remaining
positions towards the end of the underlying array are reserved, or unused.
Elements can be added at the end of a dynamic array in constant time by
using the reserved space until this space is completely consumed. When all
space is consumed, and an additional element is to be added, the underlying
fixed-sized array needs to be increased in size. Typically resizing is
expensive because you have to allocate a bigger array and copy over all of
the elements from the array you have overgrow before we can finally append
our item.
Approach: When we enter an element in array but array is full then you
create a function, this function creates a new array double size or as you
wish and copy all element from the previous array to a new array and return
this new array. Also, we can reduce the size of the array. and add an
element at a given position, remove the element at the end default and at the
position also.
Key Features of Dynamic Array
Add Element: Add element at the end if the array size is not enough then
extend the size of the array and add an element at the end of the original
array as well as given index. Doing all that copying takes O(n) time, where n
is the number of elements in our array. That's an expensive cost for an
append. In a fixed-length array, appends only take O(1) time. But appends
take O(n) time only when we insert into a full array. And that is pretty rare,
especially if we double the size of the array every time we run out of space.
So in most cases appending is still O(1) time, and sometimes it's O(n) time.
In dynamic array you can create fixed-size array when required added some
more element in array then use this approach:
Delete Element: Delete an
element from array, default remove() method delete an element from end,
simply store zero at last index and you also delete element at specific index
by calling removeAt(i) method where i is index. removeAt(i) method shift all
right element in the left side from the given index. Resize of Array
Size: When the array has null/zero data (aside from an element added by
you) at the right side of the array, meaning it has unused memory, the
method shrinkSize() can free up the extra memory. When all space is
consumed, and an additional element is to be added, then the underlying
fixed-size array needs to increase in size. Typically resizing is expensive
because you have to allocate a bigger array and copy over all of the
elements from the array you have outgrown before we can finally append
item
