Dynamic Data Structures: Lists and Trees

Dynamic data structures in C provide a way to efficiently store, organize, and manipulate data in memory during runtime. Unlike static structures such as arrays, which have a fixed size, dynamic structures like linked lists and trees can grow or shrink as needed, allowing more flexible and memory-efficient programming.

This article focuses on two primary dynamic data structures in C: Linked Lists and Trees. Understanding these will provide a strong foundation for implementing complex systems and algorithms in C programming.

Linked Lists in C

Definition and Concept

A linked list is a Dynamic Data Structures. It is a linear collection of data elements, where each element (called a node) contains two parts:

A data field to store the value.
A pointer field to store the address of the next node in the list.

This structure allows data elements to be stored at non-contiguous memory locations. Unlike arrays, linked lists can easily grow or shrink in size without the need to reallocate or reorganize memory.

Types of Linked Lists

Singly Linked List: Each node has a pointer to the next node only.
Doubly Linked List: Each node has two pointers, one to the next node and one to the previous node.
Circular Linked List: The last node of the list points back to the first node.

Operations on Linked Lists

Insertion: Adding a new node at the beginning, end, or in between existing nodes.
Deletion: Removing a node from the list.
Traversal: Visiting each node to display or process the data.

Common Use-Cases

Dynamic memory allocation.
Efficient insertion and deletion operations.
Implementing stacks and queues.

Working Example of Singly Linked List

This program demonstrates inserting elements at the beginning and displaying the list.

Click me!

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

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

void insertAtBeginning(struct Node** head, int value) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = *head;
    *head = newNode;
}

void displayList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);
    displayList(head);
    return 0;
}

Trees in C

Definition and Structure

A tree is a hierarchical Dynamic Data Structures composed of nodes connected by edges. It starts with a root node and branches out into sub trees. Trees are non-linear in nature and are useful for representing hierarchical relationships.

Each node in a tree typically contains:

A data value.
A pointer to the left child.
A pointer to the right child.

A special type of tree called a Binary Search Tree (BST) maintains a sorted order. In a BST:

Left subtree contains nodes with values less than the parent.
Right subtree contains nodes with values greater than the parent.

Why Use Trees

Efficient for searching and sorting.
Perfect for representing hierarchical data.
Enables faster insert, delete, and search operations compared to linear structures like linked lists.

Operations on Trees

Insertion: Add a new node while maintaining tree properties.
Traversal: Visit all nodes in a specific order (Inorder, Preorder, Postorder).
Searching: Find whether a given value exists.

Inorder Traversal

This traversal visits nodes in ascending sorted order for BST:

Traverse the left subtree.
Visit the root.
Traverse the right subtree.

Working Example of Binary Search Tree

This example builds a BST, inserts values, and prints them in sorted order using inorder traversal.

Click me!

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

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct TreeNode* insertNode(struct TreeNode* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }
    return root;
}

void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct TreeNode* root = NULL;
    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 70);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 60);
    insertNode(root, 80);
    printf("Inorder Traversal: ");
    inorderTraversal(root);
    return 0;
}

Advantages of Linked Lists and Trees in Dynamic Data Structures

Memory is allocated dynamically, so they are ideal for applications where size is unknown or changes frequently.
Insertion and deletion operations are faster than arrays, especially for linked lists and balanced trees.
Trees, particularly binary search trees, provide efficient searching and sorting.

Disadvantages of Linked Lists and Trees in Dynamic Data Structures

Linked lists require extra memory for pointers.
Tree operations can become inefficient if not balanced.
Recursive operations on trees can lead to stack overflow for very deep trees.
Linked lists have linear access time, meaning each element must be accessed sequentially.

Applications

Linked Lists: Stacks, Queues, Dynamic Memory Management, Symbol Tables.
Trees: File Systems, XML Parsing, Databases, Search Engines, Expression Evaluation.

Conclusion

Dynamic Data Structures like linked lists and trees provide powerful tools for efficient data management and manipulation. Their flexibility and adaptability make them essential for developing complex applications. While linked lists are ideal for sequential data handling with frequent insertions and deletions, trees excel at hierarchical data organization and fast search operations. Understanding and mastering these structures is a critical step for every programmer working in C.

Interview Questions

1. What are the advantages of using linked lists over arrays?

Company: Infosys
Answer:

Linked lists allow dynamic memory allocation, meaning size can grow or shrink as needed.
Insertion and deletion are easier compared to arrays.
No need to shift elements during insertion/deletion.

2. What is the difference between singly and doubly linked lists in Dynamic Data Structures?

Company: TCS
Answer:

Singly linked list has one pointer that points to the next node.
Doubly linked list has two pointers: one for the next node and one for the previous node.
Doubly linked lists allow two-way traversal.

3. What is a binary tree?

Company: Wipro
Answer:

A binary tree is a hierarchical structure in which each node has at most two children.
It is used for efficient searching, sorting, and hierarchical data representation.

4. What is the difference between a binary tree and a binary search tree (BST)?

Company: IBM
Answer:

In a binary tree, there is no specific order for nodes.
In a BST, left child is less than the parent, and right child is greater than the parent.
BST allows faster searching.

5. What is tree traversal? Name the types.

Company: Accenture
Answer:

Tree traversal means visiting each node of a tree in a specific order.
Types: Inorder, Preorder, Postorder, Level Order.
Each type is used based on the application, like printing, copying, or searching the tree.

Quizzes

Dynamic Data Structures in c Quiz