Data Structures are specialized methods of organizing and storing data in computers in such a way that operations on the stored data can be performed more efficiently. Data structures have a wide and diverse range of applications in computer science and software engineering.
Almost every programmer or software system that has been developed makes use of data structures. Furthermore, data structures are fundamentals of computer science and software engineering. When it comes to Software Engineering interview questions, this is a critical topic. As a result, as developers, we must be well-versed in data structures.
In this article, I'll go through 8 commonly used data structures and algorithms that every programmer should be familiar with.
1. Arrays:
An array is a fixed-size structure that can hold items of the same data type. It can be an array of integers, a floating-point number array, a string array, or even an array of arrays (such as 2-dimensional arrays). Arrays are indexed, which means they can be accessed at random.
Array Operations
1. Traverse
2. Search
3. Update
Because arrays are fixed in size, adding and removing elements from them cannot be done immediately. If you want to add an element to an array, you must first create a new array with a larger size (current size + 1), copy the existing elements, and then add the new element. The same is true for the deletion with a smaller array.
Arrays Implementation
1. Arrays are used to construct data structures such as array lists, heaps, hash tables, vectors, and matrices.
2. Used in various sorting algorithms, such as insertion sort, quick sort, bubble sort, and merge sort.
2. Linked List:
A linked list is a sequential structure that consists of a series of items. These items are linked to each other in a linear order. As a result, you must access data sequentially. In a linked list, random access is not possible. Linked lists are a simple and adaptable way to represent dynamic sets.
Consider the following terms in relation to linked lists. The below figure will give you a good idea of what I'm talking about.
1. Nodes are the elements of a linked list.
2. Each node has a key and a pointer to the node that comes after it, known as next.
3. The head attribute points to the first element of the linked list.
4. The tail is the final element of the linked list.
Operations on linked lists
I. Search: Using a simple linear search, find the first entry in the given linked list with the key k and return a pointer to that element.
II. Insert: To the linked list, add a key. Insertion can be done in one of three ways: at the start of the list, at the end of the list, or in the middle of the list.
III. Delete: Removes a provided linked list entry x. A node cannot be deleted in a single step. A deletion can be performed in one of three ways: from the start of the list, from the end of the list, or from the middle of the list.
3. Stacks
A stack is a Last In First Out (LIFO) (Last In First Out – the element placed last can be accessed first) structure found in many programming languages. Because it resembles a real-world stack — a stack of plates — this form is called "stack."
Stack operations
The two basic operations that can be performed on a stack are listed below.
Push: Push an element to the very top of the stack.
Pop: Remove the topmost element and replace it with a new one.
4. Queues
A queue is a popular FIFO (First In First Out – the element placed first can be accessed first) structure seen in many programming languages. Because it resembles a real-world queue — individuals waiting in a line — this structure is called a "queue."
Operations involving queues
Enqueue: Add a new element to the queue's end.
Dequeue: Remove the element from the queue's beginning.
5. Hash Tables
1. To circumvent the aforementioned difficulty in direct addressing. A special function called the hash function (h) is used.
2. A value with key p is stored in the slot p in direct accessing. We calculate the index of the table (slot) to which each value belongs using the hash function. The hash value for a particular key is the value calculated using the hash function, and it shows the index of the table to which the value is mapped.
h (p) = p%m
6. Trees
A tree is a hierarchical structure in which data is structured and linked in a hierarchical manner. This structure differs from that of a linked list, in which elements are linked in a linear order.
Various sorts of trees have been developed over the years to suit specific uses and to meet specific needs. Binary search tree, B tree, treap, red-black tree, splay tree, AVL tree, and n-ary tree are some examples.
Applications of trees:
Binary Trees: Binary Trees are used to create expression parsers and solvers.
Binary Search Tree: This is a type of search tree that is utilized in many backend development applications where data is continually entering and exiting.
Heaps: JVM (Java Virtual Machine) uses heaps to store Java objects.
Treaps: Treaps are a type of wireless networking protocol.
7. Heaps
A heap is like a binary tree in which the parent nodes' values are compared to those of their offsprings and the nodes are sorted accordingly.
There are two types of heaps.
Min Heaps: The parent's key is less than or equal to that of its children in the Min Heap. The heap's minimum value will be stored in the root.
Max Heap: The parent's key is greater than or equal to the children's. The heap's maximum value will be stored in the root.
8. Graphs:
1. A graph is made up of a finite number of vertices or nodes and a set of edges that connect them.
2. The number of vertices in a graph determines its order. The number of edges in a graph determines its size.
3. When two nodes are connected by the same edge, they are said to be adjacent.
Applications of Graphs:
1. It's a symbol for social media networks. Each user is a vertex, and when they join, an edge is created.
2. Search engines use this to represent web pages and links. Hyperlinks are used to connect websites on the internet. A vertex is a page, while an edge is a link between two pages. In Google, it's used to rank pages.
3. GPS, it's used to represent locations and routes. Locations are vertices, and the paths that connect them are edges. Calculates the shortest distance between two points.
0 Comments