What are data structures? - University of York

Data is a core component of virtually every computer programme and software system – and data structures are what store, organise, and manage that data. Data structures ensure that different data types can be efficiently maintained and accessed, and effectively processed and used, in order to perform both basic operations and advanced tasks.

There are different data structure types – some basic and some more complex – that have been designed to meet different requirements, but all of them typically ensure that data can be understood by both machines and humans, and then used in specific ways for specific purposes.

But to understand the different types of data structures, it’s important to first understand the different types of data.

What are the different data types?

Data types are the foundation of data structures. They are what tell the computer compiler or interpreter – which translates programming languages such as Java, JavaScript and Python into machine code – how the programmer intends to use the data. They typically fall into one of three categories.

Primitive data types

Primitive data types are the most basic building blocks of data, and include:

Boolean, which has two possible values – true or false
characters, such as letters and numerals
integers and integer values, which are whole numbers that do not contain a fraction
references (also called a pointer or handle), which allow a computer programme to refer to data stored elsewhere, such as in the computer’s memory
floating-point numbers, which are numbers that include a decimal
fixed-point numbers, which are numbers that include a decimal up to a fixed number of digits

Composite data types

Also known as compound data types, composite data types combine different primitive data types. They include:

arrays, which represent a collection of elements, such as values or variables
records, which group several different pieces of data together as one unit, such as names and email addresses housed within a table
strings, which order data in structured sequences

What is an associative array?

An associative array – also called maps, symbol tables, or dictionaries – is an array that holds data in pairs. These pairs contain a key and a value associated with that key.

Abstract data types

Abstract data types are defined by their behaviour, and include:

queues, which order and update data using a first-in-first-out (FIFO) mechanism
stacks, which order and update data using a last-in-first-out (LIFO) mechanism
sets, which can store unique values without a particular order or sequence

What are the different types of data structures?

There are several different structures that store data items and process them, but they typically fall into one of two categories: linear data structures or non-linear data structures.

The data structure required for any given project will depend upon the operation of the programme or software, or the kinds of sorting algorithms that will be used.

Examples of linear data structures

Array data structures

Like array data types, array data structures are made up of a collection of elements, and are among the most important and commonly used data structures. Data with an array structure is stored in adjoining memory locations, and each element is accessed with an index key.

Linked list data structures

Linked list data structures are similar to arrays in that they are a collection of data elements, however, the order of these elements is not determined by their place within the machine’s memory allocation. Instead, each element – or node – contains a data item and a pointer to the next item.

Doubly linked list data structures

Doubly linked lists are more complex than singly linked lists – a node within the list contains a pointer to both the previous node and the next node.

Stack data structures

Stacks structure data in a linear format, and elements can be inserted or removed from just one side of the list – the top – following the LIFO principle.

Queue data structures

Queues are similar to stacks, but elements can only be inserted or removed from the rear of the list, following the FIFO principle. There are also priority queues, where values are removed on the basis of priority.

Examples of non-linear data structures

Tree data structures

Trees store elements hierarchically and in a more abstract fashion than linear structures. Each node within the structure has a key value, and a parent node will link to child nodes – like branches on a family tree. There are a number of different types of tree structures, including red-black tree, AVL tree, and b-trees.

What is a binary tree?

Binary trees are tree data structures where each node has a maximum of two child nodes – a left child and a right child.

They are not to be confused with binary search trees, which are trees that are structured to be increasingly complex – a node is always more complex than the node that came before it, and the structure’s time complexity to operate will be directly proportional to the height of the tree.

Graph data structures

Graph structures are made up of a set of nodes – known as vertices – that can be visualised like points on a graph, and are connected by lines known as edges. Graph data structures follow the mathematical principles of graph theory.

Hash data structures

Hash data structures include hash lists, hash tables, hash trees, and so on. The most commonly known is the hash table, also referred to as a hash map or dictionary, which can store large amounts of data, and maps keys to values through a hash function. They also employ a technique called chaining to avoid collisions, which can occur when two keys are hashed to the same index within the hash table.

Dig deeper into data structures

Explore data structures in depth and prepare for a career in computer science with the online MSc Computer Science at the University of York. One of your key modules covers data structures, so you’ll learn techniques for using algorithms and associated data structures while also studying computer programming, computer architecture and operating systems, and software engineering.

This master’s degree is studied 100% online and has been designed for working professionals and graduates who may not have a computer science background but want to launch a career in the lucrative field.