Introduction To Non-Linear Data Structures | DSA Notes

 Introduction

Non-linear data structures organize data in hierarchical or interconnected ways, unlike linear structures that store elements sequentially. These structures are ideal for solving complex problems such as graph traversal, hierarchical representation (e.g., file systems), and network data management (e.g., social networks)

Key Differences Between Linear and Non-Linear Data Structures

These differences make non-linear data structures more versatile for complex problems, such as representing relationships in social networks (graphs) or organizing hierarchical data like file systems (trees).

Feature	Linear Data Structures	Non-Linear Data Structures
Storage Type	Sequential	Hierarchical/Graph-based
Traversal	One direction	Multiple directions
Examples	Arrays, Linked Lists, Stacks, Queues	Trees, Graphs, Heaps, Hash Tables

---

Types of Non-Linear Data Structures

1. Trees

A tree is a hierarchical data structure where each node has a parent (except the root) and can have multiple child nodes. Trees are widely used in applications like file systems, database indexing, and decision-making algorithms.

Types of Trees:

• Binary Tree: Each node has at most two children.
• Binary Search Tree (BST): A binary tree where the left subtree contains smaller values, and the right subtree contains larger values.
• Balanced Trees (AVL Tree, Red-Black Tree): Self-balancing trees to maintain efficiency.
• Heap (Min-Heap & Max-Heap): A specialized tree where the parent follows a specific order property.
• Trie (Prefix Tree): Used for fast word search and autocomplete features.

Tree Operations:

• Insertion
• Deletion
• Traversal (Preorder, Inorder, Postorder, Level Order)
• Searching

2. Graphs

A graph is a collection of nodes (vertices) connected by edges (links). Graphs can be directed (one-way relationships) or undirected (two-way relationships), and weighted (edges have values) or unweighted. They are essential for modeling real-world systems like social networks, transportation networks, and web pages.

Graph Representations:

• Adjacency Matrix: Uses a 2D array to store edge connections.
• Adjacency List: Uses a linked list for each vertex to store neighbors.

Graph Traversal Algorithms:

• Depth-First Search (DFS)
• Breadth-First Search (BFS)

Applications of Graphs:

• Shortest Path Algorithms (Dijkstra’s, Bellman-Ford)
• Social Networks, Web Crawlers, Network Routing

3. Heaps

A heap is a complete binary tree where each node satisfies a heap property (e.g., min-heap or max-heap). It is commonly used to implement priority queues, which are crucial for algorithms like Dijkstra's shortest path.

Types of Heaps:

• Min-Heap: The parent node is smaller than its children.
• Max-Heap: The parent node is greater than its children.

Heap Operations:

• Insertion
• Deletion
• Heap Sort

4. Hash Tables

A hash table is a data structure that stores key-value pairs using a hash function to map keys to indices. It provides fast data retrieval and is widely used in databases, caches, and compilers.

Hash Table Techniques:

• Chaining: Uses linked lists at each index to handle collisions.
• Open Addressing: Uses linear probing, quadratic probing, or double hashing.

---

C Program to Implement Graph Using Adjacency List

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        struct Node* temp = graph->adjLists[v];
        printf("Vertex %d:\n", v);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    int vertices = 5;
    struct Graph* graph = createGraph(vertices);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);
    return 0;
}

Explanation of the Code:

1. We define a Node structure for adjacency lists.
2. We define a Graph structure that holds an array of adjacency lists.
3. createNode() function allocates memory for a new node.
4. createGraph() function initializes a graph with empty adjacency lists.
5. addEdge() function adds an undirected edge between two vertices.
6. printGraph() function prints the adjacency list representation of the graph.
7. The main() function creates a graph, adds edges, and prints the graph.

---

Conclusion

Non-linear data structures like trees, graphs, heaps, and hash tables offer powerful ways to model complex relationships and solve real-world problems. From organizing hierarchical data (trees) to optimizing network routes (graphs), these structures are essential tools for efficient computation. Mastering them is key to excelling in computer science and software development.