How to pop element from tail in linked list?

Question

I am trying to learn linked list using various push and pop functions but I am not able to do popping of element from tail in linked list. Can anyone help me to solve popBack function?

I have tried something like:

typedef struct
{
  float val;
}data;

typedef struct nodePtr
{
  struct nodePtr *next;
  data *d;
}node;

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

linkList* createlinkList()
{
        linkList *ll = (linkList*)malloc(sizeof(linkList));
        ll->head = NULL;
        ll->tail = NULL;
        return ll;
}

node* createNode(data *d)
{
    node *nd = (node*)malloc(sizeof(node));
    nd-> d = d;
    nd-> next = NULL;
    return nd;
}

data* createData(float val)
{
    data *iptr = (data*)malloc(sizeof(data));
    iptr->val = val;
    return iptr;
}

void addFront(linkList *ll,data *d)
{
    node *new_node = createNode(d);
    if(ll->head == NULL && ll->tail == NULL )   
    {
        ll->head = new_node;
        ll->tail = new_node;
    }
    else
    {
        new_node->next = ll->head;
        ll->head = new_node;
    }
}

void addBack(linkList *ll,data *d)
{
    node *new_node = createNode(d);
    if(ll->head == NULL && ll->tail == NULL )   
    {
        ll->head = new_node;
        ll->tail = new_node;
    }
    else
    {
        ll->tail->next = new_node;
        ll->tail = new_node;
    }
}

void printList(linkList *ll)
{
    node *temp = ll->head;
    while(temp!=NULL)
    {
        printf("%f\n",temp->d->val);
        temp = temp->next;
        /*if(temp==ll->tail)
        {
            printf("%f\n",temp->d->val);
            break;
        }*/
    }
}

int listSize(linkList *ll)
{
    int size=0; 
    node *count;
    for(count=ll->head;count!=NULL;count=count->next)
    {
            size++;
    }
    return size;
}

data* popFront(linkList *ll)
{
    data *popf;
    popf = ll->head->d;
    node *temp = ll->head;
    ll->head = ll->head->next;
    free(temp);
    return popf;
}

**data* popBack(linkList *ll)
{
    data *popb;
    popb = ll->tail->d;
    while(ll->head->next!=NULL)
    {
        printf("%f\n",ll->head->next->d->val);
        if(ll->head->next==NULL)
        {
            node* temp = ll->head->next;
            free(temp);
        }
    }
    return popb;
}**

int main(int argc, char* argv[])
{
    linkList *ll = createlinkList();
    data *iptr = createData(11.10);
    addFront(ll,iptr);
    data *iptr1 = createData(10.10);
    addFront(ll,iptr1);
    data *iptr2 = createData(12.10);
    addBack(ll,iptr2);
    printList(ll);
    int count = listSize(ll);
    printf("%d\n",count);
    popFront(ll);
    printList(ll);
    popBack(ll);
    printList(ll);
  return 0;
}

Your if condition should check `count`. Also, don't forget to update tail — Leeor, Nov 01 '13 at 06:06
[Don't cast the return value of `malloc()`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — , Nov 01 '13 at 06:20
Without dual pointers (`prev` and `next`), that is going to be an O(n) algorithm, just so you know. That said, a fairly elegant solution using a single pointer-to-pointer variable is commonly used (well, maybe not commonly, but common by me=) — WhozCraig, Nov 01 '13 at 06:31

score 0 · Answer 1 · answered Nov 01 '13 at 07:00

You have a single-link list. You need to do several things. You need to find the node previous to the tail of the list (which only exists if there are 2 or more nodes on the list), and extract the tail (easy to find, you have a pointer to it).

Find the tail
Find the node prev(ious) to the tail
point the tail at the prev(ious) node
either set the prev(ious) next to NULL (removed), or
set the head to NULL (there was only one item on the list)

How to do that?

data* popBack(linkList *ll)
{
    node* prev; //need to find this
    node* iter; //iterator through list
    data *popb;
    if(!ll) return NULL; //list is non-existant
    if(!ll->head) return NULL; //list is empty
    prev=>NULL; //don't have a previous yet.
    iter=ll->head;
    while(iter!=ll->tail)
    {
        prev=iter; //not the tail, there must be a node after this
        iter=iter->next; //not null, could be tail
    }
    //iter==ll->tail, so prev must be either before tail or NULL (only 1 node on list)
    if( prev==NULL ) { ll->head=NULL; }
    else prev->next=NULL;
    printf("%f\n",ll->tail->d->val);
    popb = ll->tail->d;
    free(ll->tail); //free old tail
    ll->tail = prev;  //new tail
    return popb;
}

score 0 · Answer 2 · edited Oct 26 '14 at 14:21

hey rips to reverse the linked list.

you can reverse the linked list by going to last node, storing the last but one node in temporary node, and just reverse the pointers. Use recursion to make it simple.

if lastbutone->next->next=NULL
lastbutone= temporary

recursion
last->next=temporary;
last=temporary;

beware of the last and first node, give a name to the last node say headptr.. and when u arrive to the first node then assign null to its next.

score -1 · Answer 3 · answered Nov 01 '13 at 07:17

-1

data* popBack(linkList *ll)
{
data *popb;
popb = ll->tail->d;

node* ptrf = ll->head;
node* ptre = ll->tail;

if(ptrf == NULL && ptre == NULL){ //no node in the linkList
    return NULL;
}else if(ptrf == ptre){ //only one node in the linkList
    free(ptre);
    ptrf = ptre = NULL;
    return popb;
}else { //at least two nodes in the linkList
    while((ptrf->next) != ptre)
    {
        ptrf = ptrf->next;
    }
    free(ptre);
    ptrf->next = NULL;
    ll->tail = ptrf;
    return popb;
}
}

answered Nov 01 '13 at 07:17

TODD911

53
3

Thank you guys. Appreciated. – rips Nov 01 '13 at 21:30
I have one more question guys. How can I reverse the entire linked list? – rips Nov 01 '13 at 21:32

How to pop element from tail in linked list?

3 Answers3

Linked