Data Structures Flashcards
(24 cards)
What is a linked list?
a linear data structure where nodes are stored in memory non-contiguously and connected using pointers.
What are the main types of linked lists?
Singly Linked List – Each node has a next pointer to the next node.
Doubly Linked List – Each node has both next and prev pointers.
Circular Linked List – The last node connects back to the first node.
What are the advantages of a linked list over an array?
Dynamic size – Can grow or shrink without predefined limits.
Efficient Insertions/Deletions – No need to shift elements as in arrays.
Memory utilization – Uses exactly as much memory as needed.
What are the disadvantages of a linked list?
Extra memory usage – Requires extra space for pointers.
Slower access time – O(n) for lookup vs. O(1) for arrays with indexing
Poor cache locality – Due to non-contiguous storage.
What is the time complexity of common operations in a singly linked list?
Access/Search: O(n)
Insertion (at head): O(1)
Insertion (at tail or middle): O(n) (without tail pointer)
Deletion: O(n) ( O(1) if deleting from head)
How do you detect a cycle in a linked list?
Using Floyd’s Cycle Detection Algorithm (Tortoise and Hare), where:
A slow pointer moves one step at a time.
A fast pointer moves two steps at a time.
If they meet, a cycle exists.
How do you reverse a linked list?
Initialize three pointers: prev = NULL, curr = head, next = NULL.
Traverse the list, updating pointers (curr->next = prev).
Move prev and curr forward.
At the end, set head = prev.
How do you find the middle of a linked list efficiently?
A: Use the slow and fast pointer approach:
Slow moves one step at a time.
Fast moves two steps at a time.
When fast reaches the end, slow will be at the middle.
What is the difference between a stack and a linked list?
A stack is an abstract data structure (LIFO), while a linked list is a concrete data structure.
A stack can be implemented using a linked list.
A linked list allows insertions/deletions anywhere, while a stack operates only at one end.
How do you merge two sorted linked lists?
Use a recursive or iterative two-pointer approach:
Compare heads of both lists.
Append the smaller one to the result.
Move the pointer in the selected list forward.
Repeat until one list is exhausted.
How do you remove the nth node from the end of a linked list?
Use two pointers: first moves n steps ahead.
Move both pointers together until the first reaches the end.
Delete the node at the second pointer’s position.
What are real-world applications of linked lists?
Implementing stacks and queues
Undo/Redo functionality (Text editors, IDEs)
Memory management (Dynamic allocation in OS)
Graph adjacency lists
What is an array?
An array is a fixed-size, contiguous memory data structure that stores elements of the same data type and allows O(1) indexing.
What are the types of arrays?
One-dimensional (1D) array – A simple list of elements.
Multi-dimensional arrays – Includes 2D (matrices) and 3D arrays.
Dynamic arrays – Like ArrayList in Java or Vector in C++, which grow dynamically.
What are the time complexities of basic array operations?
Access (indexing): O(1)
Search (linear): O(n)
Search (binary, sorted array): O(log n)
Insertion (at end, if space available): O(1)
Insertion (at beginning/middle): O(n) (due to shifting)
Deletion: O(n) (due to shifting)
What are the advantages of arrays?
Fast indexing O(1)
Efficient use of memory (no extra pointers like linked lists)
Cache friendly due to contiguous memory allocation
What are the disadvantages of arrays?
Fixed size (except for dynamic arrays)
Insertion/Deletion is costly (O(n) due to shifting)
Memory wastage if allocated more space than required
What is a dynamic array? How does it work?
A dynamic array (like ArrayList in Java or vector in C++) automatically resizes:
When full, it doubles in size (O(n) for reallocation).
Uses amortized O(1) insertion.
How does binary search work on a sorted array?
Find the middle element.
If the target is smaller, search the left half.
If larger, search the right half.
Repeat until found or array is empty.
Time Complexity: O(log n)
How do you reverse an array in-place?
Use two pointers (one at the start, one at the end).
Swap elements.
Move pointers inward until they meet.
How do you find the largest and smallest element in an array?
Linear scan (O(n)): Iterate and track max and min.
Sorting approach (O(n log n)): Sort and take first/last elements
What are some common algorithms that use arrays?
Sorting: QuickSort, MergeSort, BubbleSort
Searching: Binary Search, Linear Search
Sliding Window: Finding subarrays, maximum sum problems
Two-pointer technique: Removing duplicates, pair sum problems
How do you check if an array contains duplicates?
Sorting + Checking Adjacent Elements (O(n log n))
HashSet (for constant lookups) (O(n) with extra space)
Brute force (nested loops) (O(n²), inefficient)
What are common applications of arrays?
Database indexing (fast retrieval)
Image processing (2D arrays as pixel grids)
Scheduling tasks
Mathematical computations (matrix operations)
