C Programming Implementing Data Structures Linked Lists Trees Hash Tables Complete Guide

C Programming Implementing Data Structures: Linked Lists, Trees, Hash Tables

Linked Lists

A linked list is a linear data structure where elements (nodes) are not stored at contiguous memory locations but are linked with each other using pointers. Linked lists can be singly linked, doubly linked, or circularly linked.

• Singly Linked List: Each node contains data and a pointer to the next node. The last node points to NULL.

  struct Node {
      int data;
      struct Node* next;
  };
  
  struct Node* head = NULL; // Global variable pointing to head node
  

• Doubly Linked List: Each node contains data and two pointers, one to the next node and another to the previous node.

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

• Circular Linked List: Similar to singly linked list; the last node points to the first node, forming a circular chain.

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

Key Operations:

• Insertion: To insert a node, allocate memory, copy data, and adjust pointers.

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

• Deletion: To delete a node, traverse list to find node, rearrange pointers, and free memory.

  void deleteNode(int key) {
      struct Node* temp = head;
      struct Node* prev = NULL;
  
      if (temp != NULL && temp->data == key) {
          head = temp->next;
          free(temp);
          return;
      }
  
      while (temp != NULL && temp->data != key) {
          prev = temp;
          temp = temp->next;
      }
  
      if (temp == NULL) return;
  
      prev->next = temp->next;
      free(temp);
  }
  

• Traversal: Starting from head, visit each node until NULL is encountered.

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

Trees

A tree is a hierarchical data structure with a root node and zero or more child nodes. Each node except the root node is connected with exactly one parent node.

• Binary Trees: Nodes have at most two children, referred to as left and right child.

  struct Node {
      int data;
      struct Node* left;
      struct Node* right;
  };
  
  struct Node* newNode(int data) {
      struct Node* node = (struct Node*)malloc(sizeof(struct Node));
      node->data = data;
      node->left = NULL;
      node->right = NULL;
      return node;
  }
  

• Binary Search Trees (BST): A binary tree where the left subtree of a node contains only nodes with keys lesser than the node’s key, and the right subtree only nodes with keys greater.

  struct Node* insert(struct Node* node, int data) {
      if (node == NULL) return newNode(data);
  
      if (data < node->data)
          node->left = insert(node->left, data);
      else if (data > node->data)
          node->right = insert(node->right, data);
  
      return node;
  }
  

• Balanced Trees: Automatically rebalance to maintain equal height on both sides, like AVL trees or Red-Black trees.

Key Operations:

• Insertion: Place data in the correct position maintaining BST property.

  struct Node* insert(struct Node* node, int data) {
      if (node == NULL) return newNode(data);
  
      if (data < node->data)
          node->left = insert(node->left, data);
      else if (data > node->data)
          node->right = insert(node->right, data);
  
      return node;
  }
  

• Deletion: Remove a node by considering three cases: no child, one child, or two children.

  struct Node* deleteNode(struct Node* root, int key) {
      if (root == NULL) return root;
  
      if (key < root->data)
          root->left = deleteNode(root->left, key);
      else if (key > root->data)
          root->right = deleteNode(root->right, key);
      else {
          if (root->left == NULL) {
              struct Node* temp = root->right;
              free(root);
              return temp;
          } else if (root->right == NULL) {
              struct Node* temp = root->left;
              free(root);
              return temp;
          }
  
          struct Node* temp = minValueNode(root->right);
          root->data = temp->data;
          root->right = deleteNode(root->right, temp->data);
      }
      return root;
  }
  

• Traversal: Use methods like in-order, pre-order, post-order, and level-order to visit all nodes.

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

Hash Tables

A hash table is a data structure used to implement associative arrays. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

• Hash Function: Maps keys to indices to find data efficiently.

  int hashFunction(int key, int capacity) {
      return key % capacity;
  }
  

• Separate Chaining: If multiple keys map to the same index, use linked lists to store all elements.

  struct Node {
      int key;
      int value;
      struct Node* next;
  };
  
  struct HashTable {
      struct Node** table;
      int capacity;
  };
  
  struct HashTable* createHashTable(int capacity) {
      struct HashTable* ht = (struct HashTable*)malloc(sizeof(struct HashTable));
      ht->capacity = capacity;
      ht->table = (struct Node**)malloc(capacity * sizeof(struct Node*));
      for (int i = 0; i < capacity; i++)
          ht->table[i] = NULL;
      return ht;
  }
  

• Open Addressing: If a collision occurs, probe other slots until an empty slot is found.

Types of open addressing:

• Linear Probing: hash(key) + i for i = 0, 1, 2, ...
• Quadratic Probing: hash(key) + i^2 for i = 0, 1, 2, ...
• Double Hashing: hash1(key) + i * hash2(key) for i = 0, 1, 2, ...

Key Operations:

• Insertion: Compute hash, insert key-value pair, handle collisions.

  void insert(struct HashTable* ht, int key, int value) {
      int hash = hashFunction(key, ht->capacity);
      struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
      newNode->key = key;
      newNode->value = value;
      newNode->next = ht->table[hash];
      ht->table[hash] = newNode;
  }
  

• Search: Compute hash, traverse linked list to find key.

  int search(struct HashTable* ht, int key) {
      int hash = hashFunction(key, ht->capacity);
      struct Node* temp = ht->table[hash];
      while (temp != NULL) {
          if (temp->key == key)
              return temp->value;
          temp = temp->next;
      }
      return -1; // Key not found
  }
  

• Deletion: Compute hash, find key, remove node.

  void deleteEntry(struct HashTable* ht, int key) {
      int hash = hashFunction(key, ht->capacity);
      struct Node* temp = ht->table[hash];
      struct Node* prev = NULL;
      while (temp != NULL && temp->key != key) {
          prev = temp;
          temp = temp->next;
      }
      if (temp == NULL) return;
      if (prev == NULL)
          ht->table[hash] = temp->next;
      else
          prev->next = temp->next;
      free(temp);
  }
  

Conclusion: