What is data structure

#1. What is Data Structure and why it’s so important?

Before getting dive into what is a data structure, first, let’s see what is data type and how it is related to data structures.

Data Type :

A data type is something that defines a domain of allowed values and the operations that can be performed on those values.

For example in C language, the int data type can take values in range and operations that can be performed are addition, subtraction, multiplication, division and all those stuff which can be done with numbers in mathematics.

Similarly, there are many other data types like float, double, String, char, boolean, etc.

These data types are built-in data types also known as primitive data types and the values and operations for them are pre-defined in the programming language.

If an application needs to use a data type other than the primitive data types of language, then it is the programmer’s responsibility to specify the values and operations for that data type and implement it. For example, there is no built-in type dates in c, and if we need to process dates, we have to define and implement a data type for a date.

Abstract Data Types (ADT) :

An abstract data type is a mathematical model or concept that defines a data type logically. It specifies a set of data and collection of operations that can be performed on that data.

The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations.

These process of hiding details is also known as Abstraction.

For example, consider Stack ADT

Stack: A stack contains elements of the same type arranged in sequential order and following operations can be performed on the stack.

Data Structures :

Now, here comes the Data Structures. So what really it is?

Data Structure is a programming construct used to implement an ADT.

It is the physical implementation of ADT. All operations specified in ADT are implemented through functions in the physical implementation. A data structure that is implementing an ADT consists of a collection of variables for storing the data specified in the ADT and the algorithms for implementing the operations specified in ADT.

ADT is the logical view of data and the operations to manipulate the data while Data Structure is the actual representation of data and the algorithms to manipulate the data.

What are the Advantages of Data Structures?

Here are some advantages of using data structures.

Now, in the next section, we will cover the types of data structure, it’s importance and some brief overview of different data structures.

Data Structures

What is Data Structure:

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

A data structure is not only used for organizing the data. It is also used for processing, retrieving, and storing data. There are different basic and advanced types of data structures that are used in almost every program or software system that has been developed. So we must have good knowledge about data structures.

Classification of Data Structure:

Classification of Data Structure

For example, we can store a list of items having the same data-type using the array data structure.

Array Data Structure

This page contains detailed tutorials on different data structures (DS) with topic-wise problems.

Introduction to Data Structures:

Popular types of Data Structures:

Overview:

Linked List:

Singly Linked List:

Circular Linked List:

Heap:

Graph:

Introduction, DFS and BFS:

Advanced Data Structure:

Advanced Lists:

Segment Tree:

All Articles on Trie
Binary Indexed Tree:

All Articles on Binary Indexed Tree
Suffix Array and Suffix Tree:

Splay Tree:

B Tree:

Red-Black Tree:

K Dimensional Tree:

Others:

Matrix:

Misc:

GeeksforGeeks Courses

DSA – Self Paced Course

Master DSA’s most popular course at the best price possible, trusted by over 75000+ students! Curated by experts having years of industry expertise, you will master all of the major topics of data structures and algorithms like as sorting, strings, heaps, DP, searching, trees, and more, as well as practise these concepts on real-world projects. Prepare for SDE interviews with big tech giants like Microsoft, Amazon, and Adobe, as well as other top product-based companies. Enrol now!

Complete Interview Preparation

An enriching course designed by the experts to help you crack the coding interview of top product or service-based organizations. Get 200+ algorithmic coding problems, premium lecture videos, subject-wise theoretical content, lifetime access, and much more. Here you’ll get prepared for each and every subject & skill relevant to the interview whether it be core CS subjects, programming language, reasoning & aptitude, resume building, etc.

Live Courses

Get best-in-industry real-time GFG Live Courses to upskill yourself and get into your dream company. You can attend these live classes from any geographical location and here you can ask your doubts to the instructor just like an offline classroom program. Do check out these worthwhile Live Courses by GeeksforGeeks – System Design Live, Competitive Programming Live, and more!

What is Data Structure?

