Doubly linked list

Aim:

To implement a Doubly Linked List (DLL) and perform operations like creation, insertion, deletion, and display.

Objectives:

  1. Understand the concept of a doubly linked list.

  2. Perform dynamic memory allocation for nodes.

  3. Implement insertion at the beginning, end, and at a given position.

  4. Implement deletion from the beginning, end, and specific position.

  5. Traverse and display the list in forward direction.

Algorithm:

1. Create Node:

  • Allocate memory using malloc.

  • Assign data.

  • Set prev and next pointers.

2. Insert:

  • At beginning: Adjust prev and next pointers.

  • At end: Traverse to last node and insert.

  • At position: Traverse to that position and insert node.

3. Delete:

  • Beginning: Update head pointer.

  • End: Update last node’s pointer.

  • Specific position: Adjust pointers of neighbors.

4. Display:

  • Traverse from head to end.

  • Print each node’s data.

Flowchart:

Generated image

C Program (Doubly Linked List Implementation)

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node *prev, *next;

};

struct Node *head = NULL;

// Create a new node

struct Node* createNode(int data) {

    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->prev = newNode->next = NULL;

    return newNode;

}

// Insert at the end

void insertEnd(int data) {

    struct Node *newNode = createNode(data);

    if (head == NULL) {

        head = newNode;

        return;

    }

    struct Node *temp = head;

    while (temp->next != NULL)

        temp = temp->next;

    temp->next = newNode;

    newNode->prev = temp;

}

// Insert at beginning

void insertBegin(int data) {

    struct Node *newNode = createNode(data);

    if (head == NULL) {

        head = newNode;

        return;

    }

    newNode->next = head;

    head->prev = newNode;

    head = newNode;

}

// Insert at specific position

void insertAtPos(int data, int pos) {

    struct Node *newNode = createNode(data);

    if (pos == 1) {

        insertBegin(data);

        return;

    }

    struct Node *temp = head;

    for (int i = 1; i < pos - 1 && temp != NULL; i++)

        temp = temp->next;

    if (temp == NULL) {

        printf("Position not found!\n");

        return;

    }

    newNode->next = temp->next;

    if (temp->next != NULL)

        temp->next->prev = newNode;

    temp->next = newNode;

    newNode->prev = temp;

}

// Delete at beginning

void deleteBegin() {

    if (head == NULL) {

        printf("List is empty\n");

        return;

    }

    struct Node *temp = head;

    head = head->next;

    if (head != NULL)

        head->prev = NULL;

    free(temp);

}

// Delete at end

void deleteEnd() {

    if (head == NULL) {

        printf("List is empty\n");

        return;

    }

    struct Node *temp = head;

    while (temp->next != NULL)

        temp = temp->next;

    if (temp->prev != NULL)

        temp->prev->next = NULL;

    else

        head = NULL;

    free(temp);

}

// Delete at specific position

void deleteAtPos(int pos) {

    if (head == NULL) {

        printf("List is empty\n");

        return;

    }

    struct Node *temp = head;

    if (pos == 1) {

        deleteBegin();

        return;

    }

    for (int i = 1; i < pos && temp != NULL; i++)

        temp = temp->next;

    if (temp == NULL) {

        printf("Position not found!\n");

        return;

    }

    if (temp->prev != NULL)

        temp->prev->next = temp->next;

    if (temp->next != NULL)

        temp->next->prev = temp->prev;

    free(temp);

}

// Display the list

void display() {

    struct Node *temp = head;

    if (temp == NULL) {

        printf("List is empty\n");

        return;

    }

    printf("Doubly Linked List: ");

    while (temp != NULL) {

        printf("%d <-> ", temp->data);

        temp = temp->next;

    }

    printf("NULL\n");

}

// Main function

int main() {

    int choice, data, pos;

    while (1) {

        printf("\n--- Doubly Linked List Menu ---\n");

        printf("1. Insert at beginning\n2. Insert at end\n3. Insert at position\n");

        printf("4. Delete at beginning\n5. Delete at end\n6. Delete at position\n");

        printf("7. Display\n8. Exit\n");

        printf("Enter choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter data: ");

                scanf("%d", &data);

                insertBegin(data);

                break;

            case 2:

                printf("Enter data: ");

                scanf("%d", &data);

                insertEnd(data);

                break;

            case 3:

                printf("Enter data and position: ");

                scanf("%d %d", &data, &pos);

                insertAtPos(data, pos);

                break;

            case 4:

                deleteBegin();

                break;

            case 5:

                deleteEnd();

                break;

            case 6:

                printf("Enter position: ");

                scanf("%d", &pos);

                deleteAtPos(pos);

                break;

            case 7:

                display();

                break;

            case 8:

                exit(0);

            default:

                printf("Invalid choice!\n");

        }

    }

    return 0;

}


Comments

Post a Comment

Popular posts from this blog

Stack using array

Image
  1) Stack using Array Aim To implement stack operations (Push, Pop, Display) using arrays in C. Objective To study the LIFO (Last In, First Out) principle. To practice array-based implementation of data structures. Algorithm Push: If top == n-1, then overflow. Else top = top + 1 and insert element at stack[top]. Pop: If top == -1, then underflow. Else delete element from stack[top], then top = top - 1. Display: If top == -1, stack empty. Else print elements from stack[top] to stack[0]. Flowchart  C Code (Stack using Array) #include <stdio.h> #define MAX 5 int main() {     int stack[MAX], top = -1, choice, item, i;     while (1) {         printf("\n--- Stack Menu ---\n");         printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");         printf("Enter choice: ");         scan...
Read more

Bubble Sort

Image
  2) Bubble Sort Aim To arrange elements in ascending order using Bubble Sort (without functions). Objective To study simple comparison-based sorting. To understand swapping of adjacent elements. Algorithm Input number of elements and array. Repeat for i = 0 to n-1 Repeat for j = 0 to n-i-2 If arr[j] > arr[j+1], swap them. Print sorted array. Flowchart C Code #include <stdio.h> int main() {     int n, i, j, temp;     printf("Enter number of elements: ");     scanf("%d", &n);     int arr[n];     printf("Enter array elements: ");     for (i = 0; i < n; i++)         scanf("%d", &arr[i]);     for (i = 0; i < n - 1; i++) {         for (j = 0; j < n - i - 1; j++) {             if (arr[j]...
Read more

Singly linked list implementation

Image
  Singly Linked List Implementation Aim To implement basic operations on a Singly Linked List in C. Objective To study dynamic memory allocation using linked lists. To perform Insert, Delete, Traverse operations. To understand pointer manipulation in data structures. Operations in Singly Linked List Insert at Beginning Insert at End Insert at Position Delete from Beginning Delete from End Delete from Position Display List Algorithm Insert at Beginning Create new node. new->next = head. head = new. Insert at End Create new node. If list empty → head = new. Else traverse to last node, set last->next = new. Insert at Position Traverse until position-1. Link new node in between. Delete from Beginning If empty → print "Underflow". Else move head to head->next, free old head. Delete from End If empty → print "Underflow". Else traverse to last-1 node, set last->next = NULL, free last. Delete from Position Traverse until position-1. Adjust links and free node...
Read more