robt's Linked List

Question

I have implemented a linked list in C++. I would love to get feedback on how I can improve my code. Should I include more comments to my code or does my code have sufficient logical flow? I would also appreciate comments on how I could make my code more concise. I have tried to make sure to stop all memory leaks. Please let me know if there are more that I have not addressed.

#include <cstdlib>
#include <iostream>
#include <cstdio>
//Node class 
template <class T> 
class Node{
 public:
 T data; 
 Node<T> *next;
 Node(T data, Node<T> *next); 
};
template <class T>
Node<T>::Node(T data, Node<T> *next){
 this->next = next;
 this->data = data;
}
//LinkedList class
template <class T> 
class LinkedList{ 
 public:
 //fields
 Node<T> *head;
 int size;
 //methods
 LinkedList();
 void push(T data);
 void append(T data);
 T pop();
 T removeLast();
 void clear();
 int getSize(); 
 void printList();
};
/* LinkedList Constructor
 Sets head of the linkedlist to null,
 Sets size to 0 */
template <class T>
LinkedList<T>::LinkedList(){
 this->head = NULL;
 this->size = 0;
}
//getSize:returns the size of the list.
template <class T>
int LinkedList<T>::getSize(){
 return this->size;
}
/* push: adds a node to the front of the list, 
 stores the given data in the node,
 increments size of list */
template <class T>
void LinkedList<T>::push(T data){
 Node<T> *n = new Node<T>(data, this->head);
 this->head = n;
 this->size++; 
}
/* append: adds a node to the end of the list, 
 stores the given data in the node,
 increments size of list */
template<class T>
void LinkedList<T>::append(T data){
 Node<T> *n = new Node<T>(data, NULL);
 Node<T> *start = this->head; 
 if (start == NULL){ 
 this->head=n; 
 this->size ++; 
 return; 
 }
 while (start->next != NULL){
 start = start->next; 
 }
 start->next = n; 
 this->size ++; 
}
/* pop: removes the node at the front of the list,
 returns the associated data. */
template <class T>
T LinkedList<T>::pop(){
 Node<T> *h = this->head;
 //if list is empty
 if (h==NULL){
 return 0;
 }
 //if list has only one node
 if (h->next==NULL){ 
 T ret = h->data; 
 this->head = NULL;
 this->size --; 
 return ret; 
 }
 //if list has multiple nodes
 else{
 T ret = this->head->data;
 this -> head = h->next;
 this->size --;
 return ret;
 }
 delete h;
}
/*removes the last node in the list 
 returns the associated data.*/
template <class T>
T LinkedList<T>::removeLast(){
 Node<T> *h = this->head;
 //if list is empty
 if (h==NULL){
 return 0;
 }
 //if list has only one node
 if (h->next==NULL){ 
 return this->pop();
 }
 //if list has multiple nodes
 while (h->next->next != NULL){
 h = h->next; 
 }
 T ret = h->next->data; 
 h->next = NULL;
 this->size--;
 delete h->next;
 return ret; 
}
/*removes all of the nodes from the list, 
freeing the associated data using the given function */
template <class T>
void LinkedList<T>::clear(){
 //if list is empty
 if (this->size == 0){
 std::cout<<"Cannot Clear Empty List"<<std::endl;
 return;
 }
 Node<T> *h = this->head;
 Node<T> *n = NULL;
 while (h != NULL) {
 n = h->next;
 delete h;
 h=n;
 }
 this->head = NULL;
 this->size = 0;
 std::cout<<"Cleared List"<<std::endl;
}
template <class T>
void LinkedList<T>::printList(){
 int i = 1;
 //if list is empty
 if (this->size == 0){
 std::cout<<"Cannot Print Empty List"<<std::endl;
 return;
 }
 Node<T> *n = this->head;
 //if there is only one element
 if (this->size ==1){
 std::cout<<i<<": "<<n->data<<std::endl;
 }
 while(n){
 std::cout<<i<<": "<<n->data<<std::endl;
 n = n->next;
 i++;
 }
 delete n;
}
int main(){ 
 LinkedList<int> list;
 //testing push
 for (int i = 1; i < 6; ++i)
 list.push(i);
 std::cout<<"After Pushing"<<std::endl;
 list.printList(); //testing printList()
 std::cout<<"\nSize of list: "<<list.getSize()<<std::endl;//testing getSize()
 //testing pop
 for (int j = 0; j < 5; ++j){
 int output=list.pop();
 std::cout<<"Popped: "<<output<<std::endl;
 }
 std::cout<<"\nAfter Popping"<<std::endl;
 std::cout<<"Size of list: "<<list.getSize()<<std::endl;
 list.printList();
 //testing Append
 list.append(0);
 list.append(20);
 std::cout<<"\nAfter Append"<<std::endl;
 std::cout<<"Size of list: "<<list.getSize()<<std::endl; //testing getSize() again
 list.printList(); //testing printList() after append
 //testing RemoveLast
 list.removeLast();
 std::cout<<"\nAfter RemoveLast"<<std::endl;
 list.printList();
 std::cout<<std::endl;
 //testing clear
 list.clear(); //output: cleared
 list.clear(); //output: cannot clear empty list
 std::cout<<"\nAfter Clear"<<std::endl;
 list.printList();
 return 0;
}

