additional midterm flashcard 2
What is an interface in Java?
A collection of abstract methods and constants that establishes a set of methods that a class must implement
What are the key differences between interfaces and classes?
- Cannot instantiate an interface 2. No constructors 3. All methods are abstract 4. Only static and final fields allowed 5. Classes implement interfaces rather than extend them
What is an Abstract Data Type (ADT)?
A collection of data items together with the operations that can be performed on that data, specifying WHAT operations do but not HOW they do it
When should you use interfaces in Java?
- When you have multiple implementations for the same ADT 2. To expose simple public methods while hiding implementation details 3. To provide a template for classes that must be followed
What is abstraction in programming?
The separation of purpose (what something does) from implementation (how it does it), allowing users to use functionality without knowing internal details
What are generics in Java?
A feature that allows classes, interfaces, and methods to be written as templates that can work with any data type while maintaining type safety at compile time
Why can’t primitive types be used directly with generics?
Primitive types cannot be used directly in angle brackets (like ). Instead, wrapper classes must be used (like )
How do you make a class generic?
Add a type parameter in angle brackets after the class name (e.g., class Name) and use that parameter as a type within the class
What is a data structure?
A particular way of organizing data in a computer so that it can be used efficiently, with different structures suited to different applications
What are the key characteristics of an algorithm?
- Unambiguous description 2. Defined set of inputs and outputs 3. Guaranteed to terminate 4. Produces a defined result
What is a linked structure?
A collection of objects (nodes) storing data and links to other objects, where each node contains both data and references to other nodes
What are the advantages of arrays?
- Random quick access to elements 2. Groups like information together 3. Efficient direct access to elements
What are the disadvantages of arrays?
- Fixed size requiring recreation for resizing 2. Insertion/deletion requires shifting elements 3. Memory must be contiguous
What is the difference between == and .equals() for objects?
== compares if two references point to the same object in memory, while .equals() compares the actual content/values of the objects
What is a node in the context of linked structures?
An object in a linked structure that contains both data and references (links) to other nodes of the same type
What happens if you lose the first reference in a linked structure?
You lose access to the entire chain of nodes since there’s no way to reach them without the first reference
What are wrapper classes used for in Java?
To convert primitive data types into objects, allowing them to be used with generics and collections (e.g., Integer for int, Double for double)
What is the purpose of type parameters in generic classes?
To allow the class to work with different data types while maintaining type safety, using placeholders like or that are replaced with actual types when used
What is a Stack and what principle does it follow?
A Stack is a collection whose elements are added and removed from the same end (top). It follows LIFO (Last In, First Out) principle
What are the primary operations of a Stack ADT?
- push (add element to top) 2. pop (remove and return top element) 3. peek (view top without removing) 4. isEmpty (check if stack empty)
What is a Queue and what principle does it follow?
A Queue is a collection where elements are added at rear and removed from front. It follows FIFO (First In, First Out) principle
What are the primary operations of a Queue ADT?
- enqueue (add to rear) 2. dequeue (remove from front) 3. first (view front without removing) 4. isEmpty (check if queue empty)
What are the differences between array and linked implementations of a Stack?
Array implementation: Push O(n)* due to resizing, Pop O(1). Linked implementation: Both Push and Pop are O(1), but uses more memory for links
What are the key differences between ArrayQueue and LinkedQueue?
ArrayQueue: enqueue/dequeue O(n) due to shifting. LinkedQueue: both operations O(1). Array implementation uses less memory but has fixed size initially
What is a CircularArrayQueue and why use it?
A queue implementation using an array that wraps around to the beginning when reaching the end, making enqueue/dequeue operations more efficient (O(1)) by avoiding shifting
What is a Linked List and what are its key characteristics?
A data structure composed of nodes where each node contains data and reference(s) to other nodes. Can grow dynamically, efficient insertion/deletion, but sequential access
What are the three main types of Linked Lists?
- Singly Linked (one directional links) 2. Circular (last node links to first) 3. Doubly Linked (bidirectional links)
What are the advantages of Linked Lists over Arrays?
- Dynamic size (can grow as needed) 2. Efficient insertion/deletion 3. No need to shift elements 4. Memory allocation as needed
What are the disadvantages of Linked Lists?
- No random access (sequential access only) 2. Extra memory needed for storing references 3. Not cache-friendly due to non-contiguous memory
How does garbage collection work with Linked Lists in Java?
Java automatically reclaims memory from objects that have no references pointing to them. To ‘delete’ a node, simply remove all references to it
What is the time complexity for searching in a Linked List?
O(n) - must traverse the list sequentially from the beginning to find an element
What is the time complexity of adding to front vs end of Linked List?
Front: O(1) - just update head pointer. End: O(n) - must traverse entire list (unless tail pointer maintained)
What real-world examples use Stack data structure?
- Browser back button history 2. Undo operations in text editors 3. Expression evaluation 4. Function call stack in programming
What real-world examples use Queue data structure?
- Print queue for documents 2. Keyboard input buffer 3. Customer service systems 4. Process scheduling in operating systems
What is the purpose of a moving reference in Linked Lists?
A temporary reference that traverses the list to access or modify nodes without losing the reference to the start of the list
How does a CircularArrayQueue handle the ‘wraparound’ at array end?
Uses modulo arithmetic (%) with array length to cycle back to beginning when reaching end, making it appear circular
What is the main difference between Stack and Queue order?
Stack (LIFO) reverses the order of elements when they’re retrieved, while Queue (FIFO) maintains the original order
What happens during ArrayStack expansion?
When array is full, creates new array (typically 2x size), copies all elements to new array, updates reference to new array. O(n) operation
