Regarding C++, I have an experience in writing only short non-object-oriented programs and competitive programming challenges.
I would like to get your feedback about my C++ style, design decisions, and overall quality.
The below is the implementation of a Singly Linked List containing a multiset of values of type T. Type T is required to provide equal to operator. The class supports the following operations:
- push a new value to the front of the list
- push a new value to the end of the list
- remove the first encountered occurrence of a given value
- check if the list contains a given value
- get the number of elements in the list
- print the list in a pretty format
- swap two lists
For the design, I decided to use both head and tail pointers to make both inserts constant time operations. For now, all pointers are raw pointers. The Node class is the internal class of LinkedList and an instance of LinkedList is responsible to delete its nodes. I decided to do that because this allows freeing the memory iteratively instead of recursively, which could cause problems if stack size is limited.
/* Singly Linked List by @pkacprzak */
#ifndef LINKED_LIST_HH__
#define LINKED_LIST_HH__
#include <ostream>
template<typename T>
class LinkedList {
public:
LinkedList() {}
LinkedList(const LinkedList& x) {
auto cur = x.head;
while (cur != nullptr) {
pushBack(cur->val);
cur = cur->next;
}
}
LinkedList& operator=(const LinkedList& rhs) {
LinkedList tmp(rhs);
swap(*this, tmp);
return *this;
}
~LinkedList() {
auto cur = head;
while (cur != nullptr) {
auto tmp = cur;
cur = cur->next;
delete tmp;
tmp = nullptr;
}
}
void pushFront(T val) {
auto node = new Node(val);
node->next = head;
if (head == nullptr) {
tail = node;
}
head = node;
++sz;
}
void pushBack(T val) {
auto node = new Node(val);
if (head == nullptr) {
head = node;
} else {
tail->next = node;
}
tail = node;
++sz;
}
bool contains(T val) const {
auto cur = head;
while (cur != nullptr) {
if (cur->val == val) {
return true;
}
cur = cur->next;
}
return false;
}
void removeValue(T val) {
if (head == nullptr) return;
if (head->val == val) {
auto cur = head;
head = head->next;
delete cur;
if (head == nullptr) {
tail = nullptr;
}
--sz;
} else {
auto cur = head->next;
auto prev = head;
while (cur != nullptr) {
if (cur->val == val) {
prev->next = cur->next;
if (cur == tail) {
tail = prev;
}
delete cur;
--sz;
return;
}
prev = cur;
cur = cur->next;
}
}
}
int size() const {
return sz;
}
friend std::ostream& operator<<(std::ostream& os, const LinkedList& x) {
auto cur = x.head;
os << "[";
while (cur != nullptr) {
os << cur->val;
if (cur != x.tail) {
os << ",";
}
cur = cur->next;
}
os << "]";
return os;
}
friend void swap(LinkedList& a, LinkedList& b) {
std::swap(a.head, b.head);
std::swap(a.tail, b.tail);
}
private:
struct Node {
Node(T val_) : val(val_) {}
T val;
Node* next = nullptr;
};
Node* head = nullptr;
Node* tail = nullptr;
int sz = 0;
};
#endif
LINKED_LIST_HH__stackoverflow.com/a/228797/14065 \$\endgroup\$