I have been trying to teach myself C++ recently and would like to have some general feedback and comments on how to improve my code so far. Furthermore, since I am more experienced with other (garbage-collected) languages like Python and Java, I would like to know if I am handling memory correctly or making any fundamental rookie mistakes.
I have attempted to make an implementation of a linked list, given below in LinkedList.h.
#pragma once
#include <stdexcept>
#include <ostream>
/*
This is a generic-type linked list implemented without using the C++ STL.
Member functions:
void append(const T&)
bool contains(const T&) const
const T& get(int) const
void insert(int, const T&)
int length() const
void prepend(const T&)
T remove(int)
bool removeValue(const T&)
*/
template <typename T>
class LinkedList {
public:
// Appends element to the end of the list
void append(const T& data) {
insert(len, data);
}
// Returns data element at given index
// Throws std::out_of_range if index is invalid
const T& get(int index) const {
if (index < 0 || index >= len)
throw std::out_of_range("Invalid index in LinkedList::get(int)");
Node *ptr = Head;
// Traverse up to the matching node
for (; index-- ;)
ptr = ptr -> next;
return ptr -> data;
}
// Prepends element to the start of the list
void prepend(const T& data) {
insert(0, data);
}
// Removes element at a given index, if possible, and returns it
// Throws std::out_of_range if index is invalid
T remove(int index) {
if (index < 0 || index >= len)
throw std::out_of_range("Invalid index in LinkedList::remove(int)");
Node *old;
if (index == 0) { // Deleting the head
old = Head; // Save the removed node to free later
Head = Head -> next; // Skip over the node
}
else {
Node *ptr = Head;
for (; --index ;) // Traverse up to just before the matching node
ptr = ptr -> next;
old = ptr -> next; // Save the removed node to free later
ptr -> next = old -> next; // Skip over the node
}
T ret = old -> data; // Save the removed data to return later
delete old; // Delete the node from memory
len--;
return ret;
}
// Removes element by value, if found, and return whether or not it was successful
bool removeValue(const T& data) {
Node *ptr = Head;
if (!ptr) // Empty list
return false;
Node *old;
if (ptr -> data == data) { // Deleting the head
old = Head; // Save the removed node to free later
Head = old -> next; // Skip over the node
}
else {
// Advance until the end of the list, or just before the object is found
while (ptr -> next && ptr -> next -> data != data)
ptr = ptr -> next;
if (!ptr -> next) // End of the list
return false;
// Object was found
Node *old = ptr -> next; // Save the removed node to free later
ptr -> next = old -> next; // Skip over the node
}
delete old; // Delete the node from memory
len--;
return true;
}
// Inserts element at a given index
// Throws std::out_of_range if index is invalid
void insert(int index, const T& data) {
if (index < 0 || index > len)
throw std::out_of_range("Invalid index in LinkedList::insert(int, const T&)");
if (index == 0)
Head = new Node(data, Head);
else {
Node *ptr = Head;
// Traverse up to one node prior to the insertion
for (; --index ;)
ptr = ptr -> next;
ptr -> next = new Node(data, ptr -> next);
}
len++;
}
// Returns whether or not the list contains a given element
bool contains(const T& data) const {
Node *ptr = Head;
while (ptr != nullptr) {
if (ptr -> data == data)
return true;
ptr = ptr -> next;
}
return false;
}
// Returns the length of the list
int length() const {
return len;
}
// Deletes all Nodes in the list
~LinkedList() {
Node *ptr = Head, *next;
// Iterate through the list
while (ptr) {
next = ptr -> next;
delete ptr;
ptr = next;
}
}
private:
class Node { public:
const T data;
Node *next;
Node(const T& data, Node* next = nullptr) : data(data), next(next) { }
};
int len = 0;
Node *Head = nullptr;
template <typename S>
friend std::ostream& operator<<(std::ostream&, const LinkedList<S>&);
};
template <typename S>
std::ostream& operator<<(std::ostream& os, const LinkedList<S>& ls) {
os << "[ ";
typename LinkedList<S>::Node *ptr = ls.Head, *next;
// Iterate through the list
while (ptr) {
os << ptr -> data;
next = ptr -> next;
if (next) // If not at the end of the list
os << ", ";
ptr = next;
}
os << " ]";
return os;
}
Additionally, I have written some code for testing most of the features, which I called LinkedList.cpp.
#include <iostream>
#include <iterator>
#include "LinkedList.h"
// Note that this file uses features from the C++17 standard, namely std::size.
int main() {
LinkedList<int> *L = new LinkedList<int>;
// This can be done without pointers, too:
// LinkedList<int> L2;
// Test append head
int x = 3;
L -> append(x);
// L2.append(x);
std::cout << "Expected: 3 \tActual: " << L -> get(0) << std::endl << std::endl;
// std::cout << "Expected: 3\tActual: " << *(L2.get(0)) << std::endl << std::endl;
// Test repeated append
int arr[] = {45, 10, 32, 12, 11, 12, 1, -1, 0, 56};
for (unsigned int i = 0; i < std::size(arr); i++)
L -> append(arr[i]);
for (unsigned int i = 0; i < std::size(arr); i++)
std::cout << "Expected: " << arr[i] << " \tActual: " << L -> get(i + 1) << std::endl;
std::cout << std::endl;
// Test remove and length
x = L -> remove(3);
std:: cout << "Expected: 32\tActual: " << x << std::endl;
int newArr[] = {3, 45, 10, 12, 11, 12, 1, -1, 0, 56};
for (int i = 0; i < L -> length(); i++)
std::cout << "Expected: " << newArr[i] << " \tActual: " << L -> get(i) << std::endl;
std::cout << std::endl;
// Test insert and prepend
L -> prepend(arr[0]);
L -> insert(1, arr[1]);
for (int i = 0; i < 2; i++)
std::cout << "Expected: " << arr[i] << " \tActual: " << L -> get(i) << std::endl;
// Test contains
std::cout << "Expected: 1 \tActual: " << L -> contains(arr[1]) << std::endl;
std::cout << "Expected: 0 \tActual: " << L -> contains(arr[2]) << std::endl;
std::cout << "Expected: 1 \tActual: " << L -> contains(arr[3]) << std::endl;
std::cout << std::endl;
// Test output operator
std::cout << "Actual: \t[ 45, 10, 3, 45, 10, 12, 11, 12, 1, -1, 0, 56 ]" << std::endl;
std::cout << "Expected:\t" << *L << std::endl;
std::cout << std::endl;
// Test removeValue
std::cout << "Expected: 1\tActual: " << L -> removeValue(0) << std::endl;
std::cout << "Expected: 0\tActual: " << L -> removeValue(9000) << std::endl;
std::cout << "Expected: 1\tActual: " << L -> removeValue(45) << std::endl;
std::cout << "Expected: 1\tActual: " << L -> removeValue(45) << std::endl;
std::cout << "Expected: 1\tActual: " << L -> removeValue(3) << std::endl;
std::cout << "Expected: 0\tActual: " << L -> removeValue(3) << std::endl;
std::cout << "Expected: 1\tActual: " << L -> removeValue(56) << std::endl;
std::cout << "Actual: \t[ 10, 10, 12, 11, 12, 1, -1 ]" << std::endl;
std::cout << "Expected:\t" << *L << std::endl;
std::cout << std::endl;
delete L;
return 0;
}
Thank you very much! I appreciate any advice or comments.
dataconstinNode? That places some unnecessary restrictions on how your class can be used. \$\endgroup\$dataaconstmember variable because it allows me to put objects of typeconst T&into the list, which should catch both lvalue and rvalue expressions in one go (without overloading). Also, the list theoretically should never need to modify one of theNodes it contains, when you can insteadremoveit andinserta new value in its place. (If any of the terminology I use is incorrect, please let me know for future reference.) \$\endgroup\$std::listand trying to be compatible with that. For instance, there's no reason to writeint length() constinstead ofstd::size_t size() const. \$\endgroup\$LinkedList<int> *L = new LinkedList<int>;A basic rule is that if you callnewyou are probably doing something wrong. C++ has other techniques that make its memory management automatic. We have what is called fine grained deterministic garbage collection built into the language (smart pointers and containers). You can of course do it manually with new but there is very little need to do this apart from in very specialized cases. \$\endgroup\$LinkedList<int> L;\$\endgroup\$