Overall
You don't use encapsulation. Which makes your list vulnerable to incorrect initialization and accidental incorrect modification from outside the list.
You use several C based style choice rather than C++ style which make your codde harder to read.
Code Review
Only a list of int
?
class Node {
public:
int value; // int only
Node* next = NULL;
};
Passing a pointer to a pointer. You can simplify this by passing a reference.
void push(struct Node** head_ref, int new_data)
In C++ you don't need to use struct keyword when using struct types.
void push(struct Node** head_ref, int new_data)
A better declaration would have been:
void push(Node*& head_ref, int new_data)
C++ you should always use new (rather than the malloc family).
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
There are two reasons for this:
If your code combines both C and C++ memory allocation you need to track which is which and use the correct de-allocation method. Thus it is best to simply use one allocation method then you always know how to deallocate it.
Using new
calls the constructor to initialize the object.
Remember this line from your class declaration.
Node* next = NULL;
This is not going to happen if you call malloc()
you must use new
to get that to happen.
Its also simpler to write:
Node* new_node = new Node{new_data, *head_ref};
Your find returns the nth
index of the list. But your index is 1 based. Most C based languages use a zero based index. But if I pass 0
to find()
this function will recurse for ever.
In recursive funtions always check for the end of the recursion first. So as the first check in find
you should check that the list pointer is not nullptr
.
This is not modified.
int count = 1;
So this should be a constexpt
. The whole point of using a named type is to make the code more expressive. A better name would help the code be more expressive.
Don't leave redundant code commented out. Delete it.
//if count equal too n return node->data
Source control system allow you to keep older versions of the code around
It is now easy to install git on all machines learn to use it.
Use better indentation
if(count == n)
return head->value;
In C++ we use nullptr
rather than NULL
.
struct Node* head = NULL;
The difference is that nullptr
is correctly typed as a pointer, while NULL is a macro (bad) for an integer (bad type). Thus you can not incorrectly use nullptr
while NULL
can be abused.
In C++ we use the C++ streams std::cout
.
printf("Element at index 3 is %d", find(head, 3));
The C++ streams have a more advanced type checking system that prevents accidents.
std::cout << "Element at index 3 is " << find(head, 3);
Beter implementation
template<typename T>
class LinkedList
{
struct Node {
T value;
Node* next;
};
Node* root;
public:
LinkedList()
: root(nullptr)
{}
~LinkedList() {
while(root) {
Node* next = root->next;
delete root;
root = next;
}
}
LinkedList(LinkedList const&) = delete;
LinkedList& operator=(LinkedList const&) = delete;
void push(T const& new_data)
{
root= new Node{new_data, root};
}
int find(int n)
{
Node* result = findElement(root, n);
if (result == nullptr) {
throw std::runtime_error("message");
}
return result->value;
}
private:
Node* findElement(Node* n, int n) {
if (n == nullptr) {
return nullptr;
}
if (n == 0) {
return n;
}
return findElement(n->next, n-1);
}
}
Main.cpp
int main()
{
LinkedList<int> list;
list.push(1);
list.push(4);
list.push(1);
list.push(12);
list.push(1);
std::cout << "Element at index 3 is " << find(head, 2) << "\n";
getchar();
}