I am currently working on implementing some data structures as a way to learn C++. I'm coming mostly from a Java background so I was hoping to get some feedback regarding this implementation of a singly linked list in C++ using templates. This singly linked list will only support insertions at the head and tail positions and deletions from the head position. The plan is to use this as a base to build further data structures. I would like to create a rather complete library of data structures, so I was hoping to make them as extensible and reusable as possible.
Below follows the class definition.
#ifndef LINKEDLISTS_SINGLYLINKEDLIST_H_
#define LINKEDLISTS_SINGLYLINKEDLIST_H_
#include <cstddef>
#include <iostream>
template <typename E>
class SinglyLinkedList {
private:
/** BEGIN NESTED NODE CLASS **/
class Node {
private:
E data; //Should this be a reference?
Node* next;
public:
Node(Node* n, const E& d) : data(d), next(n) {};
Node* getNext() const { return next; }
E& getData() { return data; }
void setNext(Node* n) { next = n; }
}; /** END NESTED NODE CLASS **/
/** Begin fields of SinglyLinkedList class **/
Node* head;
Node* tail;
int listSize;
/** End fields of SinglyLinkedList class **/
public:
SinglyLinkedList();
~SinglyLinkedList();
//Accessor methods
bool isEmpty() const;
int size() const;
const E& first() const;
const E& last() const;
//Update methods
void addFirst(const E&);
void addLast(const E&);
E* removeFirst();
void print() const;
}; /** END SINGLYLINKEDLIST CLASS HEADER **/
#include "SinglyLinkedList.tpp" //Include implementations of template code.
#endif /* LINKEDLISTS_SINGLYLINKEDLIST_H_ */
The implementations of the functions follow below:
/*
* SinglyLinkedList.tpp
*
* Created on: Jan 5, 2020
* Author: dii
*/
/** Constructor **/
template<typename E>SinglyLinkedList<E>::SinglyLinkedList() : head(nullptr), tail(nullptr), listSize(0) {}
/** Destructor **/
template<typename E>SinglyLinkedList<E>::~SinglyLinkedList() {
while(!isEmpty()) {
delete removeFirst();
}
}
/** Begin functions **/
template<typename E> bool SinglyLinkedList<E>::isEmpty() const { return listSize == 0; }
template<typename E> int SinglyLinkedList<E>::size() const { return listSize; }
template<typename E> const E& SinglyLinkedList<E>::first() const { return head->getData(); }
template<typename E> const E& SinglyLinkedList<E>::last() const { return tail->getData(); }
template<typename E> void SinglyLinkedList<E>::addFirst(const E& d) {
Node* temp = new Node(head->getNext(), d); //Create a new node.
head = temp; // Set the head pointer to point to this object.
listSize++; // Increase size of list by 1.
}
template<typename E> void SinglyLinkedList<E>::addLast(const E& d) {
Node* temp = new Node(nullptr, d);
if(isEmpty()) {
head = temp;
tail = temp;
} else {
tail->setNext(temp);
tail = temp;
}
listSize++;
}
template<typename E> E* SinglyLinkedList<E>::removeFirst() {
if(isEmpty()) {
return nullptr;
}
E* temp = &(head->getData());
head = head->getNext();
listSize--;
return temp;
}
template<typename E> void SinglyLinkedList<E>::print() const {
Node* walk = head;
while(walk != nullptr) {
std::cout << walk->getData() << std::endl;
walk = walk->getNext();
}
}
I have a feeling that the destructor is not implemented as well as it could be. I am also still not entirely sure about when to use references, e.g., should the data
field of the Node
class be of type E&
or is just E
ok?