Data Structures
What are Data Structures?
Data Structures are components that are used to help organize and store data. They provide a way to manage and manipulate data effectively, enabling faster access, insertion, and deletion operations.
Arrays
Arrays are a data structure that stores a collection of elements or indexes of the same data type.
- Fixed Size
- Contiguous memory allocation
- Constant time complexity (O(1)) for accessing elements by index
Linked List
A Linked List is a collection of elements called nodes where each node has data and points to the next node in a sequence.
- Dynamic size
- Efficient insertions/deletions (O(1) if the position is known)
- Can be singly linked (one reference per node) or doubly linked (two references per node: next and previous) or circular linked list (not really important but its just a singly linked list but all nodes are connected to each other in a circle.
Stacks
A Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last in First Out) or FILO (First In Last Out).
- Elements are added (pushed) and removed (popped) from the same end, called the top.
- Common operations: push, pop, peek (or top), and isEmpty
Queues
A Queue is a linear structure which follows a particular order in which the operations are performed in the First In First Out (FIFO).
- Elements are added (enqueued) at the back and removed (dequeued) from the front.
- Common operations: enqueue, dequeue, front, and isEmpty
Hash-Tables
A Hash Table is a data structure that stores values which have keys associated with each of them. Collisions are quite common so to avoid these collisions you can uses processes like Chaining and Open.
- Chaining is a technique is used for avoiding collisions in has tables by making the hash table an array of linked list i.e., each index has its own linked list.
- Open addressing is a method for handling collisions with all elements are stored in the hash table itself.
Trees
A Tree a hierarchical structure where data is organized hierarchically and are linked together.
Types of Trees:
- binary search tree
- B tree
- treap
- red-black tree
- splay tree
- n-ary tree
Graphs
A graph consists of a finite set of vertices or nodes and a set of edges connecting these vertices.
Types of Graphs:
- Undirected Graph: a graph that doesn't have a directed direction so it can go any route
- Directed Graph: a graph that has set directions.
- Complete Graph: a graph where all edges are connected