4 Dynamic Data Structures(Lists)

Data Structures  Arrays and Dynamic Arrays in C++

Introduction to Arrays

An array is a fundamental data structure in C++ used to store a collection of elements identified by index or key. Arrays are categorized into two main types: static and dynamic.

Static Arrays

Static arrays have a fixed size determined at the time of declaration. They are straightforward to use and provide fast access to elements by index, with a time complexity of O(1). However, static arrays have limitations as their size cannot be changed once declared, which can lead to either wasted memory or insufficient space.

Dynamic Arrays

Dynamic arrays can change size during runtime. They start with an initial capacity and resize, typically by doubling, when they reach capacity. This resizing process involves creating a new array and copying all elements, which can be time consuming with a time complexity of O(N). Despite the resizing cost, dynamic arrays offer flexibility in terms of storage capacity.

Types of Dynamic Arrays

• Vectors
  Vectors are dynamic arrays that automatically resize themselves as elements are added. They provide O(1) amortized time complexity for insertions, though frequent resizing and element copying can be costly. Inserting elements at the front of a vector requires shifting all existing elements, resulting in a time complexity of O(N).
• Growable Arrays
  Growable arrays are optimized dynamic arrays designed to maintain constant time complexity for average case insertions due to efficient resizing strategies. However, like vectors, inserting elements at the front still incurs O(N) complexity due to the need to shift elements.

Use Cases

1. Stack
   A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. It supports push and pop operations with O(1) time complexity, making it efficient for scenarios where elements need to be accessed in reverse order of their insertion.
2. Queue
   A queue is a linear data structure that follows the First In, First Out (FIFO) principle. It supports enqueue and dequeue operations with O(1) time complexity, suitable for scenarios where elements are processed in the order they are added.
3. Deque (DoubleEnded Queue)
   A deque is a data structure that allows insertion and removal of elements from both ends with O(1) time complexity for these operations. It combines the features of both stacks and queues, providing flexibility in element management.

Linked List Implementation

The `MyLinkedList` class implements a singly linked list, a data structure consisting of nodes where each node points to the next. This class supports operations such as retrieving a value by index, adding nodes at the head, tail, or a specific index, and deleting nodes by index.

Key Features of MyLinkedList:

Get Value by Index:
Retrieves the value of the node at a specified index. If the index is out of bounds, it returns an error indicator.
Add at Head:
Adds a new node with a specified value at the beginning of the list. This operation updates the head pointer to the new node.
Add at Tail:
Adds a new node with a specified value at the end of the list. If the list is empty, it adds the node at the head.
Add at Index:
Adds a new node with a specified value at a specific index. If the index is out of bounds, no action is taken.
Delete at Index:
Deletes the node at a specified index. If the index is out of bounds, no action is taken.

Key Points to Remember:
Linked List Basics: A linked list is a sequence of nodes where each node points to the next node. The head is the first node in the list.
Operations: Adding at the head updates the head pointer to the new node. Adding at the tail involves finding the last node and updating its next pointer. Adding at an index involves updating pointers to insert the new node at the correct position. Deleting at an index involves updating pointers to remove the node and free the memory.
Edge Cases: Always check for out of bounds conditions, especially when getting or deleting nodes. When adding at the tail, ensure the list is not empty before iterating through it.

This course provides a comprehensive overview of arrays and dynamic arrays in C++, covering their types, use cases, and operations, including a detailed explanation of linked list implementation and its key functionalities.