Data Structure and Algorithms with Python
What is Data Structure ?
In terms of computer, a data structure is a Specific way to store and organize data in a computer's memory so that these data can be used efficiently later. Data may be arranged in many different ways, such as the logical or mathematical model for a particular organization of data is termed as a data structure.
Types of Data Structure
The data structure can be subdivided into major types:
1. Primitive Data Structure
2. Non-Primitive Data Structure - it is also divided into 2 types :
Linear Data Structure
Non-Linear Data Structure
Primitive Data Structure
The Primitive Data Structure are the programming language defined data structures which are built into the programming language itself , which programmers can readily use in the program.
Types of Primitive Data Structure
1. Integer - It is used to represent a number without decimal point.
Ex - 1,30,50
2. Float - It is used to represent a number with decimal point.
Ex - 5.2, 3.45, 50.32
3. Character - It is used to represent single character.
Ex - A, B ,G
4. String - It is used in programming, such as an integer and floating point unit, but is used to represent
text rather than numbers.
Ex - " Data Science World "
5. Double - It is used to define numeric variables holding numbers with decimal points.
Ex - 3.146 , -5.234
Non-Primitive Data Structure
The Non-Primitive Data Structure are user defined data structures which are also referred as user defined data structures and they are not pre-defined in programming language.
Types of Non-Primitive Data Structure
1. Linear Data Structure
A data structure is said to be linear if its elements combine to form any specific order. There are two techniques of representing such linear structure within memory.
The first way is to provide the linear relationships among all the elements represented using linear memory location. These linear structures are termed as arrays.
The second technique is to provide a linear relationship among all the elements represented by using the concept of pointers or links. These linear structures are termed as linked lists.
The common examples of the linear data structure are:
1. Arrays - An array is a data structure that contains a group of elements. Typically these elements are all of the same data type, such as an integer or string.
2. Queues - queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.It is also Known as First In First Out (FIFO).
3. Stacks - stack is an abstract data type that serves as a collection of elements, with two main principal operations : Push and POP. It is also called Last In First Out(LIFO).
4. Linked lists - inked list is a linear collection of data elements whose order is not given by their physical placement in memory.
2. Non-Linear Data Structure
This structure is mostly used for representing data that contains a hierarchical relationship among various elements.
Examples of Non-Linear Data Structures are listed below:
1. Graphs
2. Trees
Tree: In this case, data often contain a hierarchical relationship among various elements. The data structure that reflects this relationship is termed as a rooted tree graph or a tree.
Graph: In this case, data sometimes hold a relationship between the pairs of elements, which is not necessarily following the hierarchical structure. Such a data structure is termed as a Graph.
Operation on Data Structure
• Traversing
– Traversal is a process of visiting each and every node of a list in systematic manner.
• Updation
– It updates or modifies the data in the data structure.
• Searching
– To search for a particular value in the data structure for the given key value.
• Sorting
– To arrange the values in the data structure in a particular order.
• Inserting
– To add a new value to the data structure
• Deleting
– To remove a value from the data structure
• Splitting
– Splitting is a process of partitioning single list to multiple list.
• Merging
– To join two same type of data structure values
Stack
A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first.
LIFO Principle of Stack
In programming terms, putting an item on top of the stack is called push and removing an item is called pop.
Working of Stack Data Structure
The operations work as follows :
1. A pointer called TOP is used to keep track of the top element in the stack.
2. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.
3. On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.
4. On popping an element, we return the element pointed to by TOP and reduce its value.
5. Before pushing, we check if the stack is already full.
6. Before popping, we check if the stack is already empty.
Queue
A queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.
Queue follows the First In First Out (FIFO) rule - the item that goes in first is the item that comes out first.
In programming terms, putting items in the queue is called enqueue, and removing items from the queue is called dequeue.
Working of Queue :
Enqueue Operation
1. check if the queue is full
2. for the first element, set the value of FRONT to 0
3. increase the REAR index by 1
4. add the new element in the position pointed to by REAR
Dequeue Operation
1. check if the queue is empty
2. return the value pointed by FRONT
3. increase the FRONT index by 1
4. for the last element, reset the values of FRONT and REAR to -1
Four different types of queues:
1. Simple Queue - Insertion takes place at the rear and removal occurs at the front.
2. Circular Queue - The last element points to the first element making a circular link.
3. Priority Queue - Element is associated with a priority and is served according to its priority.
4. Double Ended Queue - Insertion and removal of elements can be performed from either from the front or rear.
Linked List
A linked list is a linear data structure that includes a series of connected nodes. Here, each node store the data and the address of the next node. For example,
You have to start somewhere, so we give the address of the first node a special name called HEAD. Also, the last node in the linked list can be identified because its next portion points to NULL.
Linked list operation you can visit here to read more : https://www.programiz.com/dsa/linked-list-operations
Time complexity
Worst case Average Case
1. Search O(n) O(n)
2. Insert O(1) O(1)
3. Deletion O(1) O(1)
Types of linked list
1. Singly Linked List - Each node has data and a pointer to the next node.
2. Doubly Linked List - We add a pointer to the previous node in a doubly-linked list. Thus, we can go in either direction: forward or backward.
3. Circular Linked List - A circular linked list is a variation of a linked list in which the last element is linked to the first element. This forms a circular loop.
Hashing Data Structure
The Hash table data structure stores elements in key-value pairs where
Key- unique integer that is used for indexing the values
Value - data that are associated with keys.
Hashing (Hash Function)
In a hash table, a new index is processed using the keys. And, the element corresponding to that key is stored in the index. This process is called hashing.
Let k be a key and h(x) be a hash function.
Here, h(k) will give us a new index to store the element linked with k.
To deep dive into it visit : https://www.geeksforgeeks.org/hashing-data-structure/
Heap Data Structure
Heap data structure is a complete binary tree that satisfies the heap property, where any given node is
Always greater than its child node/s and the key of the root node is the largest among all other nodes. This property is also called max heap property.
Always smaller than the child node/s and the key of the root node is the smallest among all other nodes. This property is also called min heap property.
Heapify
Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap.
1. Let the input array be
2. Create a complete binary tree from the array
3. Start from the first index of non-leaf node whose index is given by n/2 - 1.
4. Set current element i as largest.
5. The index of left child is given by 2i + 1 and the right child is given by 2i + 2.
If leftChild is greater than currentElement (i.e. element at ith index), set leftChildIndex as largest.
If rightChild is greater than element in largest, set rightChildIndex as largest.
6. Swap largest with currentElement.
7. Repeat steps 3-7 until the subtrees are also heapified.
Tree Data Structure
A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.
Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. But, it is not acceptable in today's computational world.
Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.
Tree Traversal
In order to perform any operation on a tree, you need to reach to the specific node. The tree traversal algorithm helps in visiting a required node in the tree.
Types of Tree traversal
1 . Inorder traversal
First, visit all the nodes in the left subtree
Then the root node
Visit all the nodes in the right subtree
2. Preorder traversal
Visit root node
Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
3. Postorder traversal
Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
Visit the root node
Types of Tree
1. Binary Tree - A binary tree is a tree data structure in which each parent node can have at most two children. Each node of a binary tree consists of three items:
data item , address of left child , address of right child.
Types of Binary Tree -
1. Full Binary Tree
2. Perfect Binary Tree
3. Complete Binary Tree
4. Degenerate or Pathological Tree
5. Skewed Binary Tree
6. Balanced Binary Tree
2. Binary Search Tree - Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.
It is called a binary tree because each tree node has a maximum of two children.
It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.
The properties that separate a binary search tree from a regular binary tree is
1. All nodes of left subtree are less than the root node
2. All nodes of right subtree are more than the root node
3. Both subtrees of each node are also BSTs i.e. they have the above two properties
for more detail : https://www.geeksforgeeks.org/binary-search-tree-data-structure/
3. AVL Tree - AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.
4. B-Tree - B-tree is a special type of self-balancing search tree in which each node can contain more than one key and can have more than two children. It is a generalized form of the binary search tree.
It is also known as a height-balanced m-way tree.
Operations on a B-tree
Searching an element in a B-tree
Searching for an element in a B-tree is the generalized form of searching an element in a Binary Search Tree. The following steps are followed :
1. Starting from the root node, compare k with the first key of the node.
If k = the first key of the node, return the node and the index.
2. If k.leaf = true, return NULL (i.e. not found).
3. If k < the first key of the root node, search the left child of this key recursively.
4. If there is more than one key in the current node and k > the first key, compare k with the next key in the node.
If k < next key, search the left child of this key (ie. k lies in between the first and the second keys).
Else, search the right child of the key.
5. Repeat steps 1 to 4 until the leaf is reached.
Best case Time complexity: Θ(log n)
Worst case Time complexity: Θ(log n)
To know more about DSA or on any specific topic you can visit :
https://www.geeksforgeeks.org/
https://www.w3schools.in/data-structures-tutorial/intro/
NOTE : Code implementation on each algorithm is available on my github link , here i have given a button ( Link ) just click there you will be get redirected and you can use all the code from there and also you can download it.
Conclusion : Now it's your turn guys to do hand's on with python on all the topic covered above .
Follow me on LinkedIn : https://www.linkedin.com/in/vaibhav-shah-704104212/
Your feedback is appreciated!
Did you find this Blog helpful? Any suggestions for improvement? Please let me know by filling the contact us form or ping me on LinkedIn .
Thanks!