Computer Science › Section I · Data abstractions › Topic I.5
Customized data types, classes, and objects
Integers and characters are not enough to describe songs, bank accounts or stacks. Programmers build their own types, first as plain records, then as abstract data types that bundle data with its operations, and finally as classes, the form most languages use today.
Building your own types
The topic "Traditional concepts: variables, types, and control" described the primitive types that languages provide: integers, floats, characters and Booleans. Programs often need richer data, such as a music track with a title, a length and a rating, so modern languages let programmers define new types from the primitive ones and use them almost as if built in. This topic climbs three steps: record types, which name a layout of data; abstract data types, which add operations and hide the layout; and classes, which extend abstract data types.
User-defined types in C
In C, struct Track { char title[40]; int seconds; float rating; }; defines a new type named struct Track but creates no variable. Afterwards, struct Track first, second; declares two variables of that type, just as float x, y; declares two floats. Each variable is a whole block of memory holding the three fields, and first.seconds = 215; changes one field of one variable. Compare struct { ... } first; with no type name: it creates a single variable of a one-off layout that cannot be reused for other declarations. Naming the type is what lets one definition serve the whole program.
Types and instances
A user-defined type is a description, not data. It says what every item of that type contains, as a blank form lists the boxes to fill in. Each actual item made from it is an instance, like one completed copy of the form; struct Track first, second; makes two instances of one type. Python offers a compact way to define such a type. Line 1: from dataclasses import dataclass. Line 2: @dataclass above class Track:, followed by the indented lines title: str, seconds: int and rating: float. Then a = Track("Blue Hour", 215, 4.5) makes an instance, and a.seconds = 220 changes one of its fields.
What a record type does not give you
A record type describes storage only. Suppose a stack is stored as a struct holding an array of 20 integers and an integer Top that indexes the next free slot. Nothing in the type says how to push or pop, so every part of the program must write that code itself. Worse, any code can reach inside: one careless line such as s.Top = 7; or s.items[2] = 0; breaks the stack, because entries can now change in the middle or appear from nowhere, and its last-in, first-out behaviour is lost. The type has the right data but none of the rules that make it a stack.
Abstract data types
An abstract data type (ADT) is a type defined by the operations it allows, together with the data they act on. A stack ADT offers push, pop, is_empty and is_full, and promises last-in, first-out behaviour; it says nothing about arrays or pointers. Languages that support ADTs provide two features. First, a way to define the data and its operations as a single unit, which keeps related code together and eases maintenance. Second, a way to hide the internal representation, so other code can reach the data only through the operations. Languages such as Ada, widely used from the 1980s, made this a central feature.
Interfaces in Java
Java can state an ADT's operations on their own with an interface: interface IntStack { void push(int item); int pop(); boolean isEmpty(); boolean isFull(); }. It lists each operation's name, parameters and result type, but contains no storage and no algorithms. Those come from a class that implements the interface, such as class ArrayStack implements IntStack { private int[] items = new int[20]; private int top = 0; ... }, with a public method body for each of the four operations. Code can then declare IntStack s = new ArrayStack(); and call s.push(25). Because s is declared as an IntStack, the calling code depends only on the four operations.
Classes extend abstract data types
A class does everything an ADT does: it bundles the data, held in instance variables, with the methods that act on it, and marks members private so outside code must use the methods. Each object is an instance of its class, just as a variable is an instance of a user-defined type. But classes add more, as "Object-oriented programming" explained: constructors that set up each new object, inheritance, so a new class can extend an old one, and polymorphism. The ease of defining and reusing abstractions this way is a large part of why the object-oriented paradigm became so popular.
Worked example: a stack class in Python
Line 1: class Stack:. Indented below it, Line 2: def __init__(self): self._items = []. Line 3: def push(self, x): self._items.append(x). Line 4: def pop(self): return self._items.pop(). Line 5: def is_empty(self): return len(self._items) == 0. Now run s = Stack(); s.push(5); s.push(8). 1. The constructor gives s its own empty list. 2. The pushes make the list [5, 8]. 3. print(s.pop()) prints 8, the last value pushed. 4. print(s.is_empty()) prints False, since 5 remains. 5. One more pop returns 5, and is_empty() now prints True. The leading underscore in _items signals "internal"; Python does not enforce it.
Worked example: new insides, same interface
Rewrite the stack with linked nodes, each node a pair (value, next). Line 1: class LinkedStack:. Line 2: def __init__(self): self._top = None. Line 3: def push(self, x): self._top = (x, self._top). Line 4: def pop(self): x, self._top = self._top, then return x. Line 5: def is_empty(self): return self._top is None. 1. Pushing 5 then 8 makes _top equal to (8, (5, None)): 8 points to 5, which points to nothing. 2. pop unpacks the pair, returns 8 and makes the node holding 5 the top. 3. The calls from the previous example print exactly the same results. 4. Any program that used only push, pop and is_empty needs no change at all. That freedom is the point of an abstract data type.
Ready-made abstract types
Stacks, queues, lists and trees are needed so often that most languages ship them in a library. The C++ Standard Template Library offers std::stack, std::queue and std::vector, Java provides classes such as ArrayDeque and HashMap, and Python has its list, dict and collections.deque. Using them is like using a primitive type: declare a variable and call its operations, trusting the library's tested code. Writing your own once is still worthwhile: it shows what library types do for you, and how to build one when nothing ready-made fits.
Common mistakes to avoid
First, confusing a type with an instance: struct Track defines one type, and first and second are two instances of it. Second, believing a struct definition by itself creates a variable. Third, treating a record type as an abstract data type; a record has no operations and no protection. Fourth, writing code that reaches into an object's internals, such as s._items, which breaks the moment the representation changes, as LinkedStack showed. Fifth, leaving an ADT's empty case unspecified: popping an empty Stack raises an IndexError, but popping an empty LinkedStack raises a TypeError, so callers should check is_empty first.
Key takeaways
User-defined types, such as C structs and Python dataclasses, name a layout of fields built from primitive types. A type is a template; each item made from it is an instance. Record types describe storage only, so any code can corrupt their data. An abstract data type defines a type by its operations and hides its representation; Java interfaces declare such operations. Classes extend abstract data types with constructors, inheritance and polymorphism. Because users rely only on the operations, the implementation can change, from a list to linked nodes, without changing the programs that use it.
Flashcards
Flashcard
A new type built by the programmer from primitive types
Test your understanding
Question 1 of 5
A C program contains struct Point { int x; int y; }; and later struct Point a, b;. How many user-defined types and how many instances does this create?
Question 2 of 5
What does an abstract data type provide that a plain record type does not?
Question 3 of 5
Using the Stack class from the reading, s = Stack(), then s.push(3), s.push(7), s.pop(), s.push(9). What does print(s.pop(), s.pop()) show?
Question 4 of 5
In Java, what does interface IntStack { void push(int item); int pop(); boolean isEmpty(); boolean isFull(); } contain?
Question 5 of 5
A program uses a Stack only through push, pop and is_empty. The Stack class is rewritten to use linked nodes instead of a list. What must change in the program?
