Dynamic Arrays 1

• Dynamic Data Structures
• Static data structure


  An organization or collection of data in memory that is fixed in size
• Dynamic data structure


  A structure that can expand in size and contract as a program executes
• Static data structures are ideal for storing a fixed number of data items, but they lack the dynamic data structure's flexibility to consume additional memory if needed or free up memory when possible for improved efficiency
• Both static and dynamic data structures play a key role in programming languages like C, C++ and Java because they provide the programmer with the option to either focus more on performance in the former case or more on efficient memory consumption in the case of dynamic data structures
• Pointer


  A variable which stores the memory address of a data value
• Memory Allocation


  1. Allocate memory using malloc

  2. Cast the returned data type to the specific type

  3. Assign values to the allocated memory
• C does not have the capability to automatically free memory once it is unused. It has the function free to return the allocated memory space for a pointer variable
• Calloc

  Creates an array of elements of any type and initializes the array elements to zero
• The difference between malloc() and calloc() is that calloc() initiates the values to 0, while malloc() does not initialize any value
• Dangling pointer is a pointer that points to invalid data or to data which is not valid anymore
• Self-referential structure

  Contains a pointer member that points to a structure of the same structure type
• Linked list

  • A linear collection of self-referential structures, called nodes, connected by pointer links
  • Accessed via a pointer to the first node of the list
  • Subsequent nodes are accessed via the link pointer member stored in each node
  • Data is stored dynamically - each node is created as necessary
  • The link pointer in the last node is set to NULL to mark the end of the list
• Operations of Linked Lists

  • Traversing the list
  • Inserting to the list
  • Deleting in a list
• Before creating a linked list, always remember to create the structure first of your nodes
• Resizing a dynamic array is an expensive operation as it involves allocating new memory, copying the existing elements, and deallocating the old memory.
• The dynamic array is an array that can change its size at runtime.
• Dynamic arrays automatically resize themselves when the number of elements exceeds the current capacity, by doubling the size of the array.
• Dynamic arrays are implemented using pointers to the first element, which allows them to be resized dynamically as needed.
• The amortized time complexity of appending an element to a dynamic array is O(1) because most of the time, the resizing operation is infrequent.
• In C++, we use new operator to allocate memory for our data structure
• The dynamic array is an array that can change its size at runtime.
• When inserting or deleting elements from a dynamic array, the array may need to be reallocated with more or less space depending on the specific implementation.
• Realloc() returns the original address if the allocation request was successful; otherwise, it returns a null value.
• In C++, we use std::vector to implement dynamic arrays.
• Dynamic arrays have a fixed size at creation time but can be resized during runtime using realloc(). This function returns a new address with the requested number of bytes allocated from the heap.
• Dynamic arrays have two main advantages over fixed arrays: they do not require specifying their sizes when declared, and they allow resizing without losing data.
• Dynamic arrays are implemented using pointers to the first element, which allows them to be resized dynamically as needed.
• To implement a stack with a dynamic array, we need to keep track of two variables - top and max_size.
• When we append an element to the end of the array, we check if there's enough space left in the array (i.e., if tail_index + 1 == capacity)
• A doubly linked list has two links per node - one pointing forward (to the next node) and another link pointing backward (to the previous node). This makes traversal easier since we don't need to start from the beginning every time.
• In C++, we use vectors instead of dynamic arrays since they have built-in functions for resizing and handling memory allocation.
• We need to keep track of the allocated memory with a pointer called head_ptr
• std::vector has many useful functions such as push_back(), pop_back(), clear() etc.
• If we want to add more elements than what's currently available, we need to use realloc() to allocate more space on the heap.
• std::vector has several methods such as push_back(), pop_back(), insert(), erase(), clear(), capacity(), reserve(), max_size(), empty(), front(), back(), operator[], begin(), end().
• When inserting or deleting elements from a dynamic array, we need to shift all subsequent elements to make room for the new one.
• In C++, we use vectors instead of dynamic arrays because they have built-in functions for adding or removing elements from the vector without having to manually allocate/deallocate memory.
• If the reallocation fails (i.e., there's not enough free memory), then the pointer returned by realloc() will be NULL.
• C++ provides the vector class as a built-in container for storing collections of objects.