Data Structures

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 a particular way of organizing data in a computer so that it can be used efficiently.

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 characteristics, features, applications, advantages, and disadvantages.

Data Types vs Data Structures

Data Type	Data Structure
The data type is the form of a variable to which a value can be assigned. It defines that the particular variable will assign the values of the given data type only.	Data structure is a collection of different kinds of data. That entire data can be represented using an object and can be used throughout the program.
It can hold value but not data. Therefore, it is dataless.	It can hold multiple types of data within a single object.
The implementation of a data type is known as abstract implementation.	Data structure implementation is known as concrete implementation.
There is no time complexity in the case of data types.	In data structure objects, time complexity plays an important role.
In the case of data types, the value of data is not stored because it only represents the type of data that can be stored.	While in the case of data structures, the data and its value acquire the space in the computer’s main memory. Also, a data structure can hold different kinds and types of data within one single object.
Data type examples are int, float, double, etc.	Data structure examples are stack, queue, tree, etc.

Summary

*Some of these are amortized, not worst-case.

Structure	find	insert/remove	Comments
Array	O(n)	can’t do it	Constant-time access by position
Stack	top only O(1)	top only O(1)	Easy to implement as an array.
Queue	front only O(1)	O(1)	insert rear, remove front.
ArrayList	O(N), O(log N) if sorted	O(N)	Constant-time access by position Add at end: am. O(1), worst O(N)
Linked List	O(N)	O(1)	O(N) to find insertion position.
HashSet/Map	O(1)	amort. O(1), worst O(N)	Not traversable in sorted order
TreeSet/Map	O(log N)	O(log N)	Traversable in sorted order
PriorityQueue	O(1)	O(log N)	Can only find/remove smallest
Search Tree	O(log N) O(log N)	If tree is balanced, O(N) otherwise

Classification

                                      ┌───────────────────────┐
                                      │    Data Structure     │
                                      └────────────┬──────────┘
                                                   │
                             ┌─────────────────────┴────────────────────────┐
                             │                                              │
                  ┌──────────┴────────────┐                     ┌───────────┴───────────┐
                  │     Linear            │                     │  Non linear           │
                  └──────────┬────────────┘                     └───────────┬───────────┘
                             │                                              │
                             │                                              │
                             │                                              │
                             │                                              │
             ┌───────────────┴─────────────┐                          ┌─────┴────────────────────────┐
             │                             │                          │                              │
 ┌───────────┴───────────┐    ┌────────────┴──────────┐   ┌───────────┴───────────┐    ┌─────────────┴─────────┐
 │    Static             │    │   Dynamic             │   │     Tree              │    │   Graph               │
 └───────────┬───────────┘    └─┬─────────────────────┘   └───────────────────────┘    └───────────────────────┘
             │                  │
             │                  │
             │                  │
             │                  │
┌────────────┴──────────┐       │    ┌───────────────────────┐
│  Array                │       ├────┤  Queue                │
└───────────────────────┘       │    └───────────────────────┘
                                │
                                │
                                │    ┌───────────────────────┐
                                ├────┤ Stack                 │
                                │    └───────────────────────┘
                                │
                                │
                                │    ┌───────────────────────┐
                                └────┤ LinkedList            │
                                     └───────────────────────┘

1. Linear data structure: Data structure in which data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements. e.g. array, stack, queue, linked list, etc.
   1. Static data structure: Fixed memory size. It is easier to access the elements in a static data structure. e.g. array
   2. Dynamic data structure: The size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code. e.g. queue, stack, etc.
2. Non-linear data structure: Data elements are not placed sequentially or linearly. We can’t traverse all the elements in a single run. e.g. trees and graphs

Reading material

1. https://www.geeksforgeeks.org/what-is-data-structure-types-classifications-and-applications/?ref=leftbar-rightbar

Tags

1. Collections