-4

I'm pretty rusty in C++ and I'm trying to implement a double linked list but I am having some reading violations and having some odd values being given.

    #include <iostream>

struct Node
    {
      int val;
      Node* next;
      Node* prev;
};

class linkedList
{
  public:
    linkedList(); //constructor
    ~linkedList(); //destructor
    void push_back(int x);
    void addtofront(int x);
    //void deleteNode(int x);
    bool isempty();
    void firstelem();
    void prnt_tail();
    /*void insert_after(int x, int y);
    void insert_before(int x, int y);*/
  private:
    
    Node* head;
    Node* next;
    Node* prev;


};


linkedList::linkedList(){};


linkedList::~linkedList(){};


void linkedList::push_back(int x)
{
    linkedList* list = this;
    Node temp;
    temp.val=x;
    temp.next=NULL;
    temp.prev=NULL;
    if (!head)
  {
    linkedList* list = new linkedList();
    list->head;
    head = new Node;
    head->val = x;
    head->next = NULL;
    head->prev = NULL;
  }
  else
  {
    Node* temp1;
    temp1=head;
    while (temp1->next!=NULL)
    {
        temp1 = temp1->next;
    }

    temp.next= NULL; 
    temp.prev=temp1;
    temp.val = x;

  }
};

void linkedList::addtofront(int x)
{
    linkedList* list = this;
    Node temp;
    temp.val=x;
    temp.next=NULL;
    temp.prev=NULL;
    if (!head)
  {
    linkedList* list = new linkedList();
    list->head;
    head = new Node;
    head->val = x;
    head->next = NULL;
    head->prev = NULL;
  }
    else
    {
        list->head->prev=&temp;
        temp.next=head;
        head=&temp;
    }
};

//void linkedList::deleteNode(int x)
//{
//  if(head)
//  {
//      linkedList *ptr = head;
//      while(ptr->node.val != x)
//      {
//          ptr = ptr->node.next;
//      }
//      (ptr->node.next)->prev=ptr->node.prev;
//      ptr->node.prev=ptr->node.next;
//      delete ptr;
//  }
//  else
//      std::cout<<"empty list";
//}


bool linkedList::isempty()
{
    if(head)
        return false;
    else return true;
};


void linkedList::firstelem()
{
    std::cout<<head->val;
};


void linkedList::prnt_tail()
{
    if(head)
    {
        Node *temp;
        temp=head;
        temp=head->next;
        std::cout<<temp;
        while(temp->next!=NULL)
        {
            std::cout<<temp->val<<" ";
        }
        std::cout<<temp->val;
    }
    else
    {
        std::cout<<"empty list";
    }
    
};


//linkedList::insert_after(int x, int y)
//{
//
//}
//
//linkedList::insert_before(int x, int y)
//{
//
//}

and my main

#include "linkedlist2.h"
#include <stdlib.h>
#include <iostream>



int main()
{
    linkedList example;
    if(example.isempty())
        std::cout<<"this list is empty "<<"\n";
    else
        std::cout<<"this list is not empty"<<"\n";
    for (int i = 1; i<=20; i++)
    {
        example.push_back(i);
        //example.prnt_tail();
    }
    example.addtofront(25);
    example.firstelem();
    std::cout<<"\n";
    example.addtofront(28);
    example.firstelem();
    std::cout<<"\n";
    if(example.isempty())
        std::cout<<"this list is empty "<<"\n";
    else
        std::cout<<"this list is not empty"<<"\n";
    
    //example.push_back(26);
    //std::cout<<example.head->next->val;
    example.firstelem();
    std::cout<<"\n";
    example.prnt_tail();
    std::cout<<"\n";
    system("pause");
}

when I run main I get

this list is empty

-858993460

-858993460

this list is not empty

-858993460

CCCCCCCC

I also get the error

Access violation reading location 0xCCCCCCD0.

and the next statement to be executed is the while loop in "void linkedList::prnt_tail()"

