Reversing A Linked List

Having trouble reversing a linked list

Page 1 of 1

1 Replies - 1387 Views - Last Post: 04 November 2010 - 06:05 PM Rate Topic: -----

#1 Guest_Acompscihopeful*


Reputation:

Reversing A Linked List

Posted 04 November 2010 - 04:09 PM

I am currently trying to reverse a linked list, but when I try running the function I have created and then displaying the Linked List afterwords, I am always shown just the first item in the list. Could I have some help correcting this function.

HEADER FILE

#ifndef LINKEDLISTCLASS_H
#define LINKEDLISTCLASS_H

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

namespace SIMPLE
{
    class LinkedList
    {

    protected:
        struct ListNode
        {
            double value;
            ListNode *next;
            ListNode(double value1, ListNode *next1 = NULL)
            {
                value = value1;
                next = next1;
            }
        };
        ListNode *head;
    public:
        LinkedList() { head = NULL;    }
        LinkedList(const LinkedList& original);

        void recursiveIsMember(double value) { head = recursiveIsMember(head, value);}

        ~LinkedList();
        void add(double value);
        bool isMember(double value);
        
        void remove(double x);
        void displayList();

        ListNode *reverse();

    private:
        ListNode *recursiveIsMember(ListNode *aList, double value);
        static ListNode *copyList(ListNode *aList);
    };
}
#endif


FUNCTION IMPLEMENTATIONS

#include "Simple Linked List Class.h"


namespace SIMPLE
{
    void LinkedList::add(double x)
    {
        ListNode *nextPtr;



        if (head == NULL)
            head = new ListNode(x);
        else
        {
            nextPtr = new ListNode(head->value);
            nextPtr->value = x;
            nextPtr->next = head;
            head = nextPtr;
        }
    }

    bool LinkedList::isMember(double x)
    {
        ListNode *nodePtr;

        nodePtr = head;

        while (nodePtr != NULL)
        {
            if (nodePtr->value == x)
            {
                return true;
            }

            nodePtr = nodePtr->next;
        }

        return false;
    }

    void LinkedList::remove(double x)
    {
        ListNode *nodePtr, *previousNodePtr;

        if (!head) return;

        if (head->value == x)
        {
            nodePtr = head;
            head = head->next;
            delete nodePtr;
        }

        else
        {
            nodePtr = head;

            while (nodePtr != NULL && nodePtr->value != x)
            {
                previousNodePtr = nodePtr;
                nodePtr = nodePtr->next;
            }

            if (nodePtr)
            {
                previousNodePtr->next = nodePtr->next;
                delete nodePtr;
            }
        }
    }


    LinkedList::~LinkedList()
    {
        ListNode *ptr = head;
        while (ptr != NULL)
        {
            ListNode *garbage = ptr;
            ptr = ptr->next;

            delete garbage;
        }
    }

    LinkedList::ListNode *LinkedList::recursiveIsMember(ListNode *aList, double x)
    {


        if (aList == NULL)
        {
            cout << "\n" << x << " is not in the linked list.";
            return NULL;
        }

        if (aList->value == x)
        {
            cout << endl << x << " is in the linked list.";
            return aList;
        }
        else
        {
            aList->next = recursiveIsMember(aList->next, x);
            return aList;
        }

    }

    void LinkedList::displayList()
    {
        ListNode *nodePtr = head;
        while (nodePtr)
        {
            cout << endl << nodePtr->value << "     ";

            nodePtr = nodePtr->next;
        }
    }


    LinkedList::LinkedList(const LinkedList& original)
    {
        head = copyList(original.head);
    }

    LinkedList::ListNode *LinkedList::copyList(ListNode *aList)
    {
        if (aList == NULL)
            return NULL;
        else
        {
            ListNode *tailCopy = copyList(aList->next);

            return new ListNode(aList->value, tailCopy);
        }
    }

    //Function implementation for reversing the linked list
    LinkedList::ListNode *LinkedList::reverse()
    {
        ListNode *aList = head;
        ListNode *temp;
        ListNode *previousNodePtr = NULL;


        while (aList != NULL)
        {
            temp = aList->next;
            aList->next = previousNodePtr;
            previousNodePtr = aList;
            aList = temp;
        }
        return aList;
    }

}


MAIN

#include "Simple Linked List Class.h"

using SIMPLE::LinkedList;

int main()
{
    LinkedList list;
    

    list.add(8);
    list.add(6);
    list.add(5);

    if (!list.isMember(8))
        cout << "\nThe value is not in the linked list.";
    else
        cout << "\nThe value is in the linked list.";

    if (!list.isMember(5))
        cout << "\nThe value is not in the linked list.";
    else
        cout << "\nThe value is in the linked list.";

    list.recursiveIsMember(10);

    LinkedList otherList(list);

    list.remove(6);

    otherList.displayList();

    cout << endl;

    list.displayList();

    cout << endl;

    //Function call to reverse the list
    otherList.reverse();

    otherList.displayList();

    cout << endl;
    return 0;
}




The function is the one called ListNode *reverse.

Is This A Good Question/Topic? 0

Replies To: Reversing A Linked List

#2 RBSprogram101  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 38
  • Joined: 28-March 09

Re: Reversing A Linked List

Posted 04 November 2010 - 06:05 PM

You should look into doubly linked lists
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1