Learn What is Data Structures?

Abstract

A data structure is a meaningful way of arranging and storing data in a computer so as to use it efficiently.

Scope of the article

Speaking about scope, now would be a good time to lay down the expectations as well:

Takeaways

Data structures provides means for management of large dataset such as databases or internet indexing services.

Let’s take a look at a real-life analogy.

If you go out shopping at a grocery store, you would expect related items to be in the same section, such as the fruit and vegetable section, the meat section, the dairy section, etc. These items can be further organized according to their prices and so on.

Such meaningful structuring of items helps the business operate efficiently. Because you (or anyone) would never visit (or re-visit) a messy store where it takes forever to find each of your required items. 😔

Likewise, you wouldn’t want to use a slow computer where searching for an old photo takes around a day. That’s why we have an efficient data structure called the ‘file system’ that organizes and stores said data into a hierarchy starting from the root directory.

Though file system is a much more advanced data structure, it does try to solve the fundamental issue that any data structure tries to tackle i.e. efficient way of storing, organizing, and maintaining data.

Now, before proceeding further, we need to make sure we are on the same page when talking about certain terms.

Basic Terminology

It’s important to note that we will mainly discuss non-primitive data structures; what I mean by that you shall see! 😀

Types of Data Structures

But what makes an array an array, and how is it any different from a linked list or a tree?

How many different data structures are out there in the wild? рџ¤Ё

Well, I am here to tell you that there are mainly two types of data structures, namely

The primitive data structure, also known as built-in data types can store the data of only one type. You know the integers, floating points, characters, pointers, stuff like that.

Non-primitive data structures, on the other hand, can store data of more than one type. For example, array, linked list, stack, queue, tree, graph, and so on. These are often referred to as derived data types.

Let’s have a look at the big picture

And if that’s not enough, stacks and queues are also interchangeably referred to as ADT and not concrete data structures!

Wait a minute, what! 😯

Linear data structures

Let’s take a scenario, say we want to store the prices of all the groceries that we purchased. So we can allocate a contiguous memory block of size ‘n’, where ‘n’ refers to the number of items we purchased.

Array

Here, an array could be a suitable data structure as it’s just a collection of similar data types like int, float, char, etc.

Since the prices are likely to be floats, we could store these in an array, like so:

The coolest thing about an array is it provides you constant access to each element by means of zero-based indexing. рџ™…рџЏ»

In order to access the price of the third element, we could say prices[2].

Now, how about storing the prices of all the groceries that we are about to buy but don’t know the quantity in advance!

Since the array requires you to specify the size in advance, here such an attempt would be futile.

For example, setting the size of an array to the total number of items in the store or something. Nevertheless, intuition suggests that would be highly inefficient. Also, remember, the sole purpose of data structure is to increase efficiency by means of carefully organizing data.

Linked List

Instead of allocating the contiguous memory blocks in advance, how about we wrap our data in a node that spits out a reference that we can use to point to the next node.

Voila, we have a list of linked nodes vis-a-vis linked list. Alas, we lose indexing!

To learn more about linked lists, you can check out this article. 😉

Linear data structures are mainly classified into two categories, static and dynamic.

I think, suffice to say, an array is a static data structure whereas a linked list is dynamic!

Non-linear Data Structures

Non-linear data structures are not arranged sequentially in that each element of such data structures can have multiple paths to connect to other elements or form a hierarchy.

Let’s go back to the example of the file system. Visualizing it gives an impression of a upside down tree-like structure that preserves hierarchy in the form of the parent folder, child folder, and so on.

So, how can we build such a file system using data structures?

Obviously, by using a tree-like data structure aka trees (pun intended). рџЊІ

Trees are indeed one of the most important data structures with a hierarchical relationship among its elements aka nodes which are connected by links aka edges. If it helps, think of a tree as a linked list but with two or more pointers.

However, unlike a circular linked list, a tree doesn’t have any cycle, ♻