• hoffmale: The code is broken. Node<T> *n in push doesn't allocate a new node, it points somewhere undefined. return 0 in pop doesn't work if T isn't an arithmetic type (it could be a struct or a class).
• Toby Speight: Have you actually tested this? It has serious warnings, and crashes when I attempt to run. That indicates that this code isn't quite ready for review. Please fix the problems, then you'll be very welcome to post it here!
• Loki Astari: ps. Don't use malloc() and free() in C++ code.
• Loki Astari: What is the difference between new/delete and malloc/free?
• robt: Hey! I have made changes to my code. It is free of bugs. I apologise for the previous post. I would appreciate your feedback.

Answer 1

Here are some things that may help you improve your code.

Don't write this->

Within member functions this->data is redundant. It add visual clutter and does not usually aid in understanding. So for example, we have the existing Node constructor:

template <class T>
Node<T>::Node(T data, Node<T> *next){
 this->next = next;
 this->data = data;
}

I'd write that in a more modern style like this:

template <class T>
Node<T>::Node(T data, Node<T> *next) :
 data{data},
 next{next}
{ }

Prefer private to public where practical

The LinkedList class has its only data members head and size as public members. Rather than do it that way, it would be better to keep it private. Generally, it's best to keep the internals of a class private to reduce linkage among objects to only what they need. This simplifies the interface and therefore the maintenance. In a similar vein, the data members of Node could be private and the LinkedList class could be declared a friend to keep access but only within that class. Better still, put the Node definition inside the LinkedList class -- it's the only context in which a Node is used or needed.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Use only required #includes

The code has #includes that are not needed. This clutters the code and makes it more difficult to read and understand. Only include files that are actually needed. In this code, these two are not needed:

#include <cstdlib>
#include <cstdio>

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Use whitespace to improve readability

Lines like this:

std::cout<<i<<": "<<n->data<<std::endl;

become much easier to read with a little bit of whitespace:

std::cout << i << ": " << n->data << '\n';

Note, too, that as per the advice above, it's now using '\n' instead of std::endl.

Simplify the code

The current list printing routine looks like this (after removing all the redundant this-> stuff):

template <class T>
void LinkedList<T>::printList(){
 int i = 1;
 //if list is empty
 if (size == 0){
 std::cout<<"Cannot Print Empty List"<<std::endl;
 return;
 }
 Node<T> *n = head;
 //if there is only one element
 if (size ==1){
 std::cout<<i<<": "<<n->data<<std::endl;
 }
 while(n){
 std::cout<<i<<": "<<n->data<<std::endl;
 n = n->next;
 i++;
 }
 delete n;
}

There are two problems with this. First, delete n; at the end is an error. n is a pointer and was not created using new and so must not be deleted using delete. Second, it's more complex than it needs to be. An alternative:

template <class T>
void LinkedList<T>::printList(){
 if (size == 0){
 std::cout << "Cannot Print Empty List\n";
 return;
 }
 Node<T> *n = head;
 for (int i=1; i <= size; ++i) {
 std::cout << i << ": " << n->data << '\n';
 n = n->next;
 }
}

Separate data manipulation from output

The clear function really does two things. It removes all the nodes from the list and then it prints the result of the operation. Better would be to separate the two; have the clear function only clear the nodes and return a bool to indicate true if at least one node was cleared or false to indicate that the list was initially empty.

Use const where practical

The current printList() routine does not (and should not) modify the underlying object, and so it should be declared const:

void printList() const;

The same is true of getSize().

Consider keeping a tail pointer

This list provides operations on both the head and the tail, but traverses the entire list every time a tail-oriented operation is done. Simpler would be to keep a tail pointer as a private member and avoid traversing the list when it's not needed.

Fix the bugs

The pop() routine does not delete the node it removes. That's a bug that should be fixed because right now it leaks memory. A more subtle bug is what happens with an empty list:

if (h==nullptr){
 return 0;
}

This assumes that type T may be constructed from 0 which isn't necessarily true. Better would be return T{}; which only requires that T must be default-constructable. A rewritten, bug free and simplified version is this:

template <class T>
T LinkedList<T>::pop(){
 if (head == nullptr){
 return T{};
 }
 T ret{head->data};
 Node<T> *doomed{head};
 head = doomed->next;
 delete doomed;
 --size;
 return ret;
}

There's a similar problem (and fix) in removeLast().

Think of the user

Instead of always printing to std::cout, consider instead passing a std::ostream& as a parameter to printList. This would allow the user to redirect the output to any stream.

Provide a destructor

The LinkedList object should clean itself up if it goes out of scope and the way to do that is to provide a destructor. Once you fix clear, you could use it as the basis for the destructor:

~LinkedList() { clear(); }