Data structures and algorithms (DSA) goes through solutions to standard problems in detail and gives you an insight into how efficient it is to use each one of them. It also teaches you the science of evaluating the efficiency of an algorithm. This enables you to choose the best of various choices.
In computer programming terms, an algorithm is a set of well-defined instructions to solve a particular problem. Informally, an algorithm is nothing but a mention of steps to solve a problem. It takes a set of input and produces a desired output. For Example,
An algorithm to find largest of two numbers:
- Take two numbers as an input
- Compare number1 with number2 with '>'. If it is greater, then store number1 in another variable named max
- Else it is obvious that number2 is greater. So, store number2 in the variable max.
- Print the variable max.
This is how a algorithm looks like. It is independent of Programming languages. It is just a step-by-step solution to given a problem which could be understood by everyone.
Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every enterprise application uses various types of data structures in one or the other way.
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 upon the requirement, we can select a particular data structure.
For example, if you want to store data sequentially in the memory, then you can go for Array data structure
Remember these two simple equations:
- Related data + Permissible operations on the data = Data Structures
- Data structures + Algorithms = Programs
NOTE : Data structure and data types are slightly different. Data structure is the collection of data types arranged in a specific order.
Primitive Data Structure
- Pointer, etc.
Non-Primitive Data Structure
i) Linear Data Structure
- Linked Lists
ii) Non-linear Data Structure
A linear data structure has data elements connected to each other so that elements are arranged in a sequential manner and each element is connected to the element in front of it and behind it. This way, the structure can be traversed in a single run.
Linear data structures can be implemented easily as computer memory is also arranged in a linear manner.
One of the simplest data structures, an array is a collection of items that are stored sequentially. An array contains values or variables—known as “elements”—of the same data type and is of a fixed size, so you cannot change the size of an array. Each item in an array is indexed starting with 0.
Arrays are commonly used as structures for building other, more complicated data structures. They are also used for sorting algorithms.
A linked list stores a collection of items in a linear order. Each element, or node, in a linked list contains a data item, as well as a reference, or link, to the next item in the list. In Other words, Data elements are connected through a series of nodes and, each node contains the data items and address to the next node.
Linked lists are used for symbol table management in switching between programs using Alt + Tab (On a PC).
Multiplayer games use a circular list to swap between players in a loop.
A stack stores a collection of items in the linear order that operations are applied. This order could be last in, first out (LIFO) or first in, Last out (FILO). 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.
You can “push” a new element onto the top of the stack, or you can “pop,” deleting the element inserted last which is at the top of the stack.
Stacks can be used for Memory Management.
Stack data structures are used in backtracking problems.
A queue functions similarly to a stack, but instead of being a LIFO structure, it is a FIFO (First In First Out) structure. The easiest way to think about a queue is to think of a line of people waiting to enter a building. The person at the beginning of the line will enter the building first, while the person at the end will enter last.
You can enqueue an element in this structure, which means inserting the element to the end of the queue. You can also dequeue an element, which means deleting an element from the beginning of the queue.
In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
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.
As the arrangement is non-sequential, so the data elements cannot be traversed or accessed in a single run. In the case of linear data structure, element is connected to two elements (previous and the next element), whereas, in the non-linear data structure, an element can be connected to more than two elements.
It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parent-child relationship. In graph data structure, each node is called vertex and each vertex is connected to other vertices through edges. It is a collection of nodes that have data and are connected to other nodes.
The diagrammatic representation of a graph data structure looks like:
Google maps uses graphs for building transportation systems, thus their navigation system is based on the algorithm to calculate the shortest path between two vertices.
Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example of undirected 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. Each node is associated with a key value, with parent nodes linked to child nodes or sub nodes. There is one root node that is the ancestor of all the nodes in the tree.
Binary search trees are used in many different types of search applications. Other types of trees are used in wireless networking and to create expression solvers.
- Hash Table
A hash table also known as a hash map stores a collection of items in an associative array that plots keys to values. A hash table uses a hash function to convert an index into an array of buckets that contain the desired data item.
A heap is a tree-based structure in which each parent node's associated key value is greater than or equal to the key values of any of its children's key values.
A Trie is an advanced data structure that is sometimes also known as prefix tree or digital tree. It is a tree that stores the data in an ordered and efficient way. We generally use trie's to store strings.
Knowledge about data structures help you understand the working of each data structure. This helps you write memory and time efficient code.
This is my first post. Please let me know your valuable feedbacks.
Thank You! :)