Unit - 2
1-Arrays and its operations
-An array is a linear data structure that stores elements of the same
data type in contiguous memory locations. Each element in the array
is identified by an index or a key. The primary advantage of arrays is
their constant-time access to elements through indexing.
Operations on Arrays:
•Access (Read/Write):
•Description: Retrieve or modify the value of an element at a specific
index.
•Example: int value = myArray[2]; (Accessing the third element in the
array.)
•Insertion:
•Description: Add a new element at a specific index or at the end of
the array.
•Example: myArray[4] = 10; (Inserting the value 10 at the fifth index.)
•Deletion:
•Description: Remove an element from a specific index.
•Example: myArray[3] = 0; (Deleting the value at the fourth index by
assigning 0.)
•Search:
•Description: Find the index of a specific element in the array.
•Example: int index = findIndex(myArray, 8); (Searching for the index
of value 8.)
2-Linked list and its advantages & Disadvantage
-A linked list is a linear data structure where elements are stored in
nodes, and each node points to the next node in the sequence.
Unlike arrays, linked lists do not require contiguous memory
locations, allowing for dynamic memory allocation.
Advantages of Linked Lists:
•Dynamic Size:
•Linked lists can easily grow or shrink in size during runtime, as
memory allocation is dynamic.
•Ease of Insertion and Deletion:
•Inserting or deleting elements within a linked list is more efficient
compared to arrays, especially in the middle of the list.
•No Pre-allocation of Memory:
•Memory is allocated as needed, making linked lists more flexible in
managing memory.
•Efficient Memory Utilization:
•No need to predefine the size, leading to efficient memory usage.
Disadvantages of Linked Lists:
•Random Access is Inefficient:
•Accessing elements by index is less efficient compared to arrays
since you have to traverse the list from the beginning.
•Extra Memory for Pointers:
•Requires additional memory for storing pointers, increasing
overhead.
•Sequential Access:
•Accessing elements sequentially is efficient, but random access or
jumping to a specific element may involve traversing the list.
•Memory Overhead:
•Each node in a linked list carries additional overhead due to the
storage of the data and the pointer/reference to the next node.
•Cache Locality:
•Linked lists may not utilize the cache as effectively as arrays due to
scattered memory locations.
3-Doubly Linked List
-A Doubly Linked List (DLL) is a type of linked list in which each node
contains a data element and two pointers, one pointing to the next
node in the sequence (like in a singly linked list), and another
pointing to the previous node. This bidirectional linkage allows
traversal in both forward and backward directions. Here are the key
features of a doubly linked list:
•Node Structure:
•Each node in a doubly linked list contains:
•Data: The actual data stored in the node.
•Next: A pointer/reference to the next node in the sequence.
•Previous: A pointer/reference to the previous node.
•Head and Tail:
•The doubly linked list typically has a "head" pointer pointing to the
first node and a "tail" pointer pointing to the last node.
•Advantages:
•Bidirectional Traversal: Allows easy traversal in both forward and
backward directions.
•Efficient Insertions and Deletions: Inserting or deleting nodes at the
beginning, end, or in the middle is more efficient compared to a
singly linked list.
•Operations:
•The basic operations for a doubly linked list include insertion,
deletion, and traversal. These operations can be performed in both
forward and backward directions.
4-Priority Queues
-A Priority Queue is an abstract data type that operates similar to a
regular queue or stack but assigns a priority to each element. The
element with the highest priority is served before others with lower
priorities. Priority queues are commonly used in various computer
science applications, such as scheduling, task processing, and
algorithms like Dijkstra's shortest path algorithm.
Key Features of Priority Queues:
•Element Priority:
•Each element in the priority queue is associated with a priority
value.
•Elements with higher priority values are served before elements
with lower priority values.
•Data Structure:
•Priority queues can be implemented using various data structures
such as binary heaps, Fibonacci heaps, or balanced search trees.
•Operations:
•The primary operations include:
•Insertion (enqueue): Add an element to the priority queue.
•Deletion (dequeue): Remove and return the element with the
highest priority.
•Peek: View the element with the highest priority without removing
it.
•Applications:
•Priority queues are used in scenarios where tasks or elements need
to be processed based on their priorities. Examples include task
scheduling, Huffman coding, and graph algorithms like Dijkstra's
algorithm.
5-Two Dimensional Array and how it stored in memory
-A two-dimensional array is stored in memory as a contiguous block
of data. The arrangement of elements in memory depends on the
programming language and the storage order convention used,
which can be either row-major or column-major. Let's explore how a
two-dimensional array is typically stored in memory:
Row-Major Order (C/C++, Python, etc.):
In row-major order, the elements of a row are stored consecutively in
memory. The next row follows immediately after the previous one.
The formula to calculate the memory address of an element at row i
and column j in a row-major order is:
address
=
base_address
+
(
i
×
number_of_columns
+
j
)
×
size_of_element
\text{{address}} = \text{{base\_address}} + (\text{{i}} \times
\text{{number\_of\_columns}} + \text{{j}}) \times
\text{{size\_of\_element}}
address=base_address+(i×number_of_columns+j)×size_of_element
Column-Major Order (Fortran, MATLAB, etc.):
In column-major order, the elements of a column are stored
consecutively in memory. The next column follows immediately after
the previous one. The formula to calculate the memory address of an
element at row i and column j in a column-major order is:
address
=
base_address
+
(
j
×
number_of_rows
+
i
)
×
size_of_element
\text{{address}} = \text{{base\_address}} + (\text{{j}} \times
\text{{number\_of\_rows}} + \text{{i}}) \times
\text{{size\_of\_element}}
Address=base_address+(j×number_of_rows+i)×size_of_element
