Data Structure Operations

  • We have covered the basics of DSA and different types of Data Structures. Now, let us go through the most important set of operations that needs to be performed on data structures.

    As we learned, data structures are helpful to store huge amount of data efficiently in a structured manner. But efficiency of data structures does not depend on storage alone. We need efficient algorithms to perform the data structure operations in the most optimized manner as well.

    Based on the difference of approach, we can classify the basic data structure operations as below.

    1. Search
    2. Traversal
    3. Sort
    4. Insert, Update, Delete
    5. Merge, Split, Slice

    Let us further understand each of these in detail below.

  1. Data Structure Search

    Searching is one of the most important and and most performed operations on a data structure. Searching means navigating through a data structure and finding all matching items.

    For different types of data structures, we have to follow different approaches for search. For linear data structures, we can do a sequential search or an interval search.

    For a non-linear data structures like a Tree or a Graph, we have algorithms like Breadth First Search (BFS) or Depth First Search (DFS).

    We have to us the right search option considering many factors like type of data structure, amount of data, etc. For example, interval search is much faster compared to sequential search for an array especially when the amount of data is huge. No need to worry about it now, we will learn these in detail in the upcoming sessions.

    Below is a simple program written in Python that does a sequential search on an array.

    Copied 
    arry = [5, 12, 15, 18, 40, 30, 22, 45, 8, 34]

find = 40
pos = -1

for i in range(len(arry)):
    if(arry[i] == find):
        pos = i
        break

if(pos > -1):
    print("Element found at position : ", pos)
else:
    print("Element not found")
    Output:
    Element found at position : 4

  2. Sort

    Sorting is the process of arranging elements in ascending or descending order. Sorting process is mostly used for making other operations perform better.

    Sorted data helps in faster search and traversal of data structures as well as other operations. Sorting is typically more relevant for some types of linear data structures like arrays.

    For some structures like linked lists sorting may be of not much use as well, since each node is connected using pointers and even if data is sorted, we will still have to navigate to each node by using pointer references to get the data.

    We have multiple sort algorithms like Quick sort, Bubble sort, Counting sort, Bucket sort, etc for linear structures. There are some applications of sort for non-linear structures as well. Algorithms like tree sort and topological sort can be applied on certain types of trees and graphs.

    Below is a sample sort program in Python using for loops. Note that this might not be the fastest sorting algorithm in most scenarios. We will see different sorting algorithms in later chapters.

    Copied 
    arry = [5, 12, 15, 18, 40, 30, 22, 45, 8, 34]

for i in range(len(arry)):
    for j in range(i+1, len(arry)):
        if(arry[i] > arry[j]):
            tmp = arry[i]
            arry[i] = arry[j]
            arry[j] = tmp

print(arry)
    Output:
    [5, 8, 12, 15, 18, 22, 30, 34, 40, 45]

  3. Traversals

    Traversal means navigating through the elements of a data structure. Traversal process is important and is useful in many scenarios like listing all the elements of an array, from sum of all elements in an array, find shortest path between two nodes of a tree or a graph, etc.

    As mentioned earlier, for traversals as well, we need to use the best algorithms based on data structure type and amount of data.

    A traversal code sample that finds the sum of all elements in an array.

    Copied 
    arry = [5, 12, 15, 18, 40, 30, 22, 45, 8, 34]

sum = 0
for i in range(len(arry)):
    sum += arry[i]

print("Sum = ", sum)
    Output:
    Sum = 229

  4. Insert, Update and Delete

    This is the process of changing one or more elements in a data structure by inserting a new node, updating an existing node value or deleting a node.

    Most programming languages provide built-in methods to do the insert, update or delete. In the back-end these methods perform traversals, searches and re-arrangement of data to perform these actions.

    Linked lists perform well for insert update and delete operations. For example, to insert data to a particular position, we just need to break the link and insert new element to that position by updating the pointer values of just 2 nodes.

    For other data structures, we might need to do a traversal to find the right position and then do the insert, update or delete. If data is kept in sorted format, a re-arrangement is also required.

  5. Merge, Split, Slice

    Merge is the process of combining two or more data structures. Split is to break a structure to multiple groups. Slicing is copying a part of a data structure.

    All these operations require traversals and re-arrangement of nodes.

Next few topics of this module covers some important technical terms and its usages in DSA. Please follow carefully.

Absolute Code Works - Python Topics