NoteVerse

Data Structure

Comprehensive study notes, diagrams, and exam preparation for Data Structure.

Data Structure

Definition

A data structure is a systematic way of organizing and storing data in memory so that it can be used efficiently for specific operations such as retrieval, insertion, deletion, traversal, and updating.

In simple words, it is the arrangement of data in a computer so that the program can handle it effectively. Different data structures are designed for different purposes. Some are better for fast searching, some for easy insertion, and others for maintaining relationships among data items.

Examples of common data structures include:

  • Arrays
  • Linked Lists
  • Stacks
  • Queues
  • Trees
  • Graphs
  • Hash Tables

Main Content

1. Types of Data Structures

Primitive and Non-Primitive Data Structures

Data structures are broadly classified into primitive and non-primitive types. Primitive data structures store single values and are directly supported by the machine, such as int, char, float, and bool. Non-primitive data structures store collections of values or complex relationships and are built using primitive types.

Primitive example:
int age = 20;

Non-primitive example:
A list of student names, a tree representing family hierarchy, or a graph showing city connections.

Linear and Non-Linear Data Structures

Linear data structures arrange data in a sequential order, where each element is connected to the next one. Examples include arrays, linked lists, stacks, and queues. Non-linear data structures arrange data in a hierarchical or network form, such as trees and graphs.

Linear representation example:
10 -> 20 -> 30 -> 40

Non-linear representation example:
A tree structure where one root node has multiple child nodes.

Linear structures are easier to implement and understand, while non-linear structures are more suitable for complex relationships.

2. Basic Operations on Data Structures

Insertion, Deletion, and Access

Insertion means adding a new item, deletion means removing an item, and access means reading or retrieving an item. These are the core operations used in almost every data structure.

Example:

  • Insert a new product into a shopping cart
  • Delete a cancelled order
  • Access a student’s marks from a record

The efficiency of these operations depends on the data structure. For example, inserting an element in an array may require shifting elements, while insertion in a linked list can often be easier.

Traversal, Searching, and Updating

Traversal means visiting every element in a data structure, searching means finding a particular element, and updating means changing the value of an existing element.

Example:

  • Traversal: reading every node in a tree
  • Searching: finding a specific name in a list
  • Updating: changing an employee’s salary

These operations are essential in real-world software like databases, file systems, and web applications.

3. Common Data Structures with Examples

Array, Linked List, Stack, and Queue

An array stores elements in contiguous memory locations and allows direct access using index numbers. A linked list stores elements in nodes, where each node points to the next one. A stack follows the LIFO principle (Last In, First Out), while a queue follows the FIFO principle (First In, First Out).

Array example:
marks = [78, 82, 90, 67]

Linked list example:
Head -> [5] -> [10] -> [15] -> NULL

Stack example:
Bottom -> [1] [2] [3] -> Top

Queue example:
Front -> [A] [B] [C] -> Rear

These are widely used in programming:

  • Arrays for fixed-size collections
  • Linked lists for dynamic memory usage
  • Stacks for function calls and undo operations
  • Queues for task scheduling and buffering

Tree, Graph, and Hash Table

A tree is a hierarchical data structure where one node is the root and other nodes are arranged in parent-child form. A graph consists of vertices (nodes) and edges (connections), useful for representing networks. A hash table stores key-value pairs and provides very fast lookup using a hash function.

Tree example:

      A
     / \
    B   C
   / \
  D   E

Graph example:

  A --- B
  | \   |
  |  \  |
  C --- D

Hash table example:

  • Key: 101 → Value: Ravi
  • Key: 102 → Value: Anita

These structures are important in file directories, social networks, search engines, routing systems, and databases.

Working / Process

1. Identify the problem and data requirements

First, understand what kind of data needs to be stored and what operations will be performed most often. For example, if frequent searching is required, a hash table may be appropriate. If the data is hierarchical, a tree may be better.

2. Choose the suitable data structure

Select the structure based on memory usage, speed, and type of operations. For instance:

  • Use an array for indexed access
  • Use a stack for reversing actions
  • Use a queue for ordered processing
  • Use a graph for network relationships

3. Perform operations efficiently

Once selected, the data structure is used to insert, delete, search, traverse, and update values. The internal design determines how efficiently these operations are completed.

4. Analyze performance

Evaluate time complexity and space complexity to determine whether the chosen structure is optimal. A suitable structure reduces execution time and improves program performance.

Advantages / Applications

Improves efficiency

Proper data structures make programs faster by reducing the time required for operations like searching and inserting.

Optimizes memory usage

Data structures help store data in a space-efficient way, avoiding unnecessary memory consumption.

Supports real-world applications

They are used in operating systems, databases, artificial intelligence, compilers, web browsers, and networking systems. For example:

  • Stacks are used in expression evaluation and recursion
  • Queues are used in printer scheduling
  • Trees are used in file systems
  • Graphs are used in maps and social networks

Summary

  • Data structure is a way of organizing data for efficient use
  • It helps in storing and processing data effectively
  • Common examples include arrays, linked lists, stacks, queues, trees, graphs, and hash tables
  • Important terms to remember: array, linked list, stack, queue, tree, graph, hash table, traversal, insertion, deletion
← Prev: Comments.
Next: List →