ICS121 – Data Structures I

ICS121 – Data Structures I. Module 1 Circular Linked List, Doubly Linked List, Doubly Circular Linked List and Applications.

Circular Linked List: Representation of Node: struct node.

Insertion Operation: Insertion at Beginning: struct node *ptr,*temp; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) Write “OVERFLOW"; else { Read item; ptr -> data = item; if(head == NULL) {.

Insertion Operation: Insertion at Last:. struct node *ptr,*temp; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) Write "OVERFLOW"; else { Read item; ptr->data = item;.

Deletion: Deletion at Beginning: struct node *ptr; if(head == NULL) Write "UNDERFLOW"; else if(head->next == head) else {.

} else { ptr = head;. Deletion: Deletion at Last: struct node *ptr, *ptr1; while(ptr ->next != head) else if (head ->next == head) ptr1->next = ptr -> next; free(head);.

Se. arching:. flag=0; } } if(flag != 0) else Write "Item not found";.

Tracing:. struct node *ptr; ptr=head; if(head == NULL) write "nothing to print"; else Write ptr -> data; }.

Doubly Linked List: Representation of Node: struct node.

Insertion Operation: Insertion at Beginning: struct node *ptr; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) write “OVERFLOW"; else { read item; if(head==NULL) { ptr->next = NULL;.

Insertion Operation: Insertion at Last: struct node *ptr,*temp; int item; ptr = (struct node *) malloc(sizeof(struct node)); if(ptr == NULL) write "OVERFLOW"; else { Read item; ptr->data=item; if(head == NULL).

Insertion Operation: Insertion at random position: struct node *ptr,*temp; Declare item, loc, i; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) Write “OVERFLOW"; else { temp=head; Read loc; for(i=0;i<loc;i++).

Deletion: Deletion at Beginning: struct node *ptr; if(head == NULL) Write “UNDERFLOW"; else if(head->next == NULL) else {.

head = NULL; free(head); } else { ptr = head;. Deletion: Deletion at Last: struct node *ptr; if(ptr->next != NULL) write “UNDERFLOW"; ptr ->prev -> next = NULL; else if(head->next == NULL) free(ptr);.

Deletion: Deletion at random: struct node *ptr, *temp; Declare val; Read an item to delete ptr = head; while(ptr -> data != val) ptr = ptr -> next; if(ptr -> next == NULL) Write “No item"; else if(ptr -> next -> next == NULL) { ptr ->next = NULL;.

Searching: struct node *ptr; declare item,i=0,flag; ptr = head; if(ptr == NULL) Write “empty list” else { Read search item; while (ptr!=NULL) { if(ptr->data == item) {.

Doubly Circular Linked List: Representation of Node: struct node.

Insertion Operation: Insertion at Beginning: struct node *ptr,*temp; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) Write "OVERFLOW"; else { Read item; ptr->data=item; if(head==NULL) { head = ptr; ptr -> next = head;.

Insertion Operation: Insertion at Last:. struct node *ptr,*temp; int item; ptr = (struct node *) malloc(sizeof(struct node)); if(ptr == NULL) Write "OVERFLOW"; else { Read item; ptr->data=item; if(head == NULL).

Deletion: Deletion at Beginning: struct node *temp; if(head == NULL) Write " UNDERFLOW"; else if(head->next == head) else {.

Deletion: Deletion at Last: struct node *ptr; if(head == NULL) write " UNDERFLOW"; else if(head->next == head) else {.

Searching:. struct node *ptr; Int item, i=0,flag=1; ptr = head; if(ptr == NULL) write “Empty List"; else else { while (ptr->next != head).

Tracing:. struct node *ptr; ptr=head; if(head == NULL) Write “empty list"; else write ptr -> data; }.

Advantage:. Easier to insert or delete data elements Dynamic data structure Memory efficient Implementation Disadvantage: Slow search operation and requires more memory space Backtracking or reverse traversing is difficult. In a doubly linked list, it is easier but requires more memory to store the back pointer. Applications: Implementing stacks, queues, binary trees, and graphs of predefined size. Implement dynamic memory management functions of the operating system. Polynomial implementation for mathematical operations Circular linked list is used to implement OS or application functions that require round-robin execution of tasks. Circular linked list is used in a slide show where a user wants to return to the first slide after the last slide is displayed. Doubly linked list is used in the implementation of forward and backward buttons in a browser to move backward and forward in the opened pages of a website. Circular queue is used to maintain the playing sequence of multiple players in a game..