DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Build a library management system that demonstrates practical use of hash tables for book lookup, BST for sorted catalogs, queues for waitlists, stacks for undo operations, and linked lists for borrow history.
Project Overview
This project shows how different data structures solve different problems within a single application. A library management system needs to:
- Look up books by ISBN instantly → Hash Table
- Browse books in sorted order (by title/author) → Binary Search Tree
- Manage waitlists for popular books → Queue
- Support undo/redo for librarian actions → Stack
- Track borrow history for each member → Linked List
Let's build each component and see why that specific data structure is the right choice.
Component 1: Hash Table for Book Lookup
When someone walks up with an ISBN, you need O(1) lookup. A hash table maps ISBN → book details:
Example
class BookRecord:
def __init__(self, isbn, title, author, copies_total, copies_available):
self.isbn = isbn
self.title = title
self.author = author
self.copies_total = copies_total
self.copies_available = copies_available
class BookCatalog:
def __init__(self):
self.books = {} # ISBN -> BookRecord
def add_book(self, isbn, title, author, copies=1):
if isbn in self.books:
self.books[isbn].copies_total += copies
self.books[isbn].copies_available += copies
else:
self.books[isbn] = BookRecord(isbn, title, author, copies, copies)
def lookup(self, isbn):
"""O(1) lookup by ISBN."""
return self.books.get(isbn)
def is_available(self, isbn):
book = self.books.get(isbn)
return book is not None and book.copies_available > 0
def checkout(self, isbn):
book = self.books.get(isbn)
if book and book.copies_available > 0:
book.copies_available -= 1
return True
return False
def return_book(self, isbn):
book = self.books.get(isbn)
if book and book.copies_available < book.copies_total:
book.copies_available += 1
return True
return False
Why hash table? Libraries have thousands of books. Searching by ISBN must be instant — O(1) average. No other data structure gives us this for key-value lookup.
Component 2: BST for Sorted Catalog Browsing
Users want to browse books alphabetically or find books in a title range. A BST gives us sorted order naturally:
Example
class BSTNode:
def __init__(self, title, isbn):
self.title = title
self.isbn = isbn
self.left = None
self.right = None
class SortedCatalog:
def __init__(self):
self.root = None
def insert(self, title, isbn):
self.root = self._insert(self.root, title, isbn)
def _insert(self, node, title, isbn):
if not node:
return BSTNode(title, isbn)
if title < node.title:
node.left = self._insert(node.left, title, isbn)
elif title > node.title:
node.right = self._insert(node.right, title, isbn)
return node
def browse_alphabetical(self):
"""In-order traversal gives sorted order."""
results = []
self._inorder(self.root, results)
return results
def _inorder(self, node, results):
if node:
self._inorder(node.left, results)
results.append((node.title, node.isbn))
self._inorder(node.right, results)
def find_range(self, start_title, end_title):
"""Find all books with titles in [start, end] alphabetically."""
results = []
self._range_search(self.root, start_title, end_title, results)
return results
def _range_search(self, node, start, end, results):
if not node:
return
if start < node.title:
self._range_search(node.left, start, end, results)
if start <= node.title <= end:
results.append((node.title, node.isbn))
if node.title < end:
self._range_search(node.right, start, end, results)
Why BST? We need sorted order AND dynamic insertions. A sorted array gives browsing but O(n) inserts. A BST gives O(log n) for both (when balanced).
Component 3: Queue for Book Waitlists
When all copies are checked out, members join a waitlist. First-come, first-served — this is exactly FIFO (queue):
Example
from collections import deque
class WaitlistManager:
def __init__(self):
self.waitlists = {} # ISBN -> deque of member IDs
def join_waitlist(self, isbn, member_id):
if isbn not in self.waitlists:
self.waitlists[isbn] = deque()
self.waitlists[isbn].append(member_id)
position = len(self.waitlists[isbn])
return position # "You are #3 in line"
def notify_next(self, isbn):
"""When a book is returned, notify the next person in line."""
if isbn in self.waitlists and self.waitlists[isbn]:
next_member = self.waitlists[isbn].popleft()
return next_member # Send notification
return None
def get_position(self, isbn, member_id):
if isbn not in self.waitlists:
return -1
try:
idx = list(self.waitlists[isbn]).index(member_id)
return idx + 1
except ValueError:
return -1
def leave_waitlist(self, isbn, member_id):
if isbn in self.waitlists:
self.waitlists[isbn] = deque(
m for m in self.waitlists[isbn] if m != member_id
)
Why queue? Fairness demands first-come-first-served. A queue guarantees O(1) enqueue and dequeue while maintaining insertion order.
Component 4: Stack for Undo/Redo
Librarians make mistakes — check out to wrong member, add wrong book, etc. An undo system uses a stack:
Example
class Action:
def __init__(self, action_type, data):
self.action_type = action_type # "checkout", "return", "add_book"
self.data = data # dict with relevant info
class UndoRedoManager:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
def perform_action(self, action):
"""Execute an action and push to undo stack."""
self.undo_stack.append(action)
self.redo_stack.clear() # New action invalidates redo history
return self._execute(action)
def undo(self):
"""Undo the last action."""
if not self.undo_stack:
return "Nothing to undo"
action = self.undo_stack.pop()
self.redo_stack.append(action)
return self._reverse(action)
def redo(self):
"""Redo the last undone action."""
if not self.redo_stack:
return "Nothing to redo"
action = self.redo_stack.pop()
self.undo_stack.append(action)
return self._execute(action)
def _execute(self, action):
if action.action_type == "checkout":
return f"Checked out {action.data['isbn']} to {action.data['member']}"
elif action.action_type == "return":
return f"Returned {action.data['isbn']} from {action.data['member']}"
def _reverse(self, action):
if action.action_type == "checkout":
return f"UNDO: Returned {action.data['isbn']} from {action.data['member']}"
elif action.action_type == "return":
return f"UNDO: Re-checked out {action.data['isbn']} to {action.data['member']}"
Why stack? Undo is always "reverse the most recent action" — that is LIFO. The stack naturally gives us the most recent action on top.
Component 5: Linked List for Borrow History
Each member has a chronological history of borrowed books. We frequently add to the front (newest first) and display recent history:
python example
class HistoryNode:
def __init__(self, isbn, title, borrow_date, return_date=None):
self.isbn = isbn
self.title = title
self.borrow_date = borrow_date
self.return_date = return_date
self.next = None
class BorrowHistory:
def __init__(self, member_id):
self.member_id = member_id
self.head = None # Most recent borrow
self.count = 0
def add_borrow(self, isbn, title, date):
"""Add new borrow record at the front (most recent first)."""
node = HistoryNode(isbn, title, date)
node.next = self.head
self.head = node
self.count += 1
def mark_returned(self, isbn, return_date):
"""Mark a book as returned."""
current = self.head
while current:
if current.isbn == isbn and current.return_date is None:
current.return_date = return_date
return True
current = current.next
return False
def get_recent(self, n=10):
"""Get the n most recent borrow records."""
records = []
current = self.head
while current and len(records) < n:
records.append({
'isbn': current.isbn,
'title': current.title,
'borrowed': current.borrow_date,
'returned': current.return_date
})
current = current.next
return records
def currently_borrowed(self):
"""List all books not yet returned."""
borrowed = []
current = self.head
while current:
if current.return_date is None:
borrowed.append((current.isbn, current.title))
current = current.next
return borrowedWhy linked list? History is append-heavy and traversal-based. We never need random access to "the 47th book borrowed." We always traverse from recent to old. Linked list gives O(1) prepend and natural sequential traversal.
Putting It All Together
Example
class LibrarySystem:
def __init__(self):
self.catalog = BookCatalog()
self.sorted_catalog = SortedCatalog()
self.waitlists = WaitlistManager()
self.undo_manager = UndoRedoManager()
self.member_history = {} # member_id -> BorrowHistory
def add_book(self, isbn, title, author, copies=1):
self.catalog.add_book(isbn, title, author, copies)
self.sorted_catalog.insert(title, isbn)
def checkout_book(self, isbn, member_id, date):
if self.catalog.checkout(isbn):
# Record history
if member_id not in self.member_history:
self.member_history[member_id] = BorrowHistory(member_id)
book = self.catalog.lookup(isbn)
self.member_history[member_id].add_borrow(isbn, book.title, date)
# Track for undo
action = Action("checkout", {"isbn": isbn, "member": member_id})
self.undo_manager.perform_action(action)
return True
else:
# Book not available — add to waitlist
position = self.waitlists.join_waitlist(isbn, member_id)
return f"Added to waitlist at position {position}"
Lessons Learned
This project demonstrates the right tool for the right job principle:
- Hash tables for key-based lookup
- BSTs for sorted access patterns
- Queues for fairness/ordering
- Stacks for reversal/undo
- Linked lists for sequential history
No single data structure does everything well. Good software engineering means choosing the right structure for each access pattern.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Library Management System Using DSA.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, projects, library, management
Related Data Structures & Algorithms Topics
Continue learning this concept
ProjectsAutocomplete System Using TrieBuild a real-time autocomplete system using a trie data structure with frequency ranking, prefix matching, and a complete Python implementation.ProjectsRoute Finder Using GraphsBuild a route-finding application using graph data structures, Dijkstra\ProjectsMini Search Engine ProjectBuild a mini search engine from scratch using an inverted index (hash map), TF-IDF scoring for relevance ranking, and a trie for autocomplete suggestions.ProjectsSocial Network Analysis Using GraphsModel social networks as graphs and implement BFS for degrees of separation, community detection, influence spread simulation, and simplified PageRank.Interview PreparationDSA Cheatsheet: Quick ReferenceComplete quick-reference cheatsheet covering all data structures with operations and complexities, algorithm complexities, and when-to-use guidelines.Interview PreparationEssential DSA Interview Questions25+ categorized DSA interview questions with approach hints covering arrays, strings, linked lists, trees, graphs, and dynamic programming.