×

Search anything:

Data Structures (DS) and Quick Revision

Data Structures

Get this book -> Problems on Array: For Interviews and Competitive Programming

Data structures are a fundamental concept in computer science that provides a way to organize and store data in a computer so that it can be accessed and modified efficiently.

A data structure is a specific way of organizing and storing data in a computer so that it can be accessed and modified efficiently.

When data is unstructured, it is not organized or doesnâ€™t have a defined data model.

Types of Data Structures

There are many different data structures are out there, but all can be classified in these two.
1.primitive data structure, also known as built-in data types can store the data of only one type. Examples - integers, floating points, characters, pointers.

1. 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. also known as derived data types.

have a look -

as you can see - non-primitive data structures are further classified into linear and non-linear.
Linear data structures are again categorized based on whether they are static or dynamic.

have a look at Linear Vs Non-Linear

Linear Data Structure- are structures that are organized in a linear way, meaning that the elements are stored in a sequential manner, one after the other. Examples of linear data structures include arrays, linked lists, and stacks.

Static DS is a data structure that has a fixed size and does not change once it has been created. This means that you cannot add or remove elements from a static data structure after it has been created. Examples - arrays and static lists.

Dynamic DS is a data structure that can change size during the execution of a program. This means that you can add or remove elements from a dynamic data structure as needed. Examples - linked lists, stacks, and queues.

Static DS are typically easier to implement and are more efficient when it comes to accessing elements, but they can be less flexible than dynamic data structures. Dynamic DS are more flexible, but they may require more memory and may be less efficient when it comes to accessing elements.

Non-linear data structures are structures that are not organized in a linear way, meaning that the elements are not stored in a sequential manner. Examples of non-linear data structures include trees, graphs, and hash tables.

Linear data structures are typically easier to understand and implement, but they may not be as efficient as non-linear data structures when it comes to searching, inserting, and deleting elements. Non-linear data structures are usually more complex, but they can provide faster access to elements and allow for more efficient operations.

Most common types of data structures and there properties

1.Arrays

An array is a data structure that stores a collection of elements of the same data type. The elements in an array are accessed by their indices, which are integer values that specify the position of an element in the array.

A linked list is a linear data structure that consists of a sequence of nodes, where each node stores a reference to an object and a reference to the next node in the sequence. The first node in the linked list is called the head, and the last node is called the tail.

3. Queues

A queue is a type of data structure that stores a collection of elements in a linear order, and follows the principle of First In First Out (FIFO). This means that the first element added to the queue will be the first one to be removed.
There are two main operations that can be performed on a queue: enqueue and dequeue. Enqueue adds an element to the end of the queue, and dequeue removes the element from the front of the queue.

real life example

4. Stack

A stack is a type of data structure that stores a collection of elements in a linear order, and follows the principle of Last In First Out (LIFO). This means that the last element added to the stack will be the first one to be removed.
There are two main operations that can be performed on a stack: push and pop. Push adds an element to the top of the stack, and pop removes the element from the top of the stack.

real life example

5. Trees

A tree is a hierarchical data structure that consists of nodes arranged in a tree-like structure. Each node has a value, and it can have zero or more child nodes, which are represented as a list of pointers to the child nodes. The nodes that do not have any children are called leaf nodes. The node at the top of the tree is called the root node.

Trees have a number of important properties, including:

Hierarchical structure: The nodes in a tree are organized into a hierarchy, with the root node at the top and the leaf nodes at the bottom.
Parent-child relationships: Each node in a tree has a parent node (except for the root node) and zero or more child nodes.
Siblings: Nodes that have the same parent are called siblings.

There are many different types of trees, including binary trees, binary search trees, red-black trees, and AVL trees. Each type of tree has its own unique characteristics and is used in different situations.

Question

'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?
Graphs
Trees
Arrays
As you can see below a graph have one node connected to multiple and same for each node, you can call it mutual connection.

6. Graphs

A graph (G) is a non-linear data structure that consists of a set of vertices (also called nodes) and a set of edges (E) that connect the vertices. Each edge has a weight that represents the cost or distance between the two vertices it connects.

There are two main types of graphs:

Directed graph : also called digraph, edges have direction.
Undirected graph : edges do not have any direction.

Each vertex in a graph can represent anything, such as a city in a map, a person in a social network, or a web page on the internet. And edges represent the relationship between the vertices, such as the distance between two cities, the connection between two people in a social network, or the link between two web pages on the internet.

Graphs are used in a wide variety of applications such as:

• Network design and analysis.
• Modeling social and communication networks.
• Representing chemical compounds.
• Representing computational problems.
• Representing the relationships in databases.
• Modeling transportation systems.

There are many algorithms that can be used to process and analyze graphs, such as Breadth-first search (BFS) and Depth-first search (DFS), shortest path algorithms like Dijkstra's algorithm, and Minimum Spanning Tree algorithms like Kruskal's Algorithm and Prim's algorithm.

7. Heaps
A heap is a specific type of binary tree where the parent nodes are compared to their child nodes, and values are arranged in the nodes accordingly.

It is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.

A heap can be represented as an array or a binary tree as you can see in the images below:

There are two types of heaps:

1.Min heap, where the parentâ€™s key is equal or less than the keys of its children.
2.Max heap, where the parentâ€™s key is greater than the keys of its children.

With this article at OpenGenus, you must have a good revision of basic Data Structures.