Linked list using 2 structs and pointers

pce369 0 Tallied Votes 428 Views Share

I wrote a linked list program in C++ which compiles and works well. But I have been told that

a) I have to have two separate structs instead of one that contains both the info and the node; and,
b) that I have to use two pointers instead of the "count++" scheme I am using.

I have included the preprocessing section, the struct definition, the functions and the initial part of main() above - the rest a menu, etc.

Can anyone provide advice? Thanks kindly!

pce369

#include<iostream>
#include<cstdlib>
using namespace std;

struct node                     
{                               

     int count;       
     int data, serial;      
     node* ptr;              
     node()              //somehow I have to break this struct into two    
     {                       
          data = 0;              
          ptr = NULL;            
         serial=count;          
          count++;       //I have to eliminate this count scheme in favor of two pointers        
     }                       

};                              


//function protocols here, omitted from this snippet...

int main()
{
    node* start;        //but arent these the two
    node* current;      //pointers being referred to?
    start = current = NULL;
    char ch;
    int temp, i;
Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster

Advice? Yes,just do as you were told. What don't you understand about the instructions? What have you done so far to correct your program?

node* start; //but arent these the two
//pointers being referred to?

No. He means to put two pointers inside he structore, one for next and the other for previous nodes within the linked list.

Labdabeta 182 Posting Pro in Training Featured Poster

I think this is what you are looking for:

template <typename T>//allow for any type of node
class LinkedListNode
{
    private:
    T value;                    //store the value
    LinkedListNode<T> *next;    //store a pointer to the next node
    LinkedListNode<T> *prev;    //store a pointer to the previous node
    public:
    //getters:
    T getVal(){return value;}
    LinkedListNode<T> &getNext(){return *next;}
    LinkedListNode<T> &getPrev(){return *prev;}
    //setters:
    LinkedListNode<T> &setVal(const T &val){value=val;return *this;}
    LinkedListNode<T> &setNext(LinkedListNode<T> *n){next=n;return *this;}
    LinkedListNode<T> &setPrev(LinkedListNode<T> *p){prev=p;return *this;}
};
template <typename T>//allow for any type of list
class LinkedList
{
    private:
    LinkedListNode<T> *nodes;   //store all the nodes
    size_t numNodes;            //store the total number of nodes
    public:
    LinkedList()
    {
        nodes=NULL;
        numNodes=0;
    }
    LinkedListNode<T> &operator[](size_t index)
    {
        if (index>numNodes)//no need to check lower bound, size_t is unsigned
            exit(1);//or abort in some other way (throw an error if you're into that)
        return nodes[index];
    }
    LinkedList<T> &push(const T &val)
    {
        //the following is just standard dynamic memory management
        LinkedListNode<T> *tmpNodes=new LinkedListNode<T>[numNodes+1];
        for (size_t i=0; i<numNodes; ++i)
            tmpNodes[i]=nodes[i];
        if (numNodes>1)
        {
            tmpNodes[numNodes-1].setNext(&tmpNodes[numNodes]);
            tmpNodes[numNodes].setPrev(tmpNodes[numNodes-1]).setNext(NULL).setVal(val);
        }
        else
            tmpNodes[numNodes].setPrev(NULL).setNext(NULL).setVal(val);
        if (numNodes>0)
            delete[]nodes;
        nodes=tmpNodes;
        numNodes++;
        return *this;
    }
    LinkedList<T> &pop()
    {
        if (numNodes==0)
            exit(1);//or abort in some other way
        //the following is just standard dynamic memory management
        LinkedListNode<T> *tmpNodes=new LinkedListNode<T>[numNodes-1];
        for (size_t i=0; i<numNodes-1; ++i)
            tmpNodes[i]=nodes[i];
        delete[]nodes;
        tmpNodes[numNodes-1].setNext(NULL);
        nodes=tmpNodes;
        numNodes--;
        return *this;
    }
};

Basically the pointers store the access to the next and previous elements in the array. The second struct manages the nodes, setting the pointers, dynamic memory allocation, etc. You should of course add more functionality to the second struct (or in this case class) by making more constructors and operators. Hope this helps.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.