How to create a previous pointer in a linked list in C++?

Question

I have created a LinkedList class that has a function for deleting the first element in the list and one that deletes the last element in the list. The first one is easy, after I delete the element, I set it to point to the next element. Works great. However, when I delete the last element, I have to point it to the previous element in the list which becomes the last at that point. I cannot figure out how to do this. Please advise. Here is the code:

    void LinkedList::pop_front()
{
    mFront->data = NULL;
    mFront = mFront->next;
}

How can I get a function to delete the last element but reset the tail to point to the new tail?

void LinkedList::pop_back()
{
mBack->data = NULL;
...
}

class LinkedList
{
    public:

        // Default Constructor
        // Purpose: Initializes an empty list
        // Parameters: none
        // Returns: none
        LinkedList();

        // The push_front function
        // Purpose: add an item to the front of the list
        // Parameters: a int item for the front
        // Returns: none        
        void push_front(int data);

        // The push_back function
        // Purpose: insert an item into the back of the list
        // Parameters: int item to add the the back
        // Returns: none                
        void push_back(int data);

        // The pop_front function
        // Purpose: delete the item in the front of the list
        // Parameters: none
        // Returns: none
        void pop_front();

        // the pop_back function
        // Purpose: remove the item at the end of the list
        // Parameters: none
        // Returns: none        
        void pop_back();

        // The getFirst function
        // Purpose: print the first item in the list
        // Parameters: none
        // Returns: none
        void getFirst();

        // the GetLast function
        // Purpose: return the last item in the list
        // Parameters: none
        // Returns: none
        void getLast();

        void printList();

        // the clear function
        // Purpose: clear the list, free memory
        // Parameters: none
        // Returns: none
        void clear();

        // Destructor
        // Purpose: clear up memory
        // Parameters: none
        // Returns: none
        ~LinkedList();

    private:

            LinkedList *mFront; //  point to the front of our list
            LinkedList *mBack; // point to the back of our list
            LinkedList *next;  // the next node
            LinkedList *previous; // the previous node
            int data;  // our list data manipulator

If you want O(1) removal of elements, you'll need a doubly linked list (i.e. next and prev pointers on all nodes). — Mike DeSimone
– Mike DeSimone, Commented Apr 18, 2012 at 21:03
If this is homework, it is a good idea to add the homework tag so that people can try to give more explanations and less code. — thiton
– thiton, Commented Apr 18, 2012 at 21:06

thiton · Accepted Answer · 2012-04-18 21:01:12Z

4

Singly linked lists do not offer O(1) deletion of the last element. You'll have to run through the whole list from the start to find the second-to-last element.

Node* i = mFront;
while ( i->next != mBack ) i = i->next;
mBack = i;

answered Apr 18, 2012 at 21:01

thiton

36.1k4 gold badges74 silver badges104 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Paxwell Over a year ago

it says Node is undefined. I am a beginner, do I need to reference a data member of the class there? Or, create a new pointer? I edited the code above to show my class name and data members.

Luchian Grigore · Accepted Answer · 2012-04-18 21:03:04Z

1

If the list isn't double linked, you'll have to start at the first element to find the last one:

void LinkedList::pop_back()
{
   mBack->data = NULL;
   current = mFront;
   do{
      current = current->next
   } while ( current->next );
   mBack = current;
}

Very important - since data appears to be a pointer, you're possibly running into a memory leak. Just setting data = NULL doesn't free the memory, you'll have to explicitly delete it:

delete mFront->data;

answered Apr 18, 2012 at 21:03

Luchian Grigore

260k68 gold badges465 silver badges634 bronze badges

1 Comment

Paxwell Over a year ago

Your code also gives me errors. I am not sure what current is referencing, I changed the code above to represent my class

Collectives™ on Stack Overflow

How to create a previous pointer in a linked list in C++?

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related