C Programming: Implementing Linked Lists and Binary Search Trees

Posted on Jan 29, 2026 in Computers

Singly Linked List (SLL) Implementation for Student Data

This C program demonstrates the implementation of a Singly Linked List (SLL) to manage student records. It includes standard list operations (insertion, deletion) and utilizes insert_front and delete_front to simulate basic stack operations (Push/Pop).

SLL Structure and Global Variables

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

struct node {
    char usn[20], name[20], branch[20];
    int sem;
    long phone;
    struct node *link;
};

typedef struct node* NODE;
NODE start = NULL;
int count = 0;

SLL Node Creation and Insertion Functions

NODE create() {
    NODE n = (NODE)malloc(sizeof(struct node));
    if (!n) {
        printf("Memory allocation failed\n");
        exit(0);
    }
    printf("Enter USN Name Branch Sem Phone:\n");
    scanf("%s %s %s %d %ld",
          n->usn, n->name, n->branch, &n->sem, &n->phone);
    n->link = NULL;
    count++;
    return n;
}

NODE insert_front() {
    NODE n = create();
    n->link = start;
    return n;
}

NODE insert_end() {
    NODE n = create(), cur;
    if (!start) return n;
    cur = start;
    while (cur->link) cur = cur->link;
    cur->link = n;
    return start;
}

SLL Deletion and Display Functions

NODE delete_front() {
    NODE temp;
    if (!start) {
        printf("List empty\n");
        return NULL;
    }
    temp = start;
    start = start->link;
    printf("Deleted USN: %s\n", temp->usn);
    free(temp);
    count--;
    return start;
}

NODE delete_end() {
    NODE cur, prev = NULL;
    if (!start) {
        printf("List empty\n");
        return NULL;
    }
    if (!start->link) {
        printf("Deleted USN: %s\n", start->usn);
        free(start);
        count--;
        return NULL;
    }
    cur = start;
    while (cur->link) {
        prev = cur;
        cur = cur->link;
    }
    prev->link = NULL;
    printf("Deleted USN: %s\n", cur->usn);
    free(cur);
    count--;
    return start;
}

void display() {
    NODE cur = start;
    int i = 1;
    if (!cur) {
        printf("No records\n");
        return;
    }
    while (cur) {
        printf("%d) %s %s %s %d %ld\n",
               i++, cur->usn, cur->name,
               cur->branch, cur->sem, cur->phone);
        cur = cur->link;
    }
    printf("Total nodes = %d\n", count);
}

SLL Main Function (Menu)

int main() {
    int ch, n;
    while (1) {
        printf("\n1.Create 2.Display 3.InsertEnd 4.DeleteEnd 5.Push 6.Pop 7.Exit\n");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("How many students: ");
                scanf("%d", &n);
                for (int i = 0; i < n; i++)
                    start = insert_front();
                break;
            case 2: display(); break;
            case 3: start = insert_end(); break;
            case 4: start = delete_end(); break;
            case 5: start = insert_front(); break;
            case 6: start = delete_front(); break;
            case 7: exit(0);
        }
    }
}

LAB PROGRAM 8: Doubly Linked List (DLL) for Employee Data

This program implements a Doubly Linked List, allowing efficient insertion and deletion at both the front and end, utilizing both llink (left link) and rlink (right link) pointers.

DLL Structure and Setup

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

struct node {
    char ssn[20], name[20], dept[20], desig[20];
    int sal;
    long phone;
    struct node *llink, *rlink;
};

typedef struct node* NODE;
NODE first = NULL;
int count = 0;

DLL Insertion and Deletion Functions

NODE create() {
    NODE n = (NODE)malloc(sizeof(struct node));
    if (!n) exit(0);
    printf("Enter SSN Name Dept Designation Salary Phone:\n");
    scanf("%s %s %s %s %d %ld",
          n->ssn, n->name, n->dept,
          n->desig, &n->sal, &n->phone);
    n->llink = n->rlink = NULL;
    count++;
    return n;
}