Because it doesn’t make any sense if we could circularly navigate our directory like so,

For instance, searching for a pic that didn’t exist in the computer, to begin with, would never terminate and crash the whole system.

For instance, searching for a pic that didn’t exist in the computer, to begin with, would never terminate and crash the whole system.

But there could be instances where we do need such cycles or the situation could be a tad bit complicated.

In the context of social media, an expression like this doesn’t seem unheard of;

‘I’m Jane, a friend of a friend of Joe, and since you also follow Joe, I was thinking maybe we can be friends, please accept my request. ‘

What data structure can model these intricate relationships? рџ”Ќ

Graph

A graph contains nodes and edges much like a tree but far more superior and versatile. It can be so powerful that it has a dedicated branch named ‘Graph Theory’ in mathematics. 😋

A graph can have cycles, disjoints, and all kinds of flexibility on top of a tree. Hence, it’s important to remember that a tree falls under a special category of graphs.

Whew, that was a lot.

I hope you have got some clarity on the major distinctions between linear and non-linear data structures.

But it doesn’t stop here, we can mix-match and further build more and more niche data structures by implementing the generic counterparts.

For example, a hash map is perhaps the most useful (disputable) data structure that implements an associative array abstract data type, a structure that can map keys to values. Hash maps, in turn, are often built on top of a linked list. рџ‘Ѓ

A linked list can also directly implement other abstract data types such as stack and queue.

But what is this abstract data type? рџ¤Ё

Abstract Data Type (ADT)

In computer science, we often talk about abstraction and programming to an interface.

For instance, you don’t need to know automobile engineering to drive your car to the grocery store. You just have to know how to drive since the manufacturers already abstracted away all the intricacies of the car engine and other internal mechanisms. And for driving, you do get interfaces such as a steering wheel and a gearshift in order to interact with the car.

Likewise, every data structure has a corresponding interface known as Abstract Data Type or ADT. Simply put, an abstract data type only addresses the interface, and data structures implement that interface.

Queue

For instance, a queue is an ADT that must maintain the First In First Out ( FIFO ) ordering of elements. It simply means, the first person to get in the queue, would be the first person to get out of the queue.

This idea of a queue ADT might have been inspired by a real-world standing queue in front of a grocery store counter or similar scenarios.

Stack

On the other hand, Stack is another example of ADT that conforms to the Last In First Out (LIFO) ordering of elements.

This idea of this ADT is probably inspired by a real-world stack of books. рџ“™

Basic Operations

We have covered a lot of ground by discussing several data structures such as array, linked list, stack, queue, tree, graph, hashmap and probably hinted at their respective use-cases but never really got to the specifics.

Like, how do they operate?

Well, it turns out almost all data structures support a few key operations. which we are about to explore next!

Search

Hands down, the most useful operation! If you cannot search an element, how are you ever gonna be able to do anything?

Okay if that sounds vague, think of it like this — you are at a grocery store (for some reason I’m obsessed with grocery) and you are putting items into a cart.

Here, an item like Rs. 50 chocolate bar would be your data and the cart itself is a data structure. Let’s assume you forgot afterward if you had picked the chocolate bar or not.

How can you ever be sure if you are unable to search? рџ”Ћ

Now, you may claim your memory is sharp (unlike me) and you remember putting the item in the cart but then how can you show it to the counter?

How can you ever access it if you cannot search for it? (Thoughtful exercise, give it a shot! рџ’Ў)

Traverse

Traversing means iterating through a data structure in some particular order.

In an array, you could access an element in constant time i.e. O(1) provided you knew its position beforehand!

But that doesn’t mean you can search for it in constant time.

You still need to start from the first index and search for it. Hence, in order to search you need to traverse. 🏃‍♂️

So, we conclude that traversal is also as useful as searching.

Insert

Insertion basically means to insert one or more elements into your data structure. Elements can be inserted at the beginning, end or at any specified position.

