Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced

Types of Data Structures

Almost every programme or software system that has been built makes use of data structures. Furthermore, data structures are basics of computer science and software engineering. When it comes to Software Engineering interview questions, this is a critical issue. As a result, as developers, we must be well-versed in data structures.

We've spoken about data types and data structure classifications so far. Our journey through the many aspects of data structures continues with an examination of the various forms of data structures.

Arrays

Arrays are groups of data elements of the same kind that are stored in adjacent memory regions. Each data piece is referred to as a "element." Arrays are the most fundamental and basic data structure. Before going on to other structures like as queues or stacks, aspiring Data Scientists should grasp array creation.

An array is a fixed-size structure. It can be an array of integers, a floating-point number array, a text array, or even a collection of arrays (such as 2-dimensional arrays). Because arrays are indexed, they may be accessed at any time.

Operations on arrays

  • Traverse: Print the elements as you go through them.
  • Search: Search the array for a certain element. You may look for an element by its value or index.
  • Update: Updates the value of an existing element at a specified index.
Types Of Data Structures

Because arrays are fixed in size, adding and removing elements to and from them cannot be done immediately. To add an element to an array, you must first build a new array with a larger size (current size + 1), copy the existing items, and then add the new element. The same is true for deleting an array and replacing it with a smaller one.

Graphs

Graphs are illustrative nonlinear representations of element sets. Graphs are made up of finite node sets, also known as vertices that are connected by connections, also known as edges. Trees, as indicated below, are a type of graph with no rules dictating how the nodes join.

The number of vertices in a graph determines its order. The number of edges in a graph determines its size.

If two nodes are connected by the same edge, they are said to be neighbouring.

Directed Graphs

A graph G is said to be a directed graph if all of its edges have a direction specifying which vertex is at the beginning and which vertex is at the conclusion.

(u, v) is said to be incident from or exits vertex u and incident to or enters vertex v.

Self-loops are edges that connect a vertex to itself.

Undirected Graphs

If all of the edges of a graph G have no direction, the graph is said to be undirected. It can go in both directions between the two vertices.

A vertex is considered to be isolated if it is not linked to any other node in the graph.

Types Of Data Structures

Hash Tables

Hash tables, also known as hash maps, can be utilised as a linear or nonlinear data structure, albeit the former is preferred. Arrays are typically used to construct this structure. Hash tables are used to map keys to values. For example, every book in a library is allocated a unique number, which makes it easier to seek up information about the book, such as who has checked it out, its current availability, and so on. The library's books are hashed to a unique number.

Furthermore, if we know the key associated with the value, it provides efficient lookup. As a result, regardless of the amount of the data, it is highly efficient at inputting and searching.

When putting data in a table, Direct Addressing employs a one-to-one mapping between values and keys. When there are a high number of key-value pairs, however, this strategy has a difficulty. Given the memory available on a standard computer, the table will be enormous with so many records and may be difficult or even impossible to store. Hash tables are used to prevent this problem.

Using the Hash Function

To circumvent the aforementioned difficulty with direct addressing, a special function called the hash function (h) is utilised.

A value with key k is stored in the slot k in direct accessing. We compute the index of the table (slot) to which each item 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 data is mapped.

h(k) = k % m

  • h: stands for hash function.
  • k: The key for which the hash value is to be calculated.
  • m: hash table's size in millimetres (number of slots available). A prime number that isn't quite a power of two is an excellent candidate for m.
Types Of Data Structures

When the hash function yields the same index for several keys, a collision might occur. Collisions can be avoided by using a proper hash function h and strategies like chaining and open addressing.

Linked List

Linked lists keep item collections in a sequential sequence. Each linked list element contains a data item as well as a link, or reference, to the next item on the same list.

As a result, you must access data in a specific order; random access is not feasible. Linked lists are a simple and versatile way to express dynamic sets.

Consider the following words in the context of linked lists.

  • Nodes are the elements of a linked list.
  • Each node has a key and a reference to the next node, which is its successor.
  • The head property refers to the first item in the linked list.
  • The tail is the final member of the linked list.
Types Of Data Structures

The many forms of linked lists accessible are shown below.

  • Singly Linked List - Only forward traversal of items is possible with a single linked list.
  • Doubly Linked List - Traversing items in both forward and backward directions is possible using a doubly linked list. Prev is an additional pointer on nodes that points to the previous node.
  • Circular Linked List - Circular linked lists are linked lists in which the head's previous pointer links to the tail and the tail's next pointer points to the head.

Operations on linked lists

  • Search: Using a basic linear search, find the first entry in the supplied linked list with the key k and return a reference to that element.
  • Insert: To the connected 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.
  • 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.

Stack

A stack is a Last In First Out (LIFO) (Last In First Out – the element put last may be retrieved first) structure found in many programming languages. Because it resembles a real-world stack – a stack of plates — this form is called "stack."

Operations on the stack

The two fundamental operations that may be done 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.
Types Of Data Structures

In order to verify the state of a stack, the following extra functions are available.

  • Peek: Returns the stack's top member without destroying it.
  • isEmpty: Determines whether the stack is empty.
  • isFull: Determines whether the stack is full.

Queue

Queues, like stacks, store item collections sequentially, but the operation order must be "first in, first out." Queues are essentially linear lists.

Because it resembles a real-world queue – individuals waiting in a line — this structure is called "queue."

Operations involving queues

The two fundamental operations that may be done on a queue are listed below.

Types Of Data Structures
  • Enqueue: Add a new element to the queue's end.
  • Dequeue: Remove the element from the queue's beginning.

Tree

Trees are abstract hierarchies that hold item collections. They are node-based multilevel data structures. The lowest nodes are referred to as "leaf nodes," while the highest node is referred to as the "root node." Each node has references to neighbouring nodes. This structure differs from that of a linked list, in which elements are connected in a linear order.

Various sorts of trees have been produced throughout the years to suit certain uses and to fulfil specific limits. Binary search tree, B tree, treap, red-black tree, splay tree, AVL tree, and n-ary tree are some examples.

Binary Search Tree

A binary search tree (BST) is a binary tree in which data is structured in a hierarchical structure, as the name implies. The values in this data structure are stored in sorted order.

In a binary search tree, each node has the following qualities.

  • Key: The value stored in the node's key.
  • left: The pointer is pointing at the youngster on the left.
  • right: The pointer to the kid on the right.
  • p: The parent node's pointer.

A binary search tree has a distinguishing feature that sets it apart from other trees. The binary-search-tree property is the name for this property.

In a binary search tree, let x be a node.

  • When y is a node in x's left subtree, then y.key is  ≤ x.key.
  • When y is a node in x's right subtree, y.key ≥ x.key.
Types Of Data Structures

Trie

Tries, which are not to be confused with Trees, are data structures that hold strings as data elements and are organised in a visual graph. Attempts are also known as keyword trees or prefix trees. You can see the trie data structure in action whenever you use a search engine and get auto recommendations.

Heaps

A heap is a type of binary tree in which the parent nodes' values are compared to those of their offspring and the nodes are sorted accordingly.

Types Of Data Structures

There are two sorts of heaps.

  • Min Heap - The parent's key is less than or equal to that of its children in the Min Heap. The min-heap property is what it's called. The heap's minimum value will be stored in the root.
  • Max Heap - the parent's key is larger than or equal to the children's. The max-heap property is what it's called. The heap's maximum value will be stored in the root.



ADVERTISEMENT
ADVERTISEMENT