I'm fairly sure my problem is in my pointers and all that. Like I said, I'm really rusty so any help you can give would be greatly appreciated, even in things not directly related to my problems.

Community
  • 1
  • 1
Rob
  • 109
  • 2
  • 8
  • 2
    Don't reinvent the wheel. Use [`std::list`](http://en.cppreference.com/w/cpp/container/list); if you want to learn, use a debugger to find out about the pointers' values. – Basile Starynkevitch Jan 21 '14 at 19:17
  • 1
    @BasileStarynkevitch Can one not do an exercise to sharpen their skills? – BWG Jan 21 '14 at 19:18
  • 1
    In `addToFront` there are 2 weird things. The first one is that you are creating a new instance of `linkedList` when you could do `this->head = head`. The second is that you are using `temp` outside the function but its scope is the function `addToFront`. – wendelbsilva Jan 21 '14 at 19:28
  • 2
    You're not even initializing the members. Once you do that, step through the code by hand. Don't use a debugger, think before you write instead. (There are enough problems for an essay in there.) – molbdnilo Jan 21 '14 at 19:29
  • 0xCCCCCCD0 looks like you are using uninitialized memory. http://stackoverflow.com/questions/370195/when-and-why-will-an-os-initialise-memory-to-0xcd-0xdd-etc-on-malloc-free-new – drescherjm Jan 21 '14 at 19:44

4 Answers4

3

So, there's a lot of problems in this code. Let's see what we can do:

  1. It's odd that you have next and prev members in both your node objects and your linkedList objects. Let's fix this by making the linkedList object point to the first node (that is, the head node), and then use the members in each node to point to the next object.

    This means that we have:

    struct Node {
    int val;
    struct Node* next;
    struct Node* prev;
};

class linkedList {
    public:
        linkedList(); //constructor
        ~linkedList(); //destructor

        void push_back(int x);
        void addtofront(int x);
        bool isempty();

    private:
        Node* head;
};

  2. Let's fix a number of errors in your push_back. First, no matter what the state of the linkedList is, we need to create a new Node on the heap, and then we will be placing that Node somewhere in the linkedList.

    void linkedList::push_back(int x)
{
    Node *node = new Node;
    node->next = NULL;
    node->prev = NULL;
    node->val = x;

    if (head == NULL) {
        head = node;
    } else {
        Node *last = head;
        while (last->next != NULL)
            last = last->next;
        last->next = node;
        node->prev = last;
    }
}

  3. We also need to fix push_front. This code should look somewhat similar to push_back.

    void linkedList::addtofront(int x)
{
    Node *node = new Node;
    node->next = NULL;
    node->prev = NULL;
    node->val = x;

    if (head == NULL) {
        head = node;
    } else {
        node->next = head;
        head->prev = node;
        head = node;
    }
}

  4. If you're going to write a constructor, you probably should do that correctly:

    linkedList() {
    head = NULL;
}

  5. It's also worth noting that you will want a real destructor to clean up all of these objects that you are creating on the heap. And then you also need to implement the copy constructor and assignment operator.

Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
1

Apart from a extra useless semicolon, this looks wrong:

linkedList::linkedList(){};

A constructor is supposed to provide initial values for members, and you haven't done so. Leaving pointer members uninitialized is very bad style, and is the cause of many of your problems.

Because these members aren't initialized, when you later read from them (e.g. isEmpty()'s test if (head)) it will be undefined behavior.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
0

To start with, in addToFront and push_back you probably do not want to be creating new linked lists on the heap. You already have a linked list (the one the method is currently being run on) which you want to modify. Don't create new linked lists here.

However, you DO want to create new Nodes on the heap, never on the stack. In at least one place you create a node on the stack, eg 

Node temp;

And then later store and use a pointer to that object. As soon as the function quits, that variable is gone and that pointer is pointing to garbage.

bdk
  • 4,769
  • 29
  • 33
-1

in linked list class , (Node* next;) and (Node* prev;) are extera

Farhad Dalirani
  • 1