comp 2503 midterm Flashcards
What is computational complexity?
The amount of resources (time and space) required by an algorithm to solve a problem as a function of input size
What is Big-O notation used for?
To describe the upper bound or worst-case growth rate of an algorithm’s resource usage
What is the difference between LIFO and FIFO?
LIFO (Last In First Out) is used by stacks where the last element added is the first removed. FIFO (First In First Out) is used by queues where the first element added is the first removed
What are the main operations of a Stack?
push (add to top), pop (remove from top), peek (view top without removing), isEmpty
What are the main operations of a Queue?
enqueue (add to rear), dequeue (remove from front), peek (view front without removing), isEmpty
What makes Binary Search more efficient than Linear Search?
Binary Search divides the search space in half each time (O(log n)), while Linear Search checks each element sequentially (O(n))
What is the purpose of generics in Java?
To enable classes to work with different data types while maintaining type safety at compile time
What is the Comparable interface used for?
To define a natural ordering for a class by implementing the compareTo method
What is the Comparator interface used for?
To define multiple different ways to compare objects of a class without modifying the class itself
What are the key differences between arrays and linked lists?
Arrays have fixed size and continuous memory with direct access, while linked lists have dynamic size, scattered memory, and sequential access
What is the time complexity of adding to the front of an array vs. linked list?
Array: O(n) due to shifting elements, Linked List: O(1) by changing the head pointer
What is the time complexity of accessing an element by index in array vs. linked list?
Array: O(1) direct access, Linked List: O(n) must traverse from start
What are traversal pointers in linked lists used for?
To move through the list one node at a time, often used to search, modify, or perform operations on nodes
What is the difference between Singly and Doubly Linked Lists?
Singly Linked Lists have nodes with one pointer to the next node, Doubly Linked Lists have nodes with pointers to both next and previous nodes
Why use a Doubly Linked List over a Singly Linked List?
Doubly Linked Lists allow backward traversal and easier deletion of nodes, but use more memory per node
What is the advantage of implementing a Stack with a linked list vs. array?
Linked list implementation can grow dynamically without needing to resize, while array implementation may need to resize
What problem can be solved using two stacks?
Evaluating arithmetic expressions, implementing undo/redo functionality, or validating matching parentheses
What is the key difference in memory usage between arrays and linked lists?
Arrays use contiguous memory blocks and have memory overhead for resizing, linked lists use scattered memory with overhead for node pointers
How does Java Collections sort method work with custom objects?
Objects must either implement Comparable interface or a separate Comparator must be provided
What is standard input/output in Java?
System.in for input stream (keyboard by default) and System.out for output stream (console by default)
In what scenarios would you choose an array over a linked list?
When you need constant-time access to elements, fixed size is acceptable, and frequent insertion/deletion at arbitrary positions isn’t needed
What is a moving reference in linked list traversal?
A temporary pointer that moves through the list to access or modify nodes without losing the reference to the head of the list
How does a circular array implementation of a queue work?
Uses modulo arithmetic to wrap around array indices, making efficient use of space by reusing empty positions at the start
What are the advantages of implementing a queue using a linked list?
No size limitation, efficient enqueue and dequeue operations (O(1)), no need to shift elements
How do you handle edge cases in linked list operations?
Check for null pointers, empty lists, single-element lists, and maintain proper links when adding/removing at start/end of list
