Video by freeCodeCamp.org · taught by David J. Malan · streamed from YouTube. All rights remain with the creator.
Lesson 5: Data Structures
About this lesson
With pointers and memory allocation in hand, this lecture shows how to build structures that hold data more flexibly than a plain array. It begins with the limitation of arrays: their size is fixed, and growing one means asking for a larger block of memory and copying every element across, which can be slow. You see how to resize an array while a program runs and why the cost of copying matters. The lecture then introduces structures in C, which group several values into one type, and uses them to build a linked list, in which each value lives in its own node that points to the next. It walks through creating nodes, inserting new values, traversing the list and freeing its memory, with careful attention to the order of steps so that no part of the list is lost, and it weighs the advantages of a linked list against its slower searching. Moving from one dimension to two, it presents trees, and in particular binary search trees, which keep values in order so they can be searched quickly, along with the risk that a tree becomes unbalanced. The lecture then turns to hash tables, which use a hash function to place each value in one of many buckets, and discusses collisions and what makes a good hash function. It also covers tries, trees of letters that allow words to be looked up in time that does not depend on how many words are stored, and abstract structures such as stacks and queues, defined by how items are added and removed. Afterwards, read Chapter 5 of the course book, which compares the cost of each structure in a table.