#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    38
    Rep Power
    3

    Linked List pop_back() and back()


    pop_back: Delete the element at the end of the list

    back: Returns the element at the end of the list

    Can someone take a look at the following methods. I have no idea why these methods are not working.

    Code:
     template<class T>
    void MyList<T>::pop_back()
    {
        Node<T> *cursor = head;
        while(cursor->next)
        {
            cursor = cursor->next;
        }
        delete cursor->next;
        cursor->next = NULL;
    }
    Code:
    template<class T>
    T MyList<T>::back()
    {
        return tail->element;
    }
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    I don't see enough information to answer your question. Last time this happened there was sufficient information---my error. Please show more code. How is the list constructed and that sort of thing. A complete, small program that displays the trouble would be good. If the program actually compiles then I'd like to see sample input and the output you expect.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    38
    Rep Power
    3
    My entire code.

    Code:
    #include <iostream>
    using namespace std;
    
    
    template<class T>
    class Node
    {
        public:
            template<class>friend class MyList;
            T element;
            Node* prev;
            Node* next;
            Node (T e)
            {
                element = e;
                prev = next = NULL;
            }
    };
    
    template <class T>
    class MyList
    {
        Node<T> *head, *tail;
        int count;
    
        public:
            MyList();
            ~MyList();
            void push_back(T data);
            void push_front(T data);
            void pop_front();
            void pop_back();
            void clear();
            T front();
            T back();
            int size()
            {
                int count = 0;
                Node<T> *cursor = head;
                while(cursor != NULL)
                {
                    cursor = cursor->next;
                    count++;
                }
                return count;
            }
            void reverse();
            void sort();
            void unique();
            T operator[] (int index);
    
    
    };
    
    template<class T>
    MyList<T>::MyList()
    {
        int count = 0;
        head = tail = NULL;
    }
    
    template<class T>
    MyList<T>::~MyList()
    {
        Node<T>* cursor = head;
        while (cursor != NULL)
        {
            Node<T>* next_ptr = cursor->next;
            delete cursor;
            cursor = next_ptr;
        }
    }
    
    template<class T>
    T MyList<T>::operator[] (const int index)
    {
        Node<T> *cursor = this->head;
    
        for(int x = 0; x < index; x++)
        {
            cursor = cursor->next;
        }
        return cursor->element;
    
    
    }
    
    template<class T>
    void MyList<T>::push_back(T data)
    
    {
        if(head == NULL)
        {
            head = new Node<T>(data);
        }
        else
        {
            Node<T> *cursor = head;
            while(cursor->next != NULL)
            {
                cursor = cursor->next;
            }
            cursor->next = new Node<T>(data);
        }
    }
    
    template<class T>
    void MyList<T>::push_front(T data)
    {
        Node<T> *cursor = new Node<T>(data);
        cursor->element = data;
        cursor->next = head;
        head = cursor;
        if(tail == NULL)
        {
            tail = cursor;
        }
    }
    
    template<class T>
    void MyList<T>::pop_front()
    {
        Node<T> *cursor = head;
        head = head->next;
        delete cursor;
        if(head == NULL)
        {
            tail = NULL;
        }
    }
    
    template<class T>
    void MyList<T>::pop_back()
    {
        Node<T> *cursor = head;
        while(cursor->next)
        {
            cursor = cursor->next;
        }
        delete cursor->next;
        cursor->next = NULL;
    }
    
    template<class T>
    void MyList<T>::clear()
    {
        head = NULL;
    }
    
    template <class T>
    T MyList<T>::front()
    {
        return head->element;
    }
    
    template<class T>
    T MyList<T>::back()
    {
        return tail->element;
    }
    
    template<class T>
    void MyList<T>::reverse()
    {
        if(head == NULL)
        return;
        Node<T> *prev = NULL, *cursor = NULL, *next = NULL;
        cursor = head;
        while(cursor != NULL)
        {
            next = cursor->next;
            cursor->next = prev;
            prev = cursor;
            cursor = next;
        }
        head = prev;
    }
    
    template<class T>
    void MyList<T>::sort()
    {
        Node<T> *cursor = NULL;
        while(cursor != head)
        {
            Node<T> *temp, *swap;
            swap = head;
            while( swap->next != cursor )
            {
                if(swap->element > swap->next->element)
                {
                    Node<T> *swap2 = swap->next;
                    swap->next = swap2->next;
                    swap2->next = swap;
                    if(swap == head)
                    {
                        head = swap2;
                        swap = swap2;
                    }
                    else
                    {
                        swap = swap2;
                        temp->next = swap2;
                    }
                }
                temp = swap;
                swap = swap->next;
            }
    
            cursor = swap;
        }
    
    
    }
    
    template<class T>
    void MyList<T>::unique()
    {
        sort();
    
        Node<T> *ptr1, *ptr2, *duplicate;
        ptr1 = head;
    
    
      while(ptr1 != NULL && ptr1->next != NULL)
      {
         ptr2 = ptr1;
    
    
         while(ptr2->next != NULL)
         {
    
           if(ptr1->element == ptr2->next->element)
           {
    
              duplicate = ptr2->next;
              ptr2->next = ptr2->next->next;
              (duplicate);
           }
           else
           {
              ptr2 = ptr2->next;
           }
         }
         ptr1 = ptr1->next;
      }
    
    }
    
    
    template <class T>
    void print(MyList<T>& l)
    {
        for (int x = 0; x < l.size(); x++)
            cout << l[x] << " ";
        cout << endl;
    }
    
    int main()
    {
        MyList<string> l;
        cout << "-- push_front push_back test --" << endl;
        l.push_back("one");
        l.push_back("two");
        l.push_back("three");
        l.push_back("four");
        l.push_back("five");
        l.push_back("six");
        l.push_front("zero");
        l.push_front("neg-one");
        l.push_back("six");
        print(l);
    
        cout << "-- pop_front pop_back test 1 --" << endl;
        l.pop_front();
        l.pop_back();
        print(l);
    
        cout << "-- clear test (should be blank) --" << endl;
        l.clear();
        print(l);
    
        cout << "-- front back test 1 --" << endl;
        l.push_back("apple");
        l.push_back("orange");
        l.push_back("happy meal");
        l.push_front("whopper");
        cout << l.front() << " " << l.back() << endl;
    
        cout << "-- front back test 2 --" << endl;
        l.push_back("finance");
        l.push_back("google");
        l.push_back("green");
        print(l);
    
        cout << "-- reverse test --" << endl;
        l.reverse();
        print(l);
    
        cout << "-- sort test --" << endl;
        l.sort();
        print(l);
    
        cout << "-- unique test --" << endl;
        l.push_back("aapl");
        l.push_back("aapl");
        l.push_front("goog");
        l.push_back("goog");
        l.push_back("happy meal");
        l.unique();
        print(l);
    
        cout << "-- pop_front pop_back test 2 --" << endl;
        l.pop_back();
        l.pop_front();
        l.pop_back();
        print(l);
    }
    Expected output

    -- push_front push_back test --
    neg-one zero one two three four five six six
    -- pop_front pop_back test 1 --
    zero one two three four five six
    -- clear test (should be blank) --

    -- front back test 1 --
    whopper happy meal
    -- front back test 2 --
    whopper apple orange happy meal finance google green
    -- reverse test --
    green google finance happy meal orange apple whopper
    -- sort test --
    apple finance google green happy meal orange whopper
    -- unique test --
    aapl apple finance goog google green happy meal orange whopper
    -- pop_front pop_back test 2 --
    apple finance goog google green happy meal


    Originally Posted by b49P23TIvg
    I don't see enough information to answer your question. Last time this happened there was sufficient information---my error. Please show more code. How is the list constructed and that sort of thing. A complete, small program that displays the trouble would be good. If the program actually compiles then I'd like to see sample input and the output you expect.
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    I'm not a C++ expert and made the mistake of asking for more information. Your new post looks complete! I examined your code.

    1) Compilation with gcc -Wall revealed a few problems. Removing all of the unused variables and statements fixed the problems.

    2) You don't use the count member. I removed it.

    3) You've used the tail member only once. The rest of the time you read through the entire list from the head when you need the tail. In this case I think you've misused tail. Remember, it appears once in a useful way. Where I have marked a source line with a bunch of slashes it sure looks like you should have written
    tail = head = new Node<T>(data);
    Code:
    template<class T>
    void MyList<T>::push_back(T data) {
      if(NULL == head)
        head = new Node<T>(data);/////////HERE
      else {
        Node<T> *cursor = head;
        while(NULL != cursor->next)
          cursor = cursor->next;
        cursor->next = new Node<T>(data);
      }
    }
    That change doesn't alter the output.

    4) pop_back is questionable:
    Code:
    template<class T>
    void MyList<T>::pop_back() {
      Node<T>*cursor = head;
      //////////what if head is NULL?????
      //////////////// why don't you change tail????
      while(cursor->next)
        cursor = cursor->next;
      delete cursor->next;
      cursor->next = NULL;
    }
    5) clear() is questionable:
    Code:
    template<class T>
    void MyList<T>::clear() {
      /////////////// what about tail?
      /////////////// what about leaking all the memory between head and tail?
      head = NULL;
    }
    OK, I stopped looking at reverse.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    Code:
     template<class T>
    void MyList<T>::pop_back()
    {
        Node<T> *cursor = head;
        while(cursor->next)
        {
            cursor = cursor->next;
        }
        delete cursor->next;
        cursor->next = NULL;
    }
    Well, think about it. You set cursor to cursor->next in a loop. When do you stop? When cursor->next is NULL. Then you proceed to delete cursor->next, which you know is NULL. You can't delete NULL.

    Pay attention to b's post as well. Some parts of your code clearly indicate that your data structure is a doubly linked list with head and tail pointers, but much of your code ignores the `tail' and `prev' links completely, notably pop_back() and push_back(). But then you dereference tail in back(), which is probably garbage by the time you get to it after doing operations on the list that corrupt the data structure.

IMN logo majestic logo threadwatch logo seochat tools logo