In some data structures, you don’t even need to specify a position e.g. insertion in a heap.

Insertion is a fundamental operation because if you cannot insert anything into your data structure, why bother having one?

A cart рџ›’ exists for a reason to help facilitate storing items for purchase. In order to store it, you must insert it.

Delete

Once we are done with our shopping, we need to delete items from the cart, show them to the counter, and put it into our bag (another data structure).

Now, imagine we didn’t have this operation so we would never be able take any items out of the cart ever.

Seems like a miserable world I don’t wanna live in!

But you can argue, you don’t need to delete a number in an array to use it!

Because we can access an element like this:

Well, you got me there!

So, depending on the chocolate_bar’s data type, there are two possible scenarios:

The second scenario is practical but highly inefficient which contradicts the existence of data structure.

I mean you can do that but chances are you are much better off by using a cart that supports deletion and you can use other data structures like a plate to eat рџЌЅ and a garbage bin рџ—‘ to dispose of the wrapper.

Update

This one builds on top of searching and inserting e.g. you suddenly realized you’ve purchased the wrong chocolate bar so you search the wrong bar in the cart and replace it with the correct bar.

Now you might say, replacing could be also be considered an operation that builds on top of deletion and insertion.

I know it’s weird, I mean talk about violating conservation laws left and right!

But here we reach the limit of our analogy of the physical world with that of the binary!

When I say replace, I mean magically making the older bar disappear and changing its place with the new one by doing:

Here we just searched the cart and then found it to be on position 35 and replaced it with a better_chololate bar. вњЌрџЏ»

This is a quite advanced data structure operation and an array is highly efficient for this kind of operation due to its constant access and linear ordering.

Linked lists can also be sorted by manipulating pointers and so can be trees.

A special sorted binary tree known as the Binary Search Tree is one of the most useful data structures out there.

I mean, you can imagine and probably appreciate a grocery store for having all its similar items sorted in an aisle according to their prices from left to right.

So, if you are craving an expensive chocolate bar you know exactly in which direction to look! вћЎпёЏ

Merge

This is not a fundamental operation and in fact, it uses other basic ones to help facilitate the said process e.g. merging two linked lists into one by manipulating pointers, or two BSTs into one.

To put into perspective, putting the items from two carts into a larger one could be a case for merging. рџ›’вћ•рџ›’= рџ›’

Merging is also used for one of the most well-known sorting algorithms, namely merge sort (how original).

Advantages of Data Structures

None of my previous rants would make sense if there weren’t inherent benefits for using a data structure.

But I must tell you that these advantages are generic and conformed by every single data structure, so let’s check them out:

For example, searching for a value by its key is better suited for hash maps than an array.

A tree is more likely to be efficient to model any file system but not efficient for representing relations in social media applications.

You don’t need to know how STL’s unordered_map works under the hood to write an application using it in C++, you just need to know what operations it supports and how you can use that to your advantage?

In fact, you can think of the database itself as this huge composite data structure capable of storing data even when a program has run its course.

Why do we need to learn Data Structuresвќ“

That’s a reasonable question because many things in life are important but not everyone needs to learn everything. рџ¤—

Having said that, if you aspire to become a software engineer or an ML engineer or a data scientist or pursue a Ph.D. in computer science, you need to know your data structures (and also algorithms to work with those data structures).

The necessity of knowing data structures could also be a self-fulling prophecy, albeit for wrong reasons, nevertheless every bit happening.

Let me parse it for contextual ease of understanding —

Whichever lens you pick is up to you but it doesn’t take away from the fact that data structures are indeed one of the most important topics that have massive implications in software and computer science (and technical interviews).

That article dives much deeper into answering the question.

Epilogue

Let’s take a brief pause and reflect on what we have seen so far! 😇

Whewie… 😅 we covered a lot in this article and if you can answer.

I encourage you to go ahead and pick one data structure and learn it well and also practice problems that can be solved using it.

