Data Structures and Algorithms (DSA) are the foundational building blocks of computer science, forming the basis for efficient problem-solving and software development. Mastery of DSA is essential for any aspiring programmer or computer scientist, as it enables the design of optimized and scalable solutions across various applications. This project exemplifies my dedication to deepening my understanding of DSA by re-implementing core algorithms each time I learn a new programming language. Through this iterative practice, I have developed robust implementations in C, C++, Python, and Go, demonstrating my versatility and commitment to mastering these critical concepts.
I’ve broadly divided the project into 2 parts - Data Structures that include implementation of Linked List, Stacks, Queues, Tree, Graphs, Heaps and Tries. Followed by Algorithms that include implementation of various Searching and Sorting algorithms.
a data structure is a data organization, management, and storage format that enables efficient access and modification
A Linked List is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link/pointer) to the next node in the sequence.
Advantage of linked list over arrays is that linked lists are variable size hence, no restriction on number of elements at any point of time.
Disadvantage of linked list over arrays is that random access is not possible in linked list.
Application: File systems, hash collision prevention, gps systems, undo/redo functionality, polynomial representation.
Efficiency of different operations on linked list:
A Stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element. Stacks follow the LIFO (Last In First Out) methodology.
Advantage of stacks is that push and pop can be performed in O(1) providing efficient data access suitable for a wide range of applications.
Disadvantage of stacks is that access is limited only to the top and there exists a potential for overflow that is encountered usually during a recursive function call (state is stored in stack).
Applications: Recursive calls, expression evaluation, syntax parsing, infix to postfix conversion, bracket matching and memory management.
Efficiency of different operations on linked list:
Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows FIFO (First In First Out) methodology, i.e., the data item stored first will be accessed first.
Advantage of queues is that enqueue and dequeue can be performed in O(1) providing efficient data access suitable for a wide range of applications.
Disadvantage of queues is that access is limited only to the front and rear. Additionally, a maximum queue size must be defined before using the queue.
Applications: Disk scheduling, asynchronous data transfer between two processes, priority queue.
Efficiency of different operations on queues:
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are termed as vertices, and the links that connect the vertices are called edges. The breadth first search (BFS) and the depth first search (DFS) are the two algorithms used for traversing and searching a node in a graph. They can also be used to find out whether a node is reachable from a given node or not.
Advantage of graphs is that they help represent complex data, especially when relationship between entities is not straight forward. It also enables easy path finding, machine learning and social network modeling.
Disadvantage of graphs is that they are difficult to interpret, they are hard to scale and they lack standardization.
Applications: Social media analysis, network monitoring, internet of things (IOT).
Efficiency of different operations on graphs:
