Data Structure

A storage that is used to store and arrange data is called a data structure. It is a technique for organising data on computer such that it is readily available and current. A data structure is not just employed for data organisation. Data processing, retrieval, and archiving are further uses for it. Almost every software system or programme that has been created uses many fundamental and sophisticated forms of data structures. Therefore, we need to be knowledgeable about data structures. Computers employ data structures as a fundamental component to organise data in memory. In order to efficiently organise, process, access, and store data, they are necessary.

Data structure Type  :

Type of Data Structure

There are two types of DS:

  • Primitive DS

 Primitive data types correspond to primitive data structures. The primitive data structures that can store single value are int, char, float, double, and pointer.

  • Non-primitive DS

      The non-primitive DS are two types:

  • Linear data structure

A grouping of data in a consecutive manner is referred to as a linear data structure. Data structures including queues, stacks, linked lists, and arrays are employed for this purpose. In these data structures, just one element is linearly connected to every other element.

Types of Linear DS

  • Arrays:

    Each data item in an array is referred to as an element and is a collection of comparable types of data objects. The element’s data type can be any legal data type, such as char, int, float, or double.

Array

  • Linked List:

    A list is kept in memory using a linear data structure called a linked list. It can be thought of as a group of nodes kept in different parts of memory. A pointer to the node next to it is present in each node of the list.
Head ,Data,Link

  • Stack:

     Stack is a linear list whose additions and deletions are only permitted at the top end. A stack is an abstract data type (ADT), and most computer languages support its implementation. It is called a stack because it functions like a stack in the real world, such as a stack of dishes or a deck of cards.
Push
  • Queue:

    A queue is a linear list where items can only be added at one end, known as the rear, and deleted only at the other end, known as the front.

Enqueue

Non-linear data structure

A non-linear data structure is one in which one element is linked to ‘n’ different elements. Trees and graphs are the finest examples. In this instance, the elements are put in a haphazard order.

Types of non linear DS

  • Trees:

    Trees are multilevel data structures having nodes, which are the items, arranged in a hierarchy. The leaf node and root node are the bottom and top nodes, respectively, of the hierarchical structure. Each node has a pointer to another node that is nearby.

Graph

  • Graphs

    :Graphs are a visual depiction of a collection of components (represented by vertices) linked together by edges. In the sense that a graph can have cycles but a tree cannot, a graph differs from a tree. Both directed and undirected graphs exist. In contrast, edges in an undirected graph are not connected to the directions that they are connected to. The graph in the above illustration is an undirected one since none of the edges are connected to any of the directions. Vertex A and B may be traversed from B to A as well as A to B if there is an edge between them.
Directed Graph
Undirected Graph

Sorting in DS: 

  • Bubble Sort: The largest member is repeatedly moved to the array’s highest index, which is how the simplest sort algorithm works. It involves comparing each element to its neighbouring element and replacing them as necessary.
  • Bucket sort: Bin sort is another name for bucket sort. It operates by dividing the element among the array’s buckets. Each bucket is sorted separately in this sorting method using a different sorting algorithm.
  • Comb Sort: The improved version of Bubble Sort is Comb Sort. While comb sort eliminates any turtle values or small values near the end of the list, bubble sort compares all neighbouring value
  • Counting Sort: It is a key-based sorting method, where items are gathered in accordance with keys that are discrete integers. The counting sort determines the frequency of objects and records their key values. By adding the preceding key items and assigning them to objects, a new array is created.
  • Heap Sort: The heap sort maintains a minimum or maximum heap from the array elements depending on the selection, and the items are sorted by removing the heap’s root element. 
  • Insertion Sort: As the name implies, insertion sort places each element of the array in the appropriate location. When playing bridge, the deck of cards is arranged using a fairly basic sorting technique.
  • Merge sort: Merge sort is a variation on the divide-and-conquer strategy, where the list is first split into sets of equal members, and then each half is sorted separately using merge sort. An basic sorted array is created by once more combining the sorted list.
  • Quick sort: The most efficient sort algorithm is quick sort, which completes comparisons in O(n log n) comparisons. Quick sort has a similar divide and conquer strategy as merge sort.
  • Radix Sort: When using Radix sort, the names are arranged alphabetically before being sorted. It is the integer-specific lenear sorting algorithm.
  • Selection sort: The smallest element in the array is located using selection sort, which also locates the second-smallest element in the array and places it on the second spot in the list. Until all of the components are rearranged in the proper order, this process is repeated. Its running time, which is worse than insertion sort, is O(n2).
  • Shell sort: The generalisation of insertion sort known as shell sort compares elements that are separated by a distance of multiple locations, thus overcoming the limitations of insertion sort.

Major Operations:

The major operations performed on the DS:

  • Searching: Any element of a data structure can be searched for.
  • Sorting: The components of data structure can be arranged in either ascending or descending order.
  • Insertion: The new element can also be added to an existing data structure.
  • Updation: We can also replace an element with another element in order to update it.
  • Deletion: To remove an element from a data structure, we can also use the delete operation.

Need Of DS:

  • Processor speed: Fast processing is needed to manage very huge amounts of data, however because the volume of data is increasing daily to billions of files every entity, the processor may not be able to handle so much data.
  • Data Search: Assume that there are 106 things in the store’s inventory. If our programme has to look for a specific item, it must go through all 106 of them, which slows down the search process.

Advantages of DS:

  • Efficiency: If the data structure is chosen to implement a specific ADT is chosen properly, the programme will run very quickly and efficiently.
  • Reusability: The data structure ability to used by a variety of client programmes is referred to as reusability.
  • Abstraction: The level of abstraction is also provided by data structure that an ADT specifies. The client need not concerned about the implementation aspect because it cannot see how the data structure is used internally. Only the interface is visible to client.