Data Structure & Algorithms
A data structure is a programmatic way of storing data so that it can be used efficiently. Almost all enterprise applications use some data structure in some way. This tutorial will give you a thorough understanding of the complexity of an enterprise-level application and the data structures necessary to understand the need for algorithms and data structures.
Data Structure is a way to organize data in a very convenient way so that it can be used very effectively.
It includes data structures like arrays, pointers, linked lists, stacks, heaps, graphs, trees, etc.
Algorithms like sorting, searching, and many more make such algorithms that complex tasks efficient.
Data Structures are used to store, search and manipulate data stored in the memory.
Do check the above-mentioned blog post, to get the basic and complete overview of Data Structures and their types along with the time and space complexity.
In this blog/article we will discuss about – Algorithms, Major Operations Performed on Data Structures, Types, Structures, array and linked list.
Algorithms –
It is just like a set of rules and instructions which needs to be followed in calculations or other problem-solving operations.
A set of step-by-step procedures, or a set of riles to follow.
There are various types pf algorithms depending upon the type of operations to be performed –
Searching – Such algorithms are used to find any specific data withing he larger dataset. There are various searching algorithms, which is used for searching and data. And each algorithms have their own special characterises and workflow.
Linear Search – It is also knowing as sequential search. Linear Search is one of the slow algorithms as it checks each item present in a list or in an array one at a time. That means it keeps checking them data at first place, then at second place, and moves forward until it finally finds the target value.
Binary Search - Binary Search is more efficient than linear search as binary search is applied to the sorted array or a list. It works by dividing the array into two parts and checking whether the targeted value is present in the first half or in the second half. It eliminates the second-half in which the targeted value is not present and again divides the first half until the midpoint becomes the targeted value.
There 2 are the most common and basic searching algorithms used in the data structures. Apart from these there are several other searching algorithms present in DSA
Jump Search
Exponential Search
Hash Search
Interpolation Search
Sorting – Sorting algorithms sorts data into a specific order either into ascending order or descending order for numerical data. Or simply sorting algorithm sorts the data into and defined chronological orders. The most common sorting algorithms are.
Bubble Sort - Bubble sort is simple to implement, but it is slow and ineffective for large dataset. This algorithm works by repeatedly swapping adjacent elements in an array or list if they are placed in the wrong order.
Insertion Sort - Insert and short works by inserting each element. In our list or array into its proper place in a sorted list. It is very effective for small datasets, but just like bubble sort, it is also ineffective for large datasets.
Selection Sort – It is also slow and inefficient for large datasets.
Merge Sort – It is more efficient than bubble, insertion and selection sort for larger dataset. It works by dividing a lost or array into smaller sub lists, sorting those and then merging them back together.
Quick Sort – It uses the concept of recursion to solve the problem. It is more efficient than merge sort for smaller datasets but can be less efficient for lager datasets.
Heap Sort - It is more efficient than bubble, insertion, and selection sort for larger datasets.
There are more such sorting algorithms, which can be used to solve a problem.
Recursive Algorithms
Machine Learning Algorithms
Encryption & Decryption Algorithms
These are some algorithms used in Data Structures. Each algorithms have their own functionality and working. There are more such algorithms designed for different types of operations.
Data structures can also be classified as –
Static data structure - It is a type of data structure where the size is allocated at the compile time. Therefore, the maximum size is fixed.
Dynamic data structure - It is a type of data structure where the size is allocated at the run time. Therefore, the maximum size is flexible.
Major Operations –
The major or common operations that can be performed on the data structures are:
Searching - We can search for any element in a data structure.
Sorting - We can sort the elements of a data structure either in an ascending or descending order.
Insertion - We can also insert a new element in a data structure.
Updation - We can also update the element, i.e., we can replace the element with another element.
Deletion - We can also perform the delete operation to remove the element from the data structure.
Types of Data Structures –
Primitive Data Structures – These are primitive data types, which can hold single value. Ex, int, char, float, double, pointer.
Non – primitive Data Structure – It is further divided into 2 sub-groups –
Linear Data Structures – Such types of data structures stores data in the arranged and sequential manner.
Array – It is a collection of data elements of the same type that are stored in contiguous memory location.
Linked List – It is quite similar to the array, but it stored the data in a form of nodes where each node is connected to its subsequent node.
Stacks – It is a collection of elements that are arranged in a first-in, first-out order (LIFO). Elements/Data can be added or removed only from the top of the stack.
Queues - A queue is a collection of elements that are arranged in a first-in, first-out (FIFO) order. Elements can be added to the back of the queue and removed from the front.
More such Linear data structures are vectors and strings.
Non – Linear Data Structures -In a non-linear arrangement, the data elements are not arranged in sequential structure, i.e., this data structure does not form a sequence and each item or element is connected with two or more other items.
Trees - A tree is a collection of nodes that are connected by edges. Each node can have any number of children, but only one parent. Trees are commonly used to represent hierarchical relationships.
Graph - A graph is a collection of nodes, called vertices, that are connected by edges. Each edge can have a weight or cost associated with it. Graphs are commonly used to represent complex relationships, such as social networks or transportation networks.
Hash tables - A hash table is a data structure that maps keys to values using a hash function. Hash tables are commonly used to implement dictionaries, databases, and caches.
There are more such non-linear data structures which we will discuss in more details in the subsequent articles.
Structures
Structure is a user-defined data type that can group together variables of different data types under a single name. syntax –
struct structure_name
{
data_type member1;
data_type member2;
.
data_type memeber;
};
Advantages
It can hold variables of different data types.
We can create objects containing different types of attributes.
It allows us to re-use the data layout across programs.
It is used to implement other data structures like linked lists, stacks, queues, trees, graphs etc.
Example –
Array
It is a collection of data elements of the same type that are stored in contiguous memory location.
An array is a data structure that can store a fixed-size sequence of elements of the same data type.
Syntax & Representation –
As per the above illustration, there are some of the following important points –
Index starts with 0.
The array's length is 10, which means we can store 10 elements.
Each element in the array can be accessed via its index.
Example –
Memory allocation in array –
When an array is declared in a program, the system reserves a block of memory to hold the elements of the array.
The size of the memory block depends on the number of elements in the array and the size of each element.
In statically allocated arrays, the memory for the array is allocated at compile time, and the size of the array is fixed. The memory is typically allocated on the stack or in the global data segment of the program.
In dynamically allocated arrays, the memory for the array is allocated at runtime using functions
Basic Operations –
Traversal - This operation is used to print the elements of the array.
Insertion - It is used to add an element at a particular index.
Deletion - It is used to delete an element from a particular index.
Search - It is used to search an element using the given index or by the value.
Update - It updates an element at a particular index.
Time Complexity –
Advantage of using array –
Array provides a single name for a group of variables of the same type. Therefore, it is easy to remember the name of all the elements of an array.
Traversing an array is a very simple process; we just need to increment the base address of the array in order to visit each element one by one.
Any element in the array can be directly accessed by using the index.
Disadvantages of Array –
The array is homogenous. It means that elements with similar data types can be stored in them.
In an array, there is static memory allocation that is the size of an array cannot be altered.
There will be a wastage of memory if we store less number of elements than the declared size.
Linked List
A linked list is a data structure consisting of a sequence of nodes, each containing data and a reference (or "link") to the next node in the sequence. The first node in the list is called the head and the last node is called the tail.
Representation of Linked List –
A linked list is typically represented using nodes, where each node contains a data element and a reference (or "link") to the next node in the list.
Why use linked list over array?
Linked lists and arrays are both commonly used data structures, but each has its own strengths and weaknesses. Here are some reasons why you might choose to use a linked list over an array:
Dynamic Size
Insertion and Deletion
Memory Efficiency
Flexibility
Limitations of Array –
The size of the array must be known in advance.
Increasing the size of the array is a time taking process.
Inserting an element in the array needs shifting of all its predecessors.
Declaration of a linked list –
Linked list contains two parts, and both are of different types, one is a simple variable and the another is the pointer variable. Linked list can be declared by using the structure (it is a user-defined data type).
The “Node” struct has two members “data”, which holds the value of the node, and “next”, which is a pointer to the next node in the list. The “head” pointer is initially set to “NULL”, indicating that the list is empty.
Types of Linked list
Singly-linked list - A singly linked list is a type of linked list where each node only has a next pointer that points to the next node in the list. This is the simplest and most common type of linked list.
Doubly-linked list - In a doubly linked list, each element contains references to both the next and previous elements in the sequence. This allows for more efficient traversal in both directions, but requires more memory to store the additional references.
Circular singly linked list - In a circular singly linked list, each node has a data element and a pointer to the next node in the list. The pointer of the last node in the list points back to the first node, forming a cycle.
Circular doubly linked list - In a circular doubly linked list, each node has three fields: the data element, a pointer to the next node in the list, and a pointer to the previous node in the list. The pointers of the first and last nodes are adjusted to point to each other, creating the circular structure
Operations performed on Linked List
Insertion
Deletion
Display
Search
Time Complexity –
Space Complexity –
In the next blog/article we will learn about Linked List and its type and their implementation in more details.
It will help you to understand the concept of Competitive Programming and DSA.