You might wanna start with simpler ones and then slowly work towards more complicated data structures.

Oh and I also remembered that I have yet to purchase this week’s grocery! 😫

What is Data Structure: Types, Classifications and Applications

What is Data Structure:

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

A data structure is not only used for organizing the data. It is also used for processing, retrieving, and storing data. There are different basic and advanced types of data structures that are used in almost every program or software system that has been developed. So we must have good knowledge about data structures.

Data structures are an integral part of computers used for the arrangement of data in memory. They are essential and responsible for organizing, processing, accessing, and storing data efficiently. But this is not all. Various types of data structures have their own characteristics, features, applications, advantages, and disadvantages. So how do you identify a data structure that is suitable for a particular task? What is meant by the term ‘Data Structure’? How many types of data structures are there and what are they used for?

What is Data Structure: Types, Classifications, and Applications

We have got you covered. We have made a complete list of everything about what data structure is, what are the types of data structures, the classification of data structures, the applications of each data structure, and so on. In this article, we will discuss every aspect of each data structure to help you choose the best one in just minutes.

Table of Contents

How Data Structure varies from Data Type:

We already have learned about data structure. Many times, what happens is that people get confused between data type and data structure. So let’s see a few differences between data type and data structure to make it clear.

Classification of Data Structure:

Data structure has many different uses in our daily life. There are many different data structures that are used to solve different mathematical and logical problems. By using data structure, one can organize and process a very large amount of data in a relatively short period. Let’s look at different data structures that are used in different situations.

Classification of Data Structure

Need Of Data structure :

The structure of the data and the synthesis of the algorithm are relative to each other. Data presentation must be easy to understand so the developer, as well as the user, can make an efficient implementation of the operation.
Data structures provide an easy way of organizing, retrieving, managing, and storing data.
Here is a list of the needs for data.

Arrays:

An array is a linear data structure and it is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together in one place. It allows the processing of a large amount of data in a relatively short period. The first element of the array is indexed by a subscript of 0. There are different operations possible in an array, like Searching, Sorting, Inserting, Traversing, Reversing, and Deleting.

Characteristics of an Array:

An array has various characteristics which are as follows:

Applications of Array:

Different applications of an array are as follows:

Real-Life Applications of Array:

Want to get started with arrays? You can try out our curated articles and lists for the best practice:

Linked list:

A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

Types of linked list:

Characteristics of a Linked list:

A linked list has various characteristics which are as follows:

Applications of the Linked list:

Different applications of linked list are as follows:

Real-Life Applications of a Linked list:

Want to get started with a linked list? You can try out our curated articles and lists for the best practice:

Stack:

Stack is a linear data structure that follows a particular order in which the operations are performed. The order is LIFO(Last in first out). Entering and retrieving data is possible from only one end. The entering and retrieving of data is also called push and pop operation in a stack. There are different operations possible in a stack like reversing a stack using recursion, Sorting, Deleting the middle element of a stack, etc.

Characteristics of a Stack:

Stack has various different characteristics which are as follows:

Applications of Stack:

Different applications of Stack are as follows:

Real Life Applications of Stack:

Want to get started with Stack? You can try out our curated articles and lists for the best practice:

Queue:

Queue is a linear data structure that follows a particular order in which the operations are performed. The order is First In First Out(FIFO) i.e. the data item stored first will be accessed first. In this, entering and retrieving data is not done from only one end. An example of a queue is any queue of consumers for a resource where the consumer that came first is served first. Different operations are performed on Queue like Reversing a Queue (with or without using recursion), Reversing the first K elements of a Queue, etc. Few basic operations performed In Queue are enqueue, dequeue, front, rear, etc.

Characteristics of a Queue:

Queue has various different characteristics which are as follows:

Applications of Queue:

Different applications of Queue are as follows:

Real-Life Applications of Queue:

Want to get started with Queue? You can try out our curated articles and lists for the best practice:

