In computer science, data structures are an important way of organizing information in a computer. They aim to optimize space, time, and input/output operations per the application’s requirements.
Computer science encompasses theoretical and practical approaches to computing. It is divided into four sub-disciplines, which are all essential for the field:
- Theory of computation
- Algorithms and Data Structures
- Programming methodologies and Languages
- Computer Elements and Architecture
This section discusses data structure and guides you in learning different data structures and their implementation.
Imagine you get hired as a project manager for a company, and you are tasked with creating a database of names of all the company’s management and employees. To start your work, list everyone in the company and their position.
| NAME | POSITION |
| Arthur | Manager |
| Charlie | Vice President |
| Geetha | Employee |
| John | Employee |
| Johnson | Vice President |
| Julia | President |
| Keith | Manager |
| Latha | Manager |
| Manoj | Employee |
| Patrick | Employee |
| Reetha | Secretary |
| Sarala | Vice President |
| Sushma | Manager |
| Tony | Employee |
| Zoe | Employee |
However, this information only gives you one view of this company. You also want your database to show the company’s relationships between management and employees. Although it contains both names and positions, it doesn’t tell you which managers are responsible for subordinates so they can be contacted easily.
After considering the problem, you decide that a tree diagram would be the best way to display work relationships at the company.
These two diagrams represent different data structures. Your employees are organized into a list in one of the data structures. This is very useful for keeping them in alphabetical order because it makes it easier to find the employee’s name when you need it. However, creating a tree-like organizational structure is the best way to show employee relationships. The list structure is not that helpful in this regard.
In computer science, data structures are an important way of organizing information in a computer. They aim to optimize space, time, and input/output operations per the application’s requirements.
A data structure is organizing data in a computer’s memory or sometimes on a disk to be able to store and retrieve information. What does managing the data mean? It means that the data should be arranged in a way that is easily accessible.
Just like the diagram above illustrates, programmers use many different data structures to organize data in the computer; these data structures include arrays, linked lists, stacks, binary trees, and hash tables, among others.
Some data structures are good at representing relationships between data, like the tree diagram. Others allow you to order the data in a particular way, like a list of employees. Each data structure has unique properties that make it well-suited for a specific data view.
A data structure helps you to understand the relationship of one data element with the other and organize it within the memory.
Building Blocks
Data structures are built with
- Records (a.k.a. structs, classes, hashes), which group entities into a single unit with named fields
- Arrays, which store fixed-size entities into indexed, contiguous slots in memory
- Links (a.k.a. references or pointers)
Let us discuss each of these bullet points in the later section.
Types of Data Structures
Data structures are broadly categorized into two classes
- Primitive data structure
- Non-primitive data structures.
Primitive
Primitive data structures consist of the number and characters built into a programming language. Primitive data structures provided by many programming languages are integer, real, character and boolean, etc.
Most of the time, a primitive value is represented directly at the lowest level of the language implementation and is immutable, i.e., it cannot be altered.
- They are the fundamental building blocks of data structures.
- The number of bits allocated for each primitive data structure depends on the programming languages, the compiler, and the operating system.
- Primitive data structures are also referred to as primitive data types.
Non Primitive
Non-primitive data structures are derived data structures from primitive data structures. They focus on forming a set of data elements that is either homogeneous (same data type) or heterogeneous (different data type).
Examples of non-primitive data structures are arrays, lists, queues, stacks, trees, sets, etc.
Based on the structure and arrangement of data, these data structures are further divided into
- Linear data structure
- Non-linear data structures
Linear
The data items are arranged in a linear sequence in a linear data structure.
Examples of linear data structures are ‘arrays’, ‘stacks’, ‘queues’, ‘lists’,
- A linear data structure has a first and the last element.
- Each of the other elements in the linear data structure has a predecessor and a successor.
There are two techniques for representing such structure within memory.
- First way is to provide the linear relationships among all the elements represented using the linear memory location. These linear structures are termed arrays.
- The second technique provides the linear relationship among all the elements represented using pointers or links. These linear structures are termed linked lists
Non-Linear
The non-linear data structure is a kind of data structure in which data elements are not arranged in sequential order. This structure mainly represents data with a hierarchical relationship among various elements.
Examples of non-linear data structures are ‘trees’ and ‘graphs.’
Difference between linear and nonlinear data structures
| Linear | Non-Linear |
| Data items are arranged orderly where the elements are attached adjacently. | It arranges the data in sorted order, and a relationship exists between the data elements. |
| The linear relationship is present between data elements | Data elements have a hierarchical relationship |
| Easy to implement | Difficult to implement |
| We can traverse in a single run as it is linear | We can’t traverse it in a single run as it is a non-linear structure. |
| The utilization of memory is not efficient | The memory utilization is efficient |
| Array, Queue, Stack, list, etc. | Tree, Graph |
Operations on Data Structures
The basic operations that are performed on data structures are as follows:
- Insertion: Adding a new element in a data structure
- Deletion: Removal of a data element from a data structure if it is found
- Traversing: Processing of all data elements present in a data structure.
- Sorting: Arranging data elements of a data structure into some particular order, such as ascending or descending.
- Merging: Combining elements of two similar data structures to form a new data structure of the same type.
- Searching: Searching for the specified data element in a data structure.