We want to erase a node from the middle of our linked list. How can we do that?

Question

We want to erase a node from the middle of our linked list. How can we do that? We want to keep the remaining linked list attached and the same. Just remove one node from the middle that has a certain index number. This is one of the powerful and most fundamental properties of a linkedlist: you can add/remove a node from the middle of the linked list without changing the remaining linked list and without doing any shifting operations. You need to work with the code attached with this assignments. You will find that you have multiple files: item.h, status.h, node.h, linkedlist.h, linkedlist.c, main.c. The main.c contains a program to test your code after your correctly complete it. Your output should look like the following if you correctly implement the erase function: Current linkedlist: 10 20 30 40 50 After erasing at index 1: 10 30 40 50 Try to access index 10 (invalid): 0 You should also handle the case if someone gives an invalid index. For example, the linked list has only 5 elements and someone tries to access index 10. You need to completely solve the insert function and handle all the different cases.

#include <stdlib.h>
#include <stdio.h>
#include "linkedlist.h"
#include "node.h"

struct linkedlist
{
Node_Ptr front;
};

typedef struct linkedlist LinkedList, * LinkedList_Ptr;

// initializing and allocating the memory for our linkedlist
LinkedList_Ptr linkedlist_init_default()
{
// allocating the memory for my linkedlist
LinkedList_Ptr pLinkedList = malloc(sizeof(LinkedList));
  
// check if the memory was successfully allocated
if(pLinkedList != NULL)
{
// setting the front to NULL as the linkedlist is empty
pLinkedList->front = NULL;
}

return pLinkedList;
}

// Takes the handle to the linkedlist and the item to add to the
// end of the linkedlist
Status linkedlist_push_back(LinkedList_Ptr hLinkedList, Item item)
{
// making sure that the linkedlist was allocated
if(hLinkedList == NULL)
{
return FAILURE;
}

// list is empty, allocate memory for the front node (first node)
if(hLinkedList->front == NULL)
{
hLinkedList->front = malloc(sizeof(Node));
// check if memory was allocated
if(hLinkedList->front == NULL)
   {
   return FAILURE;
   }
// hold the input item
hLinkedList->front->data = item;
// set the next to NULL
hLinkedList->front->next = NULL;
}
else
{
Node_Ptr current = hLinkedList->front;
while(current->next != NULL)
   {
   current = current->next;
   }
Node_Ptr temp = malloc(sizeof(Node));
if(temp == NULL)
   {
   return FAILURE;
   }
temp->data = item;
temp->next = NULL;
current->next = temp;
}
return SUCCESS;
}

// removes the last node in the linkedlist
Status linkedlist_pop_back(LinkedList_Ptr hLinkedList)
{
if(hLinkedList == NULL || hLinkedList->front == NULL)
{
return FAILURE;
}
  
// removing the first node (the linkedlist only have one node)
if(hLinkedList->front->next == NULL)
{
free(hLinkedList->front);
hLinkedList->front = NULL;
}
else
{
//
Node_Ptr current = hLinkedList->front->next;
Node_Ptr previous = hLinkedList->front;
while(current->next != NULL)
   {
   previous = current;
   current = current->next;
   }

free(current);
previous->next = NULL;
}
  
return SUCCESS;
}

void linkedlist_display(LinkedList_Ptr hLinkedList)
{
if(hLinkedList != NULL)
{
Node_Ptr current = hLinkedList->front;
while(current != NULL)
   {
   printf("%d ", current->data);
   current = current->next;
   }
}
}

Status linkedlist_insert(LinkedList_Ptr hLinkedList, Item item, int index)
{
return FAILURE;
}

Status linkedlist_erase(LinkedList_Ptr hLinkedList, int index)
{
return FAILURE;
}

void linkedlist_destroy(LinkedList_Ptr* phLinkedList)
{
if(*phLinkedList != NULL)
{
if((*phLinkedList)->front != NULL)
   {
   Node_Ptr current = (*phLinkedList)->front;
   Node_Ptr next = (*phLinkedList)->front->next;
   while(next != NULL)
   {
   free(current);
   current = next;
   next = next->next;
   }
   free(current);
   }
free(*phLinkedList);
*phLinkedList = NULL;
}
}

#ifndef LINKED_LIST_H_
#define LINKED_LIST_H_

#include "status.h"
#include "item.h"

typedef struct linkedlist * LinkedList_Ptr;

// initialization for the linkedlist
LinkedList_Ptr linkedlist_init_default();

// add an item to the end of the linkedlist
Status linkedlist_push_back(LinkedList_Ptr hLinkedList, Item item);

// removes an item from the end of the linkedlist
Status linkedlist_pop_back(LinkedList_Ptr hLinkedList);

// display function to see what we have inside the linkedlist
void linkedlist_display(LinkedList_Ptr hLinkedList);

Status linkedlist_insert(LinkedList_Ptr hLinkedList, Item item, int index);

Status linkedlist_erase(LinkedList_Ptr hLinkedList, int index);

void linkedlist_destroy(LinkedList_Ptr* phLinkedList);

#endif

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

int main(int argc, char* argv[])
{
LinkedList_Ptr hLinkedList = linkedlist_init_default();
linkedlist_push_back(hLinkedList, 10);
linkedlist_push_back(hLinkedList, 20);
linkedlist_push_back(hLinkedList, 30);
linkedlist_push_back(hLinkedList, 40);
linkedlist_push_back(hLinkedList, 50);

printf("Current linkedlist: ");
linkedlist_display(hLinkedList);

linkedlist_erase(hLinkedList, 1);

printf("After erasing at index 1: ");
linkedlist_display(hLinkedList);

//Should be invalid index now
printf("Try to access index 10 (invalid): %d ", linkedlist_erase(hLinkedList, 10));

linkedlist_destroy(&hLinkedList);
return 0;
}

#ifndef NODE_H_
#define NODE_H_

#include "status.h"
#include "item.h"

struct node;
typedef struct node Node, * Node_Ptr;

struct node
{
Item data;
Node_Ptr next;
};

#endif // NODE_H_

Explanation / Answer

Status linkedlist_erase(LinkedList_Ptr hLinkedList, int index)
{
if(hLinkedList == NULL || hLinkedList->front == NULL)
    {
      return FAILURE;
    }
if(hLinkedList->front->next == NULL && index == 0)
    {
      free(hLinkedList->front);
      hLinkedList->front = NULL;
      return SUCCESS;
    }
Node_Ptr current = hLinkedList->front->next;
Node_Ptr previous = hLinkedList->front;
int i = 0;
while(current->next != NULL && i != index)
      {
      previous = current;
      current = current->next;
      i++;
     }
   if(i == index && current->next != NULL){
       previous->next = current->next;
       free(current);
       return SUCCESS;
   }
   if(i == index && current->next == NULL){
       free(current);
        previous->next = NULL;
       return SUCCESS;
   }
return FAILURE;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.