github twitter email rss
CS Notes: Data Structures and Abstract Data Types
Feb 21, 2017
4 minutes read

Please note, this post is part of my notes for the AQA Computer Science exams, which I am taking in 2017. The content is taken directly from the course, so any inaccuracies are the fault of AQA (I have to know them regardless)

First, some definitions.

A data structure is any method used to store data in an organised and accessible manner.

An abstract data type is a purely conceptual model of how data can be stored and processed. Each programming language and standard library will have a different implementation of this, this being the data structure. However, they still implement the same abstract data type. As an example, we have the concept of a linked list, yet C++ has a different implementation of this model to what Golang may have.

Different data structures are more suited to different applications and requirements, and have different strengths and weaknesses.

Arrays

An array is essentially a named sequence of data. Each item in an array is known as an element. Arrays can have multiple dimensions, so you may have a 1D array, 2D array, etc. However, generally you will be dealing with a 1D array. Arrays are used to store a table or sequence of related data. In many programming languages, a 2D array would be a 1D array where each element itself is another array. Arrays are also stored contiguosly in memory, ie, each element right next to its neighbours in memory.

In some languages, you actually need to state how much memory an array is going to occupy when defining it, whereas in others they can be dynamically resized and reallocated during runtime.

As an example, let’s represent the inventory of the player in a game.

Instead of

Item1 = "Sword"
Item2 = "Shield"
Item3 = "Bow"

the programmer could use an array called inventory, and do something like this:

Inventory = []
Inventory[0] = "Sword"
Inventory[1] = "Shield"
Inventory[2] = "Bow"

Each number inside square brackets is known as an index, while the general square bracket usage is known as index notation.

Files

There is also the obvious way of storing data, in a file.

There are many different file formats, some are more standard, while others are more application specific. Two common formats are text files and binary files.

A text file is little more than lines of human-readable data. Each line is usually referred to as a record, and each item of data is referred to as a record (this is similar to SQL.) They are commonly encoded using ASCII, or more recently UTF-8/Unicode. Configuration files and anything else that will need to be read and/or edited by a human are often stored in a text file.

Binary files usually have some form of header describing how the data is stored, as they are often more complex than a text file. They are less easily readable by humans, but can be read very quickly by a machine.

Images are represented in a binary format, as are executables.

Static and dynamic data structures

There are two main classifications of data structure, static and dynamic.

Static data structures have a predefined size, and they cannot change. For instance, if I say that my static array has length of 10, then that will stay the same throughout the runtime of my program. This is done by allocating a set quanitity of memory to the data structure, and they are usually very fast to access. However, they will use up their set amount of space regardless of whether they are used or not.

Dynamic data structures can use as much memory as required through the use of the heap. Unused blocks of memory are available to the program via the heap, and can be taken from here if needed and returned when no longer in use. This is generally a more efficient use of resources, and is more flexible. However, it is slower, and it is therefore better to use a static resource if you already know how much capacity your program is going to need.


Back to posts