Starting at the top
//any suggestions
Yes, plenty. But don't add that to the code.
using namespace std;
Nearly every beginner includes this (and it's understandable because this is what they do in books).
In actual practice this is a bad idea. Never include this line in real code. The reason books include it is to save space (because each printed page costs extra). When writing real code, this will create bad habits that will bite you in the end so it is a habit you should break now.
see: Why is “using namespace std;” considered bad practice?
node class
protection level
There is no need to make the node class public. This is internal to your linked list so you should hide its implementation from other people by making it a private member class of the linked class.
style
class node
{
friend class linked;
private:
int data;
public:
node *link;
node()
{
data=0;
link=NULL;
}
};
Small note on vertical spacing: there is way too much here. It's a small class so it does not stand out. But if you do the same thing on a bigger class it becomes hard to read. Now don't take this to the extreme and completely eliminate vertical space-- break things up into logical units.
Since we are making this class a private member of linked there's no need for friendship; just make everything public.
But we can improve the code by having a constructor that takes the data value and the link (if you look at your code you could use both at the same time. When writing constructors, it's preferred to use the initializer list syntax to initialize members:
node(int data, node* link)
: data(data)
, link(link)
{}
You will notice here that everything is lower case. It is relatively common to define user-defined types with an initial capital letter, while objects have an initial lower case letter. This allows you to quickly see the difference between types and objects (an important distinction in C++).
So, following this style, your code should look like this:
class Linked
{
struct Node
{
int data;
node* next;
Node(int data, Node* next)
: data(data)
, next(next)
{}
};
....
linked class
class linked
{
public:
node *start=NULL;
node *ptr;
node *temp=NULL;
void append(int item);
void traverse();
};
Not sure what all the pointers are for? OK start marks the start of the list (usually called head). But what are the others supposed to represent? If they are really just things you use a throw away then they can be local to the function methods and not part of the class.
You call new in your code. For every call to new there must be a corresponding call to delete. Otherwise you will leak memory (and resources). So the best place to do this is in the destructor.
Also you are missing a constructor. This means that all you member variables are likely to be undefined (this means they have random values in them. C++ (unlike Java and other languages at this level) does not do automatic initialization of variables.
see: Why aren't pointers initialized with NULL by default?
So lets add the constructor and destructor
class Linked
{
struct Node
{
int data;
node* next;
Node(int data, Node* next)
: data(data)
, next(next)
{}
};
Node* head;
Linked():
head(nullptr)
{}
~Linked()
{
Node* tmp;
for(;head;head = tmp)
{
tmp = head->next;
delete head;
}
}
...
If we look at append. You get the correct test for adding an element to an empty list. But it starts to go wrong in the second half where you are using a loop.
The member temp is not initialized. It is also public -- this means it could have been altered since last time you used it. So it is best to use a local variable that you initialize to head.
Note: you can also use the new constructor for node to reduce code in this function.
void Linked::append(int item)
{
if (head == nullptr)
{
head = new Node(item, nullptr);
}
else
{
// First find a pointer to the last item in the chain.
Node* last = head;
while(last->next)
{
last = last->next;
}
// Now just add the node.
last->next = new Node(item, nullptr);
// Notice this loop happens each time you add an element.
// This makes adding an element relatively expensive.
// To avoid this a lot of implementation keep two pointers
// in the list a `head` and a `tail`. That way data elements
// can be quickly added to the tail.
// When you start adding things like delete.
// It becomes useful to know your previous element.
// So it is also very common for the node object to have
// two pointers `next` and `prev`
}
Note: we always seem to place nullptr as the second argument. So we could potentially remove it. But if you try to implement an insert function then it becomes useful:
void Linked::insert_at_head(int value)
{
head = new Node(item, head); // See very useful.
}
Not sure what your traverse is doing.
void linked::traverse()
{
node *trav=start;
while(trav!=NULL)
{
cout<<trav->data<<endl;
trav=trav->link;
}
}
I would just name that print; traverse implies going through a tree.
One way to improve the functionality and modularity of traverse would be for it to take a parameter of a function that should be applied to all the nodes (but I think that is a bit beyond this exercise). So a couple of things here:
- Rename to
print
- Mark the function as
const
It does not alter the state of the object. So it is safe to call on a const version of the object.
- Printing in C++ is usally done by
operator<<
so create one of these that calls your print method.
Like this:
void Linked::print(std::ostream& str = std::cout) const // Note const
{
node *trav=start;
while(trav!=NULL)
{
// Added space here so yo can see the <<
// and what they are applied too.
//
// Also prefer "\n" to std::endl (especially in here)
// The std::endl forces a buffer flush. Doing this
// after printing every integer becomes very inefficient.
str << trav->data << "\n";
trav=trav->link;
}
}
std::ostream& operator<<(std::ostream& str, Linked const& data)
{
data.print(str);
return str;
}
I think we have now covered enough in one review. I would have another bash at this example. Once you have done that post the code for review again and we can go into some other details.
