Data Structures in Code

The instructor is ready

Data Structures in Code

Interactive digital-human course

Data Structures in Code

Learn to organize code efficiently using key data structures like arrays, lists, stacks, and queues for clearer, more effective programming.

My workspace34 minFree to watch

What you’ll learn

  1. 01Data Structures: Organizing Information in CodeWelcome to this course on data structures. Today we're going to build a clear, language-neutral understanding of how to organize information in code. We'll focus on four key models: collections, stacks, queues, and trees. The reason this matters is that the structure you choose directly affects the correctness, clarity, and real-world performance of your program. As we learn, we'll use conceptual models, simple pseudocode, and everyday analogies, so you can understand the behavior without getting lost in language-specific syntax. By the end, you'll be able to recognize these structures, explain how they behave, and reason about their trade-offs. Let's get started by defining exactly what we mean by a data structure.Data Structures: Organizing Information in Codestackoverflow.comhyperskill.orgcs.stackexchange.com+21 min
  2. 02What Is a Data Structure?Now that we have a sense of where we are, let's define exactly what a data structure is. Imagine a toolbox. Inside, you have a hammer, a screwdriver, and a wrench. Each tool is designed for a specific job and organizes your approach to fixing something. A data structure works the same way. It is a tool that organizes and stores data in your code so you can access and change it efficiently. To truly understand this, we need to separate two ideas: the 'what' and the 'how'. The 'what' is called an Abstract Data Type, or ADT. It is like a contract that defines the expected behavior and operations, such as insert, delete, or search, but it hides the messy internal details. The 'how' is the actual data structure, the concrete implementation that makes those promised behaviors work. Think of a car. You have a steering wheel, an accelerator, and brakes. That interface is the ADT. The engine, the transmission, and the wheels working together under the hood are the data structure. In this course, we will focus on this language-neutral way of thinking, describing behavior and constraints with simple pseudocode instead of locking ourselves into a specific programming language. Take a moment to check your own understanding. Can you name the five core operations common to most data structures? They are insert, delete, search, traverse, and update. Next, we will explore the important distinction between the ADT and the data structure in more detail.What Is a Data Structure?stackoverflow.comhyperskill.orgcs.stackexchange.com+22 min
  3. 03The ADT vs. Data Structure DistinctionNow let's clarify a key distinction that will frame everything we build: the difference between an abstract data type and a data structure. Think of an abstract data type, or ADT, as a contract. It defines *what* operations are allowed, like push and pop, but it says nothing about *how* those operations actually work inside. A data structure, on the other hand, is the concrete implementation that fulfills that contract. For example, a Stack is an ADT—it promises you can add and remove items from the top. An array-based stack is a data structure that uses an array to make that promise a reality. This separation is powerful. It lets us reason about the behavior of a stack independently from the performance of its underlying array. One ADT can have many implementations, each with different trade-offs in speed or memory. So, when you design software, you first choose the ADT that fits your problem, and then you select the data structure that optimizes your specific needs. Up next, we'll explore the two fundamental layouts for linear collections.The ADT vs. Data Structure Distinctionstackoverflow.comhyperskill.orgcs.stackexchange.com+22 min
  4. 04The Linear Collections: Two Fundamental LayoutsNow let's organize our mental model around two fundamental layouts: the array and the linked list. Think of an array like a row of numbered lockers, all built together in one solid block. If you want locker number five, you walk straight to it. That is why arrays give us constant-time access by index. The downside is that inserting a new locker in the middle forces you to shift every locker after it down the line. A linked list works differently. Picture a treasure hunt where each clue is a node that holds a piece of data and a pointer to the next clue. The nodes can be scattered anywhere, and the only way to reach the fifth clue is to follow the chain from the start. That means index-based access takes linear time. But once you are standing at a node with a pointer in hand, inserting or deleting a new clue is a constant-time pointer update. No shifting required. So, the core trade-off is this: arrays give you instant jump-to-any-element, while linked lists give you instant insert-and-delete, but only when you already hold a pointer to that exact spot. Next, we will explore why, in practice, arrays usually win the race.The Linear Collections: Two Fundamental Layoutsdsa.handbook.academyspacecomplexity.aigeeksforgeeks.org+22 min
  5. 05Why Arrays Usually Win in PracticeNow, let's talk about why arrays usually win in practice, and the answer is a hardware secret that Big-O notation hides. Performance isn't just about counting operations. It's about how the CPU actually talks to memory. When you access one element in an array, the CPU doesn't just fetch that one value. It loads an entire cache line of adjacent elements, typically sixty-four bytes at a time. So, for the price of one memory access, you get the next fifteen or so elements almost for free. The hardware prefetcher then detects your sequential stride and starts loading future cache lines before you even ask for them. A linked list is a completely different story. Its nodes are scattered across the heap. Each node points to a random memory address. To reach the next node, you must chase that pointer. This creates a serial chain of load requests, and the prefetcher is helpless. Every single pointer chase risks a full hundred-nanosecond stall to main memory. And here's the crucial point about linked list insertion. The O of one complexity is only true if you already hold a pointer to the insertion point. To find that spot, you usually have to traverse from the head, which is O of n with a slow pointer chase. This is exactly why dynamic arrays, like Python's list or Java's ArrayList, are the default collection. The search for the right position, thanks to the cache, completely dominates the cost. Even when an array has to shift elements, that bulk memory move is incredibly fast. Next, we'll explore the specific scenarios where linked lists truly shine and are the right tool for the job.Why Arrays Usually Win in Practicedsa.handbook.academyspacecomplexity.aigeeksforgeeks.org+22 min
  6. 06When Linked Lists Are the Right ToolNow let's talk about when linked lists are actually the right tool. The rule is simple: a linked list wins when you already hold a pointer to the node you need to change. If you have that pointer, the mutation is truly constant time. No searching, no shifting. The classic example is the LRU cache. A hash map gives you constant-time access to any node. Then a doubly linked list lets you unlink that node and reinsert it at the head in constant time, because the node itself knows its own previous and next neighbors. Evicting the least recently used item is also constant time, just remove the tail. Linked lists also win for constant-time range splicing, where you move an entire section of nodes between lists without copying a single element. And they give you iterator stability: inserting or deleting elsewhere never invalidates pointers you are holding. One important note: production FIFO queues almost always use circular buffers, not linked lists. The textbook teaches the linked queue, but real systems prefer the cache-friendly array approach. So, remember the key question: do you already have the node in hand? If yes, the linked list shines. If not, search dominates and the array usually wins. Next, we’ll look at stacks: the last-in, first-out data structure.When Linked Lists Are the Right Tooldsa.handbook.academyspacecomplexity.aigeeksforgeeks.org+22 min
  7. 07Stacks: Last-In, First-Out (LIFO)Now let's explore a structure called a stack. A stack follows a simple rule: last in, first out. Think of a stack of plates in a cafeteria. You can only take the plate from the top, and any new plate you add goes right on top as well. The most recently added item is always the one you remove first. In code, we call the add operation a push, and the remove operation a pop. You can also peek at the top item without removing it. The key constraint is that only the top is accessible. This might sound limiting, but that limitation actually guarantees very predictable behavior. And because every core operation runs in constant time, it's extremely fast. You see stacks in undo and redo features, where the most recent action is reversed first. Your program's function call stack uses the same principle to return from the deepest call to the previous one. Stacks also power expression evaluation and backtracking algorithms. So when you need to access the newest item first, a stack is the right tool. Next, we'll compare this with its sibling structure: queues, which follow a first-in, first-out rule.Stacks: Last-In, First-Out (LIFO)geeksforgeeks.orgthelinuxcode.comcodeintuition.io+21 min
  8. 08Queues: First-In, First-Out (FIFO)Now let's shift our focus to queues, which follow a different rule: first in, first out, or FIFO. Think of a ticket line. The person who has been waiting the longest is served first; newcomers join at the back. A queue works exactly the same way. The core operations are enqueue, which adds an element to the rear, and dequeue, which removes an element from the front. You can also peek at the front element without removing it. Because insertion happens at one end and removal at the other, queues naturally preserve fairness and order. This makes them perfect for task scheduling, processing requests in the order they arrive, or print spooling. A common optimization is the circular queue, which uses a fixed-size array to achieve constant-time enqueue and dequeue without shifting elements. So, ask yourself: in your programs, do you need to process items in the exact order they arrived? If so, a queue is your tool. Next, we’ll put these two structures side by side in a decision framework.Queues: First-In, First-Out (FIFO)geeksforgeeks.orgthelinuxcode.comcodeintuition.io+22 min
  9. 09Stacks vs. Queues: The Decision FrameworkNow we have a decision framework for stacks and queues. The core question is straightforward: do you need to favor the newest item or the oldest item? If your logic says the most recent thing is the most relevant, reach for a stack. That gives you last-in-first-out behavior, perfect for undo systems, backtracking, or depth-first search. If your logic says fairness or arrival order matters, reach for a queue. That gives you first-in-first-out behavior, ideal for task scheduling, request buffers, or breadth-first search. Both are restricted-access structures. The constraint is not a limitation; it is a behavioral guarantee. And here is a powerful insight: swap a stack for a queue in a breadth-first search, and you get depth-first search. The structure dictates the algorithm. Let’s move on and look at pseudocode conventions and common patterns.Stacks vs. Queues: The Decision Frameworkgeeksforgeeks.orgthelinuxcode.comcodeintuition.io+21 min
  10. 10Pseudocode Conventions and Common PatternsNow let's talk about how we'll write these data structures during the course. We'll use a consistent, language-neutral pseudocode so you can focus on the ideas, not the syntax of a specific language. Think of it as a shared vocabulary. For a stack, the pattern is always stack.push to add an item, item equals stack.pop to remove the top item, and item equals stack.peek to look at the top without removing it. For a queue, we use queue.enqueue to add an item, item equals queue.dequeue to remove the front item, and item equals queue.front to see what's at the front. These simple patterns are the foundation for implementing stacks and queues in any language you choose. Up next, we'll step off the line and explore hierarchical data with trees.Pseudocode Conventions and Common Patternsgeeksforgeeks.orgthelinuxcode.comcodeintuition.io+21 min
  11. 11Stepping Off the Line: Introducing Hierarchical DataSo far our data structures have been linear, like a single-file line. But many relationships aren't flat sequences. Think about a family tree or a computer's file system. These show parent and child connections, not just a next-in-line order. We call this a hierarchical model. In computer science, a tree is a collection of nodes connected by edges. It has a single starting point called the root, and importantly, there are no cycles, meaning you can't loop back to a node. Let's define some key terms. The root is the topmost node. A leaf is a node with no children. A parent has outgoing edges to its children, who share the same parent as siblings. The depth of a node is how many edges from the root, and the height of the tree is the longest path from root to leaf. A powerful property to remember is that any node and its descendants form a subtree, which is itself a valid tree. This self-similarity makes recursion a natural fit for tree operations. Next, we'll examine the most common type, the Binary Tree, as our fundamental building block.Stepping Off the Line: Introducing Hierarchical Data2 min
  12. 12Binary Trees: The Fundamental Building BlockNow, let's look at the binary tree, which is a fundamental building block for organizing information. A binary tree is simple: each node has at most two children, a left child and a right child. You see this structure everywhere, in file systems, in organization charts, and even in the browser's Document Object Model, the DOM. When we need to visit every node in a binary tree, the order of our visit is determined by the data structure we choose. If we want to explore a deep branch all the way to its end first, we use a stack. This is called depth-first search, or DFS, and the stack's last-in, first-out behavior makes it possible. If we want to explore level by level, moving across the tree before going deeper, we use a queue. This is breadth-first search, or BFS, and the queue's first-in, first-out rule guarantees that we finish one level before starting the next. So, the traversal strategy defines the tool: a stack for depth-first, and a queue for breadth-first. Next, we will build on this idea with the binary search tree, organized for fast lookup.Binary Trees: The Fundamental Building Blockgeeksforgeeks.orgthelinuxcode.comcodeintuition.io+22 min
  13. 13Binary Search Trees: Organized for Fast LookupNow let's look at a structure that takes this idea even further: the binary search tree. Imagine you are looking for a word in a dictionary. You wouldn't start at page one and scan every entry. You'd open the book near the middle, check if your word comes before or after that page, and then repeat the process on just the half that remains. This is exactly how a binary search tree works. The entire tree is organized around one simple property, the BST property. For any node, every value stored in its left subtree is smaller, and every value stored in its right subtree is larger. Because of this rule, each comparison you make lets you throw away half of the remaining possibilities. This is what enables fast search, insertion, and even deletion. It mirrors the logic of binary search on a sorted array, but with a crucial difference. A sorted array is great for searching, but inserting a new item in the middle is slow because you have to shift everything over. A linked list inserts quickly, but searching is slow because you have to scan from the beginning. A binary search tree combines the best of both worlds. In a balanced tree, you get efficient, logarithmic time search, just like the sorted array, and efficient insertion, just like the linked list. When the tree is balanced, we say the operations are O of log n. With each comparison, you cut the search space in half. But here is the critical catch. The shape of the tree depends entirely on the order in which you insert the data. We'll explore that danger next, when we look at the hidden danger of degenerate trees.Binary Search Trees: Organized for Fast Lookupalgs4.cs.princeton.eduen.wikipedia.orgcs.odu.edu+22 min
  14. 14The Hidden Danger of Degenerate TreesLet's look at a hidden danger with basic binary search trees: what happens when we insert data that is already sorted. Imagine taking a stack of papers numbered one through ten, and sliding them one by one onto a spike, always keeping the smallest on top. Each new paper just goes to the right of the last one. In a binary search tree, if we insert keys in sorted order, we get the same result. Every new node becomes the right child of the previous one, and the tree turns into a single long chain, essentially a linked list. We call this a degenerate tree. The height of the tree becomes the number of nodes, n. Operations like search and insert no longer take time proportional to log n. Instead, they degrade to O of n, or linear time, in the worst case. The tree's shape, and therefore its performance, depends entirely on insertion order. A basic BST offers no guarantee of balance. To fix this, we have self-balancing variants like AVL trees and Red-Black trees. They automatically restructure the tree during insertions and deletions to maintain a height proportional to log n. Next, we'll explore how to traverse these structures efficiently in A Tale of Two Traversals: DFS versus BFS.The Hidden Danger of Degenerate Treesalgs4.cs.princeton.eduen.wikipedia.orgcs.odu.edu+22 min
  15. 15A Tale of Two Traversals: DFS vs. BFSNow, let's put stacks and queues side by side to see how they shape traversals. Depth-first search, or DFS, relies on a stack. It explores one branch all the way down, then backtracks to the most recent fork. That's like walking as far as you can into a maze before turning around. Breadth-first search, or BFS, uses a queue. It visits all the immediate neighbors first, then moves outward level by level. Think of it like ripples spreading from a stone dropped into water. The tree itself hasn't changed, but the secondary structure you choose creates a completely different visit order. The core principle is this: the data structure enforces your processing order. If you need the newest unexplored node, pick a stack. If you need the earliest discovered node, pick a queue. Next, we'll apply this idea to a practical decision guide for choosing the right data structure.A Tale of Two Traversals: DFS vs. BFSgeeksforgeeks.orgthelinuxcode.comcodeintuition.io+21 min
  16. 16Choosing the Right Data Structure: A Practical GuideSo far we've met several data structures, each with its own strengths. But how do you choose the right one for the task at hand? Let's walk through a practical guide. Start by identifying the dominant operation. Does your algorithm mostly need random access, or does it search, insert, delete, or maintain ordering? That single question eliminates many options. Next, ask about fairness. If the oldest item must be handled first, choose a queue. If the newest item is the priority, choose a stack. For instance, a print spooler needs a queue, while an undo system needs a stack. Now compare arrays and linked lists. Arrays give you fast reads and are cache-friendly, but shifting elements is costly. A linked list shines when you already hold a pointer to a node, because you can mutate in constant time. If you need ordered fast lookup, a balanced binary search tree is a top candidate. But beware: inserting sorted data can turn it into a slow linked list. Finally, remember that you can combine structures. An L R U cache pairs a hash map with a doubly linked list. Each piece does what it does best, and together they solve a problem neither could handle alone. Let's move on to the key takeaways and next steps.Choosing the Right Data Structure: A Practical Guidegeeksforgeeks.orgthelinuxcode.comcodeintuition.io+22 min
  17. 17Key Takeaways and Next StepsLet's quickly recap what we covered. Data structures are all about optimizing access. The best choice always depends on which operations you need to perform most often, like searching, adding, or removing. We explored linear collections, stacks, queues, and trees. Remember, LIFO and FIFO are not limitations. They are guarantees about behavior that make your code predictable and safe. Now, your next step is to practice. Try implementing each of these structures in your own programming language. Use the pseudocode models as a guide. Looking ahead, we will build on this foundation with hash tables, graphs, and priority queues. Thank you for learning with me. Keep practicing, and you will master these concepts in no time.Key Takeaways and Next Steps1 min

Sources consulted

Web sources consulted while building this course.