A tree is a non-linear and hierarchal data structure where the elements are arranged in a tree-like structure. In a tree, the topmost node is called the root node. Each node contains some data, and data can be of any type. It consists of a central node, structural nodes, and sub-nodes which are connected via edges. Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure. A tree has various terminologies like Node, Root, Edge, Height of a tree, Degree of a tree, etc.

There are different types of Tree like

Characteristics of a Tree:

Tree has various different characteristics which are as follows:

Applications of Tree:

Different applications of Tree are as follows:

Real Life Applications of Tree:

Want to get started with Tree? You can try out our curated articles and lists for the best practice:

Graph:

A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a finite set of vertices and set of edges that connect a pair of nodes. Graph is used to solve the most challenging and complex programming problems. It has different terminologies which are Path, Degree, Adjacent vertices, Connected components, etc.

Characteristics of Graph:

Graph has various different characteristics which are as follows:

Applications of Graph:

Different applications of Graph are as follows:

Real-Life Applications of Graph:

Want to get started with Graph? You can try out our curated articles and lists for the best practice:

Conclusion

Although these are the most widely known and used data structures, there are some other forms of data structures as well which are used in Computer Science, such as policy-based data structures, etc. But no matter which data structure you choose, each one has its perks and disadvantages, without the knowledge of which, it can be very costly to choose the wrong type of data structure. So it is very important to understand the need of the situation, and then decide which kind of data structure suits best for the job.

Data Structure and Types

In this article, you will learn about data strucrture and its types.

What are Data Structures?

Data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

Depending on your requirement and project, it is important to choose the right data structure for your project. For example, if you want to store data sequentially in the memory, then you can go for the Array data structure.

Array data Structure Representation

Note: Data structure and data types are slightly different. Data structure is the collection of data types arranged in a specific order.

Types of Data Structure

Basically, data structures are divided into two categories:

Let’s learn about each type in detail.

Linear data structures

In linear data structures, the elements are arranged in sequence one after the other. Since elements are arranged in particular order, they are easy to implement.

However, when the complexity of the program increases, the linear data structures might not be the best choice because of operational complexities.

Popular linear data structures are:

1. Array Data Structure

In an array, elements in memory are arranged in continuous memory. All the elements of an array are of the same type. And, the type of elements that can be stored in the form of arrays is determined by the programming language.

To learn more, visit Java Array.

An array with each element represented by an index

2. Stack Data Structure

In stack data structure, elements are stored in the LIFO principle. That is, the last element stored in a stack will be removed first.

It works just like a pile of plates where the last plate kept on the pile will be removed first. To learn more, visit Stack Data Structure.

In a stack, operations can be perform only from one end (top here).

3. Queue Data Structure

Unlike stack, the queue data structure works in the FIFO principle where first element stored in the queue will be removed first.

It works just like a queue of people in the ticket counter where first person on the queue will get the ticket first. To learn more, visit Queue Data Structure.

In a queue, addition and removal are performed from separate ends.

4. Linked List Data Structure

In linked list data structure, data elements are connected through a series of nodes. And, each node contains the data items and address to the next node.

A linked list

Non linear data structures

Unlike linear data structures, elements in non-linear data structures are not in any sequence. Instead they are arranged in a hierarchical manner where one element will be connected to one or more elements.

Non-linear data structures are further divided into graph and tree based data structures.

1. Graph Data Structure

In graph data structure, each node is called vertex and each vertex is connected to other vertices through edges.

Graph data structure example

Popular Graph Based Data Structures:

2. Trees Data Structure

Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data structure, there can only be one edge between two vertices.

Tree data structure example

Popular Tree based Data Structure

Linear Vs Non-linear Data Structures

Now that we know about linear and non-linear data structures, let’s see the major differences between them.

Why Data Structure?

Knowledge about data structures help you understand the working of each data structure. And, based on that you can select the right data structures for your project.

This helps you write memory and time efficient code.

To learn more about the importance of data structure, visit Why Learn Data Structure?