Join Simon Allardice for an in-depth discussion in this video What is a data structure?, part of Foundations of Programming: Data Structures.
- View Offline
Let's get some ground rule together. This term, data structure, might seem a little abstract, a little non-specific. And, usually, it's program is we're going to nail that definition down. Well, what does that mean exactly? But for our purposes, abstract and non-specific is good, it's flexible, it's useful. Because a data structure is exactly what it sounds like. It's just some arrangement of data that we've built. Not one lone integer variable over here and a string over here and a full one down here but we've gathered some data together into an orderly arrangement.
Why? Because it's useful, because it makes our lives easier to do this. The same way that if you're working in bills and taxes, you're likely to gather your paperwork together into stacks or folders, and then perhaps your folders into a filing cabinet. Because it's easy to manage when you keep related information together. That you would always write a recipe with the ingredients and the description together because if the exact same information is split up and disconnected it's kind of pointless. You'll end up with, single piece of paper that says four ounces of flour.
So we need data structures in our programs because we think this way as human beings, it's easy to forget this sometimes. We start learning about data structures and we're immediately surrounded with terms like associative arrays and binary search trees. And they sound completely detached from anything we'd ever do as a human being. But they're not, we naturally think in data structures. Okay, we don't use that term, but we think in collections of information. A recipe is an actual data structure, as is a shopping list.
A telephone directory, a dictionary, a thesaurus, an encyclopedia, a flight schedule, these are not haphazard. They have a structure, they have a format. So imagine a bank statement, we can hold that single concept in our head and we know it's a collection of information. It's an arrangement of data, it's not random. It's an intentional list of transactions with an order to it and each transaction itself is in intentional arrangement of data, information, the date, the amount, who it's from or to.
And these have nothing to do with computers, we didn't need a computer to have a bank statement or a telephone directory or a shopping list, they all existed long before computers were a glint in Charles Babbage's eye. Now if you're an object oriented programmer, you may be thinking, Well isn't this what we do with classes and objects? I mean, we define these real-world objects in a program because we think like, or at least we're supposed to. And yes, absolutely. And we'll kind of get into that later, but objects are a type of data structure, just not the only type.
I purposefully use simple, real world examples, because this term data structure does not and should not imply a level of complexity. Sure, we can have huge complex data structures, but we need a lot of small straight forward ones too. So, our working definition in this course is that. A data structure is just an intentional arrangement of data, that's it. It's a proudly non-specific definition and it covers a whole range of possibilities. There is, however, one line I am going to draw.
That our focus in this course is on data structures created and held. In memory, in a running computer program. Yes, at some point you may want to take some or all of that data and persist it. Save it out to a file on disk, or send over the network to cloud storage or to a database, but that is not what we're talking about here. Sure, when you're working with databases, SQL Server, Oracle, MySQL. We have tables, we have rows and columns, and that does meet that definition of an intentional arrangement of data, but I trust you understand where I'm drawing the distinction.
Once that data leaves our program to go to a disk drive or a separate server, that is a different set of issues. So our attention here is on the intentional arrangement of data held in memory. Inside a running application. So with that simple and non-specific definition in place, let's take a look at some simple and non-specific data structures.
Starting with simple ways of grouping data like arrays and structs, together you'll explore gradually more complex data structures, like dictionaries, sets, hash tables, queues and stacks, links and linked lists, and trees and graphs. Simon keeps the lessons grounded in the real world and answers the "why" behind many data-structuring decisions: Why use a hash table? Why is a set useful? Why avoid arrays? When you're finished with the course, you'll have a clear understanding of data structures and understand how to use them in whatever language you're programming in, today or 5 years from now.
- What is a data structure?
- Using C-style structs and arrays
- Sorting and searching arrays
- Working with singly and doubly linked lists
- Using stacks for last-in, first-out (LIFO) structures
- Using queues for first-in, first-out (FIFO) structures
- Working with hash tables
- Understanding binary search trees (BSTs)
- Learning about graphs