1
\$\begingroup\$

I was trying to implement a deque using a singly LL when I realized that eject() (popping the tail element) wasn't going to work without a pointer to the previous element.

A few implementations I've seen online seem to use a node struct as well as a queue struct, so I'm starting to think I might've really messed this thing up (although it somehow seems to work).

I'm only including the 4 main functions; push() pop() inject() and eject().

Any feedback is welcome. A few things on my mind besides optimization issues: how would you test the robustness of something like this? I ran tests "manually" but clearly nothing exhaustive. Also I wanted to return an actual value for pop() and eject() instead of just printing it, but I'm not sure what to do when the list is empty. As of right now I end up returning zero with a message, but that feels...not amazing.

EDIT: This is obviously a lot of code butpop()/eject() and push()/inject() are very similar; so if you don't have time to look at the whole thing, feedback on pop() and push() would already be great, or even just one of them.

typedef struct node{
    int value;      
    struct node* next;
    struct node* previous;      
}node;

node* head = NULL;
node* tail = NULL;

int head_value();
int tail_value();
void push(int);
int pop();
void inject(int);
int eject();

int size = 0;

void push(int value)
{
    if (head == NULL)
    {       
        head = malloc(sizeof(node));
        head->value = value;
        head->next = NULL;
        head->previous = NULL;
        tail = head;
        size++;
    }
    else
    {
        node* new_node = malloc(sizeof(node));
        new_node->value = value;
        new_node->next = head;
        new_node->next->previous = new_node;
        head = new_node;
        new_node->previous = NULL;
        size++;     
    }   
}

int pop()
{   
    if (head == NULL)
    {
        printf("List Empty\n");     
        return 0;
    }

    node* temp = head;
    int value = temp->value;        
    head = head->next;
    free(temp);
    if (head != NULL)
        head->previous = NULL;
    size--;
    if (size == 0)
        tail = NULL;
    return value;
}

void inject(int value)
{
    if (tail == NULL)
    {               
        tail = malloc(sizeof(node));
        tail->value = value;
        tail->next = NULL;
        tail->previous = NULL;
        head = tail;
        size++;
    }
    else
    {
        node* new_node = malloc(sizeof(node));      
        new_node->value = value;
        tail->next = new_node;
        new_node->previous = tail;
        tail = new_node;
        new_node->next = NULL;
        size++;
    }
}

int eject()
{
    if (tail == NULL)
    {
        printf("List Empty\n");     
        return 0;
    }

    int value = tail->value;
    node* temp = tail;
    tail = temp->previous;
    free(temp);
    if (tail != NULL)
        tail->next = NULL;
    size--; 
    if (size == 0)
        head = NULL;
    return value;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.