The third section of the course introduces the concept of an abstract data type (ADT) and how an ADT defines the method signatures rather than the internal workings, reinforcing the concept of encapsulation. You will be given the opportunity to implement a range of common collection ADTs using more than one data structure, including lists, stacks, trees, sets and maps.
Information is an abstract concept, but data is concrete. Data is the implementation or representation of information, eg: the number eleven can be represented in many different ways: 11 (decimal), XI (roman),13 (octal), B (hexadecimal). All of these are different types of data representing the same item of information.
A collection of items of information gathered together in one place is known as a node. (Nodes are implemented in many programming languages as records.) Each item of information is known as an attribute. Each attribute has a name and a type. All the structures we will discuss in this course are made up of nodes with the same collection of attributes. We can represent a node by a box, eg: a book node:
A data structure is simply a collection of nodes. In order to talk about individual nodes we must give them names. Two methods are possible:
- named nodes: we can give each node an individual name, eg: mybook, yourbook etc. To refer to the year attribute we can write mybook.year. We can assign values to attributes, eg: yourbook.cover = paper, where paper is a value of an enumerated type.
- access variables: instead of individual names for each node we may be able to obtain the address of the node or a pointer to the node. This is known as an access path and we will assume that an access path can be held in an access variable. We will also assume that each node has a unique access path. We can represent this by a diagram as shown:
If we wish to refer to the attributes of the node pointed to by the access variable av we use the notation av^, eg: av^.year.
In this course we will deal with four types of data structure: linked lists (often referred to simply as lists), stacks, queues and trees.
Next: Simple Data Structures