Note_Tech

All technological notes.

Project maintained by simonangel-fong Hosted on GitHub Pages — Theme by mattgraham

DSA - Data Structure & Algorithms

Abstract Data Type: an abstraction of a data strucutre which provides only the interface to which a data structure must adhere to.
- The interfac does not give any specific details about how something should be implemented or in what programming langugae.

computer program
- a collection of instructions to perform a specific task.
- For this, a computer program may need to store data, retrieve data, and perform computations on the data.
data structure
- a named location that can be used to store and organize data.
- a way of arranging data on a computer so that it can be accessed and updated efficiently.
Data structure and data types are slightly different.
- Data structure is the collection of data types arranged in a specific order.
Algorithm
- a collection of steps to solve a particular problem.
Learning data structures and algorithms allow us to write efficient and optimized computer programs.

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.

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.

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.

stack

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

queue

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.

linked list

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.

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

graph

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

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

Linear Data Structures	Non Linear Data Structures
in sequential order, one after the other.	in non-sequential order (hierarchical manner).
All the items are present on the single layer.	The data items are present at different layers.
can traverse all the elements sequentially in a single pass.	requires multiple runs. might not be possible to traverse all the elements in a single pass.
The memory utilization is not efficient.	Different structures utilize memory in different efficient ways depending on the need.
Time complexity increase with the data size.	Time complexity remains the same.
Example: Arrays, Stack, Queue	Example: Tree, Graph, Map