Data Structures and Algorithms

Introduction

Data structures and algorithms is a topic covering the representation of data, and ways in which those representations can be manipulated. Many such structures are known as abstract, because they can be applied in different situations.

A list, for example, is an abstract data type - we do not specify what items go into the list at design time, but will need to create a data type specific instance of the list when we decide what we are going to do with it. It could be a list of file names, or a list of network addresses.

The data structures and algorithms used to manipulate the list, the language (C, C++, Java etc.) that the list is implemented in, and the way the list is to be implemented are only decided once the design is complete. This article focuses on abstract data types, but will also look at some concrete examples.

Data Structures

Typically, a data structure will be built up from an abstract data type, plus some implementation specific data depending on the use to be made of it. Choosing an appropriate data structure for the task in hand is vital to successfully creating the system designed to complete that task.

A record (also known as a structure) is an example of a basic data structure which allows several kinds of data to be stored (as fields, or members) within that structure. We can then refer to the structure without needing to explicitly name the members, and manipulate the data in a single object.

Object Oriented Design

The way in which data structures and algorithms are used is key to the principle of object oriented design, as it allows us to model a computer system by building it up from objects that have real world counterparts. This allows the designer to create a system of interacting units, rather than creating dependencies between the data being manipulated.

Algorithms

Often the algorithms being used to manipulate the data structures will stem from the design of the data structures themselves. For example, if we create a data structure designed to represent a list, we will need algorithms to manage a collection of such objects (i.e. the list).

Since the data structure is likely to be abstract, algorithms will need to be developed that are similarly non-implementation dependent. In this way, the whole definition of the abstract data type can be reused for other concrete examples.

Operators

The exception is in defining a set of operators that manipulate individual items. These will need to be defined in such a way as they can be overridden when the actual list of items is implemented, to allow comparison between node values, display, storage and so on.

Examples

There are many types of data structures and algorithms used to create abstract data types. Here are a few of the more common examples used in computer programming.

Stack

A stack is a container for items which can be pushed onto it, or removed from the top of it. Navigation through the stack is not normally allowed, and access is limited to one unit (or node) at a time.

Queue

A queue is similar to a stack in that items can be added or removed from it. A LIFO queue (last-in-first-out) models the same behaviour as a stack, while a FIFO queue (fist-in-first-out) allows items to be added at one end, and removed from the other.

Linked List

A linked list represents a queue of items in which individual nodes can be removed, added at arbitrary points, and the whole list freely navigated. Each node is linked to the next and/or previous node.

Designing Data Structures and Algorithms

There is an art to data modelling. The first decision a designer will make is whether to design algorithms that provide the interface that is required to model the behaviour, or the data structures that will model the data to be manipulated.

Once this has been established, then the standard abstract data types need to be considered, before creating something new. Following these rough guidelines will help to get the design, and implementation right, first time.

Print Article

Email Article

View All Articles

How to subscribe to feeds