Week 5 programs to implement Circular Linked list and Doubly-linked list operations.

Circular Linked List

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty() {
   return head == NULL;
}
int length() {
   int length = 0;
   if(head == NULL) {
      return 0;
   }
   current = head->next;
   while(current != head) {
      Length++;
      current = current->next;
   }
   return length;
}
void insertFirst(int key, int data) {
   struct node *link = (struct node*) malloc(sizeof(struct node));
   Link->key = key;
   Link->data = data;
   if (isEmpty()) {
      head = link;
      head->next = head;
   } else {
      Link->next = head;
      head = link;
   }
}
struct node * deleteFirst() {
   struct node *tempLink = head;
   if(head->next == head) {
      head = NULL;
      return tempLink;
   }
   head = head->next;
   return tempLink;
}
void printList() {
   struct node *ptr = head;
   printf(“\\n[ “);
   if(head != NULL) {
      while(ptr->next != ptr) {
         printf(“(%d,%d) “,ptr->key,ptr->data);
         Ptr = ptr->next;
      }
   }
   printf(“ ]”);
}
void main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf(“Original List: “);
   printList();
   while(!isEmpty()) {
      struct node *temp = deleteFirst();
      printf(“\\nDeleted value:”);
      printf(“(%d,%d) “,temp->key,temp->data);
   }
   printf(“\\nList after deleting all items: “);
   printList();
}

Double Linked List

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};
struct node *head = NULL;
struct node *last = NULL;
struct node *current = NULL;
bool isEmpty() {
   return head == NULL;
}
int length() {
   int length = 0;
   struct node *current;
   For(current = head; current != NULL; current = current->next){
      Length++;
   }
   return length;
}
void displayForward() {
   struct node *ptr = head;
   printf(“\\n[ “);
   while(ptr != NULL) {
      printf(“(%d,%d) “,ptr->key,ptr->data);
      Ptr = ptr->next;
   }
   printf(“ ]”);
}
void displayBackward() {
   struct node *ptr = last;
   printf(“\\n[ “);
   while(ptr != NULL) {
      printf(“(%d,%d) “,ptr->key,ptr->data);
      Ptr = ptr ->prev;

   }
}
void insertFirst(int key, int data) {
   struct node *link = (struct node*) malloc(sizeof(struct node));
   Link->key = key;
   Link->data = data;
   if(isEmpty()) {
      last = link;
   }
   else {
      head->prev = link;
   }
   Link->next = head;
   head = link;
}
void insertlast(int key, int data) {
   struct node *link = (struct node*) malloc(sizeof(struct node));
   Link->key = key;
   Link->data = data;
   if(isEmpty()) {
      last = link;
   }
   else {
      last->next = link;
      Link->prev = last;
   }
   last = link;
}
struct node* deleteFirst() {
   struct node *tempLink = head;
   if(head->next == NULL){
      last = NULL;
   }
   else {
      head->next->prev = NULL;
   }
   head = head->next;
   return tempLink;
}
struct node* deletelast() {
   struct node *tempLink = last;
   if(head->next == NULL) {
      head = NULL;
   }
   else {
      last->prev->next = NULL;
   }
   last = last->prev;
   return tempLink;
}
struct node* delete(int key) {
   struct node* current = head;
   struct node* previous = NULL;
   if(head == NULL) {
      return NULL;
   }
   while(current->key != key) {
      if(current->next == NULL) {
         return NULL;
      }
      else {
         Previous = current;
         current = current->next;
      }
   }
   if(current == head) {
      head = head->next;
   }
   else {
      current->prev->next = current->next;
   }
   if(current == last) {
      last = current->prev;
   }
   else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data) {
   struct node *current = head;
   if(head == NULL) {
      return false;
   }
   while(current->key != key) {
      if(current->next == NULL) {
         return false;
      }
      else {
         current = current->next;
      }
   }
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = newKey;
   newLink->data = data;
   if(current == last) {
      newLink->next = NULL;
      last = newLink;
   }
   else {
      newLink->next = current->next;
      current->next->prev = newLink;
   }
   newLink->prev = current;
   current->next = newLink;
   return true;
}
void main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf(“\\nList (First to last): “);
   displayForward();
   printf(“\\n”);
   printf(“\\nList (last to first): “);
   displayBackward();
   printf(“\\nList , after deleting first record: “);
   deleteFirst();
   displayForward();
   printf(“\\nList , after deleting last record: “);
   deletelast();
   displayForward();
   printf(“\\nList , insert after key(4) : “);
   insertAfter(4,7, 13);
   displayForward();
   printf(“\\nList  , after delete key(4) : “);
   delete(4);
   displayForward();
}