What are data structures?Posted on: September 16, 2021
by Ruth Brooks
All computer programs store and process data. Every computer software contains a data model which defines what data will be collected and worked on. The role of the data structure in a piece of software is to define how the flow of data is controlled in relation to inputs, processes, and outputs.
A data structure can organise, process, retrieve and store data, and they make it easy for users to access and work with the data they need whilst framing the organisation of information within software so that both machine and human can better understand it. There are several basic and advanced types of data structures which are uniquely designed to arrange data for a specific purpose.
When used in computer science and computer programming, the purpose of a data structure may be to use it with various algorithms. In this case, the basic algorithm operations are paired with the data structure’s design.
Data structures are created alongside programming languages. If a computer software uses an object-oriented programming language, the data structure and its associated methods are tied together as part of a class definition. In non-object-oriented languages, some functions may be defined to work with the data structure but they are not technically a part of it.
There are three characteristics each data structure is classified by. These are:
- Linear or non-linear: Whether the data items are arranged in a sequential order or in an unordered sequence
- Homogenous or heterogeneous: Whether all data items in a given repository are of the same type
- Static or dynamic: How the data structures are compiled – static data structures have fixed sizes, structures and memory locations, dynamic data structures have sizes, structures and memory locations that can shrink or expand depending on the use
What are data types?
Whereas data structures are the building blocks for more sophisticated applications such as algorithms and computer programs, data types are the building blocks of data structures.
These typically include the following:
- Boolean: stores logical values which are either true or false
- Integer: stores a range of numbers
- Floating-point numbers: stores a formulaic representation of real numbers
- Fixed-point numbers: used in some programming languages, hold real values but are managed as digits to the left and right of a decimal point
- Character: uses symbols from a defined mapping of integer values to symbols
- Pointers: reference values that point to other values
- String: an array of characters followed by a stop code, or managed using a length field which is an integer value
How data structures are used
Data structures are used to implement the physical forms of abstract data types and are a crucial part of designing efficient computer software. They play a crucial role in the design of algorithms and how those algorithms are used within computer programs. Many programming languages include a large collection of built-in data structures which organise code and information for machine and user.
Here are some examples of how data structures are used:
- Storing data: used for efficient data persistence – specifying the collection of attributes to a dataset and its corresponding data structure
- Managing resources and services: core operating system resources and services are enabled through data structures such as linked lists for memory allocation, file directory management and file structure trees
- Data exchange: defines the organisation of information shared between applications
- Ordering and sorting: binary search trees (also known as ordered binary trees or sorted binary trees) sort objects such as character strings that are used as tags
- Indexing: B-trees index objects that are stored in a database
- Searching: indexes that have been created by binary search trees, B-trees or hash tables speed up the process of finding a specific item
- Scalability: big data applications use data structures for allocating and managing data storage across distributed storage locations within a piece of software, allowing scalability and enhancing performance
Commonly used data structures
Common data structures are essential knowledge for those in the field of software engineering. In fact, interview questions for jobs within the computer science sector may indeed ask an interviewee to list some of the most popular ones.
Arrays are a fixed-sized data structure which can hold items of the same data type such as integers, floating-point numbers, or strings. They are indexed, so random access is possible.
This type of data structure is used as a building block for array lists, heaps, hash tables, vectors and matrices, and is used for sorting algorithms such as insertion sort, quick sort, bubble sort, and merge sort.
A linked list is a sequential structure that consists of a sequence of items in linear order which are linked to each other.
Types of linked lists include: singly linked list – where traversal of items can be done in the forward direction only; doubly linked list – where traversal of items can be done forwards and backwards; and circular linked lists – where the previous pointer of the head points to the tail, and the next pointer of the tail points to the head.
A LIFO (Last In First Out) data structure, commonly found in many programming languages. Stacks resemble a real-world stack of plates, and elements can either be inserted to the top of the stack (push), or deleted and returned to the top of the stack (pop).
A FIFO (First In First Out) data structure, also commonly found in many programming languages. Elements can be inserted to the end of the queue (enqueue), or deleted from the beginning of the queue (dequeue).
A hash table stores values which have keys associated with each of them, and efficiently supports lookup if the key associated with the value is known. It is an effective data structure for searching and inserting, regardless of the size of the data.
Direct addressing uses one-to-one mapping between values and keys when storing in a table. Hash function is used to overcome this problem, and each key is given a hash value.
Trees are a structure where data is stored hierarchically and linked together. Some examples of tree data structures include binary search tree, B-tree, treap, red-black tree, splay tree, AVL tree, and n-ary tree.
Heaps are a special case of binary trees where the values of parent nodes are compared to their children nodes and arranged accordingly. They are used by JVM (Java Virtual Machine) to store Java objects.
A graph consists of a finite set of vertices or nodes and a set of edges connecting these vertices.
A directed graph indicates the direction of the start vertex and the end vertex. An undirected graph can go in both ways between the two vertices, with all edges having no set direction.
Learn more about different data structures
If you’re looking to develop your knowledge on data structures further, the North Wales Management School’s MSc Computer Science is for you, whether you currently work in the field of computer science or you’re looking to change your career path.
Designed with a real-world focus, this degree will equip you with valuable problem-solving skills which you can apply to your career, be that as a programmer, a software developer, in artificial intelligence, or another computer science career.
Studied entirely online, you’ll interact with peers from all over the world in tutorials and through our tailor-made virtual learning environment, giving you the opportunity to grow your global network.