CODEWITHSUNDEEP
cdoubly-linked-listtail
idkusrname126
idkusrname126

Reputation: 117

doubly linked tail delete o(1) time

Im trying to delete from the end of a linked list using a tail pointer, but I can't seem to get it.

typedef struct node
{
    int data;
    struct node *next;
    struct node *prev;
} node;

typedef struct LinkedList
{
    node *head;
    node *tail;
} LinkedList;

// Deletes from the head of the list using a head                                 pointer
void doubly_head_delete(LinkedList *list)
{
    if (list->tail->prev == NULL)
    {
        list->head = list->head->next;
        list->head->prev = NULL;
    }
    else
    {
        list->tail->prev->next = list->tail->next;
        list->tail->next->prev = list->tail->prev;
    }
}

// Deletes the tail of the list using a tail pointer
void doubly_tail_delete(LinkedList *list)
{
    if (list == NULL || list->head == NULL)
        return;
    if (list->head != list->tail)
    {
        list->tail = list->tail->prev;
        list->tail->next = NULL;
        list->tail = list->tail->prev;
    }
    else
    {
        list->head = list->tail = NULL;
    }
}

I don't think the tail delete function is working because I can't figure out how to properly free the tail. Also, im not exactly sure how to set the tail pointer to the tail of the list. As for the head_delete(), it seems to be working but i am not sure exactly how, or if it is actually correct, or if it is just a coincidence that it works. Im still trying to learn this and the internet doesn't seem to have the best examples. Thanks

Upvotes: 0

Views: 63

Answers (1)

vmp
vmp

Reputation: 2420

You need to keep the address before changing the pointer.

void doubly_tail_delete(LinkedList *list)
{
   if (list == NULL || list->head == NULL)
      return;
   if (list->head != list->tail)
   {
       node *todelete = list->tail;
       list->tail = list->tail->prev;
       list->tail->next = NULL;
       //the next line you had is wrong.
       //list->tail = list->tail->prev;
       free(todelete);
   }
   else
   {
      free(list->head); //free it here before setting as NULL otherwise you lose the reference.
      list->head = list->tail = NULL;
   }
}

You are also not freeing while deleting from head... And there were a few bugs on it.

void doubly_head_delete(LinkedList *list)
{
   if (list == NULL || list->head == NULL)
      return;

   if (list->tail->prev == NULL)
   {
       free(list->head);
       list->head = list->tail = NULL;
   }
   else
   {
       node *todelete = list->head;
       list->head = list->head->next;
       list->head->prev = NULL;
       free(todelete);
   }
}

Upvotes: 2

Related Questions