7 Abstract data types: Designing the simplest container, the Bag
In this chapter
- The difference between an abstract data type and a data structure.
- Arrays and linked lists: Are they data structures or data types?
- The key properties of a container.
- Meet the bag, the simplest possible container.
By now, you should be familiar with arrays and linked lists, the focus of our first six chapters. These are core data structures, ubiquitous in computer science and software engineering. But more than that, they are also foundational data structures, which means that we can – and will – build more complex data structures on top of them.
In chapter 2 we discussed how arrays can be approached as concrete language features, or as abstract data types. In this chapter, we will discover that this duality isn’t limited to arrays. We will then discuss an important class of abstract data types, containers, which will be our focus for the next five chapters.
This chapter is a bridge between the first half of the book, where we have discussed core data structures and principles, and the second half, where we focus on data structures that build on top of what we have learned so far.
Here we bridge the gap by introducing the first of many examples taken from the containers class, bags.
Abstract data types versus data structures
What’s the difference between a data structure and an abstract data type? We have scratched the surface of this question when we discussed arrays.