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;
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.
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.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.