pROG Flashcards
What does a pointer store?
Address of a variable
Which operator is used to access the value stored at the memory address held by a pointer?
*
What is the correct way to declare a pointer to an integer?
int pointer;
Which keyword is used to free dynamically allocated memory?
delete
Which of the following is a correct way to declare an array of 10 integers?
int arr[10];
Are dynamic data structures that provide flexibility and efficient operations compared to static arrays
Linked List
Check if the stack is empty.
IsEmpty
A pointer can point to any data type.
True
An array in C++ can store different types of data in the same array.
FALSE
When dynamically allocating an array, you must free the memory using delete[].
True
Is used to retrieve the address of a variable.
The address-of operator (&)
Which of the following is the correct way to define a structure?
struct myStruct{ int x; float y; };
Points to the next node in the list
Next Pointer
Visiting each node in the linked list, usually to read or process the data stored in each node.
Traversal
Remove the element from the front of the queue.
Dequeue
Finding a node in the linked list that contains a specific value.
Search
Enhance traversal capabilities, allowing for easy movement in both directions.
Doubly Linked List
The value held by the node.
Data
Adding a new node to the linked list. This can be done at various positions:
Insertion
Add an element to the top of the stack.
Push
Points to the previous node in the list.
Previous Pointer
Return the front element without removing it.
Peek
A pointer/reference to the first node in the list.
Head
Return the top element without removing it.
Peek
Linked lists can grow or shrink as needed, unlike arrays which have a fixed size.
Dynamic Size
Add an element to the end of the queue.
Enqueue
Remove the element from the top of the stack.
Pop
The basic unit of a linked list that contains data and a pointer to the next node.
Node
A pointer/reference to the last node in the list (optional).
Tail
Removing a node from the linked list. This can involve:
Deletion
Basic Operations on Data Structures ARAU
Adding Data: (Create | Insert).
Removing Data:(Delete).
Accessing Data:(Search | Read).
Updating Data: (Update).
Like a row of boxes where each box has a number.
-A simple list where each item is stored in a specific order
ARRAYS
Like a chain of linked rings, where each ring points to the next one.
- A list where each item points to the next one in line.
LINKED LISTS
Like a stack of plates where you add and remove from the top.
-A collection where the last item added is the first one to be removed (Last In, First Out - LIFO).
STACKS
Like a line at a checkout where the first person in line is the first one served.
-A collection where the first item added is the first one to be removed (First In, First Out - FIFO).
QUEUES
Like an upside-down family tree showing relationships between items.
-A structure that resembles an upside-down tree, with a root and branches showing how items are related.
TREES
Like a map showing various points (cities) and connections (roads) between them.
- A network of points connected by lines, showing how items are linked.
GRAPHS
Like a collection of unique items, no duplicates allowed.
-A collection of unique items with no duplicates.
SETS
Like a real-world dictionary where you look up words (keys) to find their definitions (values).
-A collection of key-value pairs where each key is unique and maps to a specific value.
MAPS
is a variable that stores the memory address of another variable. Hold the location where data is stored in memory.
-Variables that store memory addresses, allowing for efficient data manipulation and memory management.
POINTER
allows programs to request memory at runtime, rather than at compile time. This is useful when the amount of memory needed isn’t known beforehand.
DYNAMIC MEMORY ALLOCATION
Techniques (new and delete) to allocate and
deallocate memory at runtime, providing flexibility in handling data structures whose size isn’t known at compile time.
DYNAMIC MEMORY ALLOCATION
Collection of elements of the same type stored in contiguous memory locations. Arrays allow you to manage multiple variables using a single name.
ARRAY
User-defined data types that group different types of variables,
allowing for the representation of complex data entities.
STRUCTURE
data structure that consists of a sequence of elements, where each element points to the next element in the sequence. Unlike arrays, linked lists do not require contiguous memory locations, allowing for efficient memory usage and dynamic sizing.
LINKED LIST
Are dynamic data structures that provide flexibility and efficient operations compared to static arrays.
LINKED LIST
The basic unit of a linked list that contains data and a pointer to the next node.
NODE
A pointer/reference to the first node in the list.
HEAD
A pointer/reference to the last node in the list (optional).
TAIL
Adding a new node to the linked list.
INSERTION
The new node becomes the head of the list.
At the beginning
The new node is added after the last node.
At the end
The new node is inserted between two existing nodes.
At a specific position
Removing a node from the linked list.
DELETION
The head of the list is removed, and the next node
becomes the new head.
Deleting the first node
The last node is removed, and the second-to-last
node’s next pointer is set to null.
Deleting the last node:
A node is removed based on its value or position,
updating the pointers of adjacent nodes accordingly.
Deleting a specific node
Visiting each node in the linked list, usually to read or process the data stored in each node. This is typically done starting from the head and moving through each node using the next pointers until the end of the list is reached.
TRAVERSAL
Finding a node in the linked list that contains a specific value. This
operation involves traversing the list and checking each node’s value until the desired value is found or the end of the list is reached.
SEARCH
Add an element to the top of the stack.
PUSH
Remove the element from the top of the stack.
POP
Return the top element without removing it.
PEEK
Check if the stack is empty.
IsEmpty
Each node contains data and a pointer to the next node.
NODE STRUCTURE
Contains a private pointer top and methods for stack operations.
STACK CLASS
Allow you to view the top element and check if the stack is empty.
Peek and isEmpty
Add an element to the end of the queue.
ENQUEUE
Remove the element from the front of the queue.
Dequeue
Return the front element without removing it.
PEEK
Contains two pointers (front and rear) to facilitate efficient insertion and deletion.
Queue Class
process of determining the computational resources required byCan algorithm, focusing primarily on its time complexity and space complexity.
Algorithm Analysis
is crucial for evaluating algorithm efficiency, helping choose the best solution for a problem.
Algorithm Analysis
measures the amount of time an algorithm takes to complete as a function of the length of the input.
-Understanding time complexity allows us to predict the performance of an algorithm.
TIME COMPLEXITY
measures the total amount of memory space required
by the algorithm, including both the input and auxiliary space.
- space complexity helps developers understand the resource requirements of an algorithm, which is essential in environments with limited memory.
SPACE COMPLEXITY
describes the upper bound of an algorithm’s time or space complexity. It provides a high-level understanding of the efficiency of an algorithm without getting bogged down in implementation details.
Big O notation
The algorithm takes the same amount of time regardless of input size.
O(1): Constant time
The algorithm’s run time increases linearly with the input size.
O(n): Linear time
The run time grows proportionally to the square of the input size.
O(n^2): Quadratic time
The algorithm reduces the problem size in each step.
O(log n): Logarithmic time
To analyze an algorithm: IDU
- Identify the input size.
- Determine the operations performed by the algorithm.
- Use Big O notation to express the time and space complexities.
Each node points to the next node.
Singly Linked List
Each node points to both the next and previous nodes.
Doubly Linked List
The last node points back to the first node.
Circular Linked List
Advantages
● Dynamic Size: Linked lists can grow or shrink as needed, unlike arrays which have a fixed size.
● Efficient Insertions/Deletions: Adding or removing elements is easier and more efficient, especially at the beginning or middle of the list.
Disadvantages
● No Random Access: Unlike arrays, linked lists do not allow direct access to
elements; they must be accessed sequentially.
● Extra Memory Overhead: Each node requires additional memory for storing pointers.
enhance traversal capabilities, allowing for easy movement in both directions.
Doubly linked lists
The value held by the node.
DATA
Points to the next node in the list.
Next Pointer
Points to the previous node in the list.
Previous Pointer
