The Self-Taught Computer Scientist

Data Structures
84
An abstract data type is a description of a data structure, whereas a data structure is an actual 
implementation. For example, a list is an abstract data type: it describes a data structure that holds 
a group of items where each item has a position relative to the others. A list also has operations to 
manipulate its items, like adding and removing them. When you use a Python list, you are using a 
data structure, not an abstract data type, because a data structure is the actual implementation of an 
abstract data type. For example, Python could have two different list data structures, implemented in 
entirely different ways, both based on the list abstract data type.
Computer scientists classify data structures based on different properties, for example, whether 
they are linear or nonlinear. A linear data structure arranges data elements in a sequence, while a 
nonlinear data structure links data nonsequentially. For example, Python lists are a linear data struc-
ture: each element can have one element before and one element after it. In contrast, graphs (which 
you will also learn more about later) are nonlinear structures where each element can connect to 
many other elements.
Traversing a data structure means going from the first element in a data structure to the last. In a 
linear data structure, you can easily traverse from the first element to the last without backtracking 
(moving backward in the data structure), whereas in a nonlinear data structure you often have to 
backtrack. It is often more efficient to access individual elements in a linear data structure because 
nonlinear data structures often require backtracking or recursion to access a single element. Because 
you can easily traverse a linear data structure, making a change to every element in one is often simpler 
than making a change to every element in a nonlinear structure. Because you don’t have to backtrack 
to visit every element, linear data structures are often easier to design and use. Regardless, nonlinear 
data structures can be better (and more efficient) for certain kinds of problems. For example, you 
can use nonlinear data structures to store and access data that would be inefficient to store in a linear 
structure, such as the connections in a social network.
Computer scientists also classify data structures by whether they are static or dynamic. A static