This post is also available in: العربية (Arabic)
Almost all computer programs use one or the other type of Data Structure. There are various types of data structures that suit different types of applications. Here we will discuss basic data structures that will be helpful in kids coding.
What is meant by Data Structure?
In computer science, a Data Structure is a way of organizing data in a computer so it can be used efficiently. By efficiently, we mean the computer operations to be performed using as few resources, in terms of execution time and memory.
Data structures are the implementation of abstract data types in a concrete and physical setting. They do this by using algorithms.
Types of Data Structure
Different kinds of data structures are suited to different kinds of applications, and some are highly specialized for certain tasks. Finding the best data structure when solving a problem is an important part of programming. B-trees are well-suited for the implementation of databases while routing tables rely on networks of machines to functions.
The data structures are broadly classified as Linear and Non-Linear Data Structures.
Linear Data Structure
Linear Data Structure has data elements arranged sequentially and each member element is connected to its previous and next element. The traversal, in this case, is sequential, which means if one wants to visit the 100th element, then one has to pass through the previous 99 elements. Such data structures are easy to implement as computer memory is also sequential. Examples of linear data structures are Array, Linked List, Stack, Queue.
Non Linear Data Structure
Non Linear Data Structure has no set sequence of connections all its elements and each element can have multiple paths to connect to other elements. The traversal from one element to another, in this case, can be done in multiple ways. Such data structures are not easy to implement but are more efficient in utilizing computer memory. Examples of non-linear data structures are Tree, Graphs, Hash Table.
Let’s understand the various data structures.
An array is the simplest type of data structure. It is a linear data type. An array holds several values of the same data type (integer, float, string, etc.). An array is normally of fixed size. After the size of the array is defined at the start, it is not possible to increase the size of the array.
An array consists of several elements, each identified by an array index or a key. You can perform any type of arithmetic operation with an index.
Let’s consider an array of integers of size 10. The organization of the elements can be visualized as:
If we call this array by the name ‘a’, then the value 14 can be accessed as a, where 5 is called array index or a key.
In many programming languages, the first position is referred to as index 0. In such a case, value 14 can be accessed as a.
Arrays are among the oldest and most important data structures and are used by almost every program. They can also be used to implement many other data structures, such as linked lists.
Some of the applications of an array are:
- A simple question paper is an array of numbered questions with each of them assigned some marks.
- 2D arrays (Two-Dimensional arrays), commonly known as matrix, are used in image processing.
- It is also used in speech processing, in which each speech signal is an array.
2. Linked List
A linked list is a set of information/data linked together by references. The data are often called nodes. The references are often called links or pointers.
The nodes can store any type of data (integer, float, string). Unlike pointers in arrays, the pointers in the linked list can only be incremented or decremented (addition and subtraction).
Some of the applications of the linked list are:
- The images are linked with each other so that an image viewer software uses a linked list to view the previous and the next images using the previous and next buttons.
- Web pages can be accessed using the previous and the next URL links which are linked using a linked list.
- The music players also use a linked list to switch between music.
- To keep the track of turns in a multi-player game, a circular linked list is used.
A stack is also a linear data structure represented by a real physical stack or a pile. In the case of the stack, the insertion and deletion of items take place at one end called the top of the stack.
The basic concept of the stack can be illustrated by thinking of your data set as a stack of books where you can only take the top item off the stack to remove books from it. Also, you can put a new book at the top only. This type of data accessing is called “Last In First Out”. That’s the reason stacks are also called LIFO lists.
Following three operations can be performed on stacks:
- Inserting (“pushing”) an item into a stack.
- Deleting (“popping”) an item from a stack.
- Displaying the contents of the top item of the stack (“peeking”).
Some of the applications of the stack are:
- Converting infix to postfix expressions.
- Undo and Redo operations are carried out through stacks.
- Syntaxes in languages are parsed using stacks.
- The stack is used in many virtual machines like JVM (Java Virtual Machine).
A queue is a linear data structure, in which the elements are inserted from one end called “tail” and the existing elements are deleted from the other end called “head”. This type of putting and removing process of elements is called “First In First Out” and hence queue is a FIFO structure in which the element that is inserted first is taken out first. A very common example of a queue is lines of people waiting at bank counters, booking counters, etc. The first person in the line who goes first is served first while the person who goes last is served last.
The process of adding an element to a queue is called “enqueuing” and the process of removing an element from a queue is called “dequeuing”.
Some of the applications of the linked list are:
- Operating System uses a queue for job scheduling.
- To handle congestion in a networking queue can be used.
- Data packets in communication are arranged in queue format.
A graph is a linear data structure where one can traverse from one node to another in many different ways.
A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y, e.g. edge (side) of a triangle joining its two vertices.
The nodes may be part of the graph structure or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute.
Some of the applications of the graph are:
- Facebook’s Graph API uses the structure of Graphs.
- Google’s Knowledge Graph also uses the concept of Graphs.
- The Dijkstra algorithm (shortest path algorithm) uses a graph structure to find the shortest path between the nodes.
- GPS (Global Positioning System) navigation system uses a graph.
A tree is one of the most powerful and advanced data structures. It is used in Artificial Intelligence (AI) and design. A tree is a non-linear hierarchical data structure that consists of nodes connected by edges.
In a tree unlike linear data structures, one can traverse from one node to another in many different ways. A tree consists of nodes (containing the data) and edges connecting the nodes.
In order to perform any operation on a tree, you need to reach a specific node. The process of reaching a node from the top-most node (also called the root) is called tree traversal.
There are three types of tree traversals:
- Inorder: First of all left node or left subtree is visited, then the root, and lastly the right node or right subtree is visited.
- Preorder: First of all the root is visited, then the left node or left subtree, and lastly the right node or right subtree is visited.
- Postorder: First of all the left node or left subtree is visited, then the right node or right subtree, and lastly the root is visited.
Some of the applications of the tree are:
- XML Parser uses tree algorithms.
- A decision-based algorithm is used in Machine Learning which works upon the algorithm of the tree.
- Databases also use tree data structures for indexing.
- Domain Name Server (DNS) also uses tree structures.
7. Hash Table
A hash table is an array where each index points to a linked list is based on a hash value. A hash value is a value determined by a hash function. A hash function determines a unique value based on the data it is storing. This allows for access to data in constant time because the computer always knows where to look for the data.
Some of the applications of the hash table are:
- Data stored in databases is generally of the key-value format which is done through hash tables.
- Every time we type something to be searched in Google Chrome or other browsers, it generates the desired output based on the principle of hashing.
- In our computers, we have various files stored in them, each file has two very crucial pieces of information that is, filename and file path. To make a connection between the filename to its corresponding file path hash tables are used.
Conclusion: Data Structures are necessary for designing efficient algorithms. It provides reusability and abstraction. Using appropriate data structures can help programmers save a good amount of time while performing operations such as storage, retrieval, or processing of data. Manipulation of large amounts of data is easier.