A data structure is a specialized format for organizing, processing, retrieving and storing data. While there are several basic and advanced structure types, any data structure is designed to arrange data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.
In computer programming, a data structure may be selected or designed to store data for the purpose of working on it with various algorithms. Each data structure contains information about the data values, relationships between the data and functions that can be applied to the data.
Characteristics of data structures
Data structures are often classified by their characteristics. Possible characteristics are:
- Linear or non-linear: This characteristic describes whether the data items are arranged in chronological sequence, such as with an array, or in an unordered sequence, such as with a graph.
- Homogeneous or non-homogeneous: This characteristic describes whether all data items in a given repository are of the same type or of various types.
- Static or dynamic: This characteristic describes how the data structures are compiled. Static data structures have fixed sizes, structures and memory locations at compile time. Dynamic data structures have sizes, structures and memory locations that can shrink or expand depending on the use.
Types of data structures
Data structure types are determined by what types of operations are required or what kinds of algorithms are going to be applied. These types include:
- Arrays- An array stores a collection of items at adjoining memory locations. Items that are the same type get stored together so that the position of each element can be calculated or retrieved easily. Arrays can be fixed or flexible in length.
- Stacks- A stack stores a collection of items in the linear order that operations are applied. This order could be last in first out (LIFO) or first in first out (FIFO).
- Queues- A queue stores a collection of items similar to a stack; however, the operation order can only be first in first out.
- Linked lists- A linked list stores a collection of items in a linear order. Each element, or node, in a linked list contains a data item as well as a reference, or link, to the next item in the list.
- Trees- A tree stores a collection of items in an abstract, hierarchical way. Each node is linked to other nodes and can have multiple sub-values, also known as children.
- Graphs- A graph stores a collection of items in a non-linear fashion. Graphs are made up of a finite set of nodes, also known as vertices, and lines that connect them, also known as edges. These are useful for representing real-life systems such as computer networks.
- Tries- A trie, or keyword tree, is a data structure that stores strings as data items that can be organized in a visual graph.
- Hash tables- A hash table, or a hash map, stores a collection of items in an associative array that plots keys to values. A hash table uses a hash function to convert an index into an array of buckets that contain the desired data item.
Uses of data structures
In general, data structures are used to implement the physical forms of abstract data types. This can be translated into a variety of applications, such as displaying a relational database as a binary tree.
Importance of data structures
Data structures are essential for managing large amounts of data, such as information kept in databases or indexing services, efficiently. Proper maintenance of data systems requires the identification of memory allocation, data interrelationships and data processes, all of which data structures help with.
Additionally, it is not only important to use data structures but it is important to choose the proper data structure for each task. Choosing an ill-suited data structure could result in slow runtimes or unresponsive code. A few factors to consider when picking a data structure include what kind of information will be stored, where should existing data be placed, how should data be sorted and how much memory should be reserved for the data.