15. A doubly linked list is one in which each node points not just to the next n
ID: 3906336 • Letter: 1
Question
15. A doubly linked list is one in which each node points not just to the next node in the linked list, but also the previous node in the linked list. The struct definition is: typedef struct node int data; struct node next struct node *prev node; Implement tail insert, headinser0, tail_delete0, head _delete0, and delete_Nth0 functions for doubly linked lists. Repeat these exercises with doubly linked lists in which you maintain a tail pointer. How does the tail pointer affect the runtimes of these functions? Are any of these functions more efficient for doubly linked lists with tail pointers than they are for singly linked lists with tail pointers?Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty() {
return head == NULL;
}
int length() {
int length = 0;
struct node *current;
for(current = head; current != NULL; current = current->next){
length++;
}
return length;
}
//insert link at the first location
void head_insert(int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void tail_insert(int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
//delete first item
struct node* head_delete() {
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL){
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
//delete link at the last location
struct node* tail_delete() {
//save reference to last link
struct node *tempLink = last;
//if only one link
if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
//return the deleted link
return tempLink;
}
//delete a link with given key
struct node* deleteNth(int data) {
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL) {
return NULL;
}
//navigate through list
while(current->data != data) {
//if it is last node
if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
current->prev->next = current->next;
}
if(current == last) {
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
void main() {
// your logic goes here
}
NOTE: Due to time limit, I could implement only the functions for doubly linked list only. Please post separately for the remaining implementation.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.