NODE insert_front() {
    NODE n = create();
    if (!first) return n;
    n->rlink = first;
    first->llink = n;
    return n;
}

NODE insert_end() {
    NODE n = create(), cur;
    if (!first) return n;
    cur = first;
    while (cur->rlink) cur = cur->rlink;
    cur->rlink = n;
    n->llink = cur;
    return first;
}

NODE delete_front() {
    NODE temp;
    if (!first) return NULL;
    temp = first;
    first = first->rlink;
    if (first) first->llink = NULL;
    free(temp);
    count--;
    return first;
}

NODE delete_end() {
    NODE cur;
    if (!first) return NULL;
    cur = first;
    while (cur->rlink) cur = cur->rlink;
    if (cur->llink)
        cur->llink->rlink = NULL;
    else
        first = NULL;
    free(cur);
    count--;
    return first;
}

void display() {
    NODE cur = first;
    int i = 1;
    if (!cur) {
        printf("Empty DLL\n");
        return;
    }
    while (cur) {
        printf("%d) %s %s %s %s %d %ld\n",
               i++, cur->ssn, cur->name,
               cur->dept, cur->desig,
               cur->sal, cur->phone);
        cur = cur->rlink;
    }
    printf("Total = %d\n", count);
}

DLL Main Function (Menu)

int main() {
    int ch;
    while (1) {
        printf("\n1.InsertFront 2.InsertEnd 3.DeleteFront 4.DeleteEnd 5.Display 6.Exit\n");
        scanf("%d", &ch);
        switch (ch) {
            case 1: first = insert_front(); break;
            case 2: first = insert_end(); break;
            case 3: first = delete_front(); break;
            case 4: first = delete_end(); break;
            case 5: display(); break;
            case 6: exit(0);
        }
    }
}

LAB PROGRAM 9: Binary Search Tree (BST) Implementation

This C program implements a Binary Search Tree, covering recursive node insertion, standard traversal methods (Inorder, Preorder, Postorder), and iterative searching.

BST Structure and Insertion

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

struct bst {
    int data;
    struct bst *l, *r;
};

typedef struct bst* NODE;

NODE insert(NODE root, int x) {
    if (!root) {
        NODE n = (NODE)malloc(sizeof(struct bst));
        n->data = x;
        n->l = n->r = NULL;
        return n;
    }
    if (x < root->data)
        root->l = insert(root->l, x);
    else if (x > root->data)
        root->r = insert(root->r, x);
    return root;
}

BST Traversal Methods

void inorder(NODE r) {
    if (r) {
        inorder(r->l);
        printf("%d ", r->data);
        inorder(r->r);
    }
}

void preorder(NODE r) {
    if (r) {
        printf("%d ", r->data);
        preorder(r->l);
        preorder(r->r);
    }
}

void postorder(NODE r) {
    if (r) {
        postorder(r->l);
        postorder(r->r);
        printf("%d ", r->data);
    }
}

BST Search Function

void search(NODE r, int key) {
    while (r) {
        if (key == r->data) {
            printf("Key found\n");
            return;
        }
        r = (key < r->data) ? r->l : r->r;
    }
    printf("Key not found\n");
}

BST Main Function (Menu)

int main() {
    NODE root = NULL;
    int ch, x, n;
    while (1) {
        printf("\n1.Create 2.Traverse 3.Search 4.Exit\n");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("Enter number of nodes: ");
                scanf("%d", &n);
                printf("Enter %d elements:\n", n);
                for (int i = 0; i < n; i++) {
                    scanf("%d", &x);
                    root = insert(root, x);
                }
                break;
            case 2:
                printf("Inorder: "); inorder(root);
                printf("\nPreorder: "); preorder(root);
                printf("\nPostorder: "); postorder(root);
                printf("\n");
                break;
            case 3:
                printf("Enter key to search: ");
                scanf("%d", &x);
                search(root, x);
                break;
            case 4:
                exit(0);
        }
    }
}