This code seems to work correctly. I would appreciate any comments on how to improve the code, e.g. readability, algorithms, const-correctness, memory, anything else I am forgetting?
Also, for the function swap_values
, would it make more sense to swap two nodes instead of just values of the nodes and why?
SinglyLinkedList.hpp
#pragma once
#include <iostream>
class SinglyLinkedList {
private:
struct ListNode {
int value;
std::shared_ptr<ListNode> next;
ListNode(int val) : value(val), next(nullptr) {}
};
std::shared_ptr<ListNode> head;
std::shared_ptr<ListNode> tail;
std::shared_ptr<ListNode> find (int val) const;
public:
SinglyLinkedList();
void print_list () const;
void push_back (int val);
void pop_back ();
void push_front (int val);
void pop_front ();
size_t get_size () const;
bool search (int val) const;
void swap_values (int val1, int val2);
void remove_nodes (int val);
void reverse ();
~SinglyLinkedList();
};
SinglyLinkedList.cpp
#include "SinglyLinkedList.hpp"
SinglyLinkedList::SinglyLinkedList () : head (nullptr), tail (nullptr) {
}
void SinglyLinkedList::print_list () const {
// O(n)
if (head) {
std::shared_ptr<ListNode> tempNode = head;
while (tempNode) {
std::cout << tempNode->value << " ";
tempNode = tempNode->next;
}
std::cout << "\n";
} else {
std::cout << "List is empty.\n";
}
}
void SinglyLinkedList::push_back(int val) {
// O(n)
std::shared_ptr<ListNode> currNode = std::make_shared<ListNode>(val);
if (head) {
std::shared_ptr<ListNode> tempNode = head;
while (tempNode != tail) {
tempNode = tempNode->next;
}
tempNode->next = currNode;
tail = currNode;
} else {
head = currNode;
tail = currNode;
}
}
void SinglyLinkedList::pop_back () {
// O(n)
if (!head) {
std::cout << "List is empty.\n";
return;
}
if (head == tail) {
head = nullptr;
tail = nullptr;
return;
}
std::shared_ptr<ListNode> currNode = head;
while (currNode->next != tail) {
currNode = currNode->next;
}
tail = currNode;
currNode->next = nullptr;
}
void SinglyLinkedList::push_front (int val) {
// O(1)
std::shared_ptr<ListNode> currNode = std::make_shared<ListNode>(val);
currNode->next = head;
head = currNode;
}
void SinglyLinkedList::pop_front () {
// O(1)
if (!head) {
std::cout << "List is empty.\n";
return;
}
std::shared_ptr<ListNode> currNode = head;
head = head->next;
currNode->next = nullptr;
}
size_t SinglyLinkedList::get_size () const {
// O(n)
size_t listSize = 0;
std::shared_ptr<ListNode> currNode = head;
while (currNode) {
++listSize;
currNode = currNode->next;
}
return listSize;
}
bool SinglyLinkedList::search (int val) const {
// O(n)
if (!head) {
std::cout << "List is empty.\n";
return false;
}
std::shared_ptr<ListNode> currNode = head;
while (currNode) {
if (currNode->value == val) {
//std::cout << "Value " << val << " is in the list\n";
return true;
}
currNode = currNode->next;
}
//std::cout << "Value " << val << " is not in the list.\n";
return false;
}
std::shared_ptr<SinglyLinkedList::ListNode> SinglyLinkedList::find (int val) const {
// O(n)
if (!head) {
return nullptr;
}
std::shared_ptr<ListNode> currNode = head;
while (currNode) {
if (currNode->value == val) {
return currNode;
}
currNode = currNode->next;
}
return nullptr;
}
void SinglyLinkedList::swap_values (int val1, int val2) {
// swap is O(1), find is O(n)
// Should I be swapping nodes instead of values?
std::shared_ptr<ListNode> val1Node = find (val1);
std::shared_ptr<ListNode> val2Node = find (val2);
if (!val1Node) {
std::cout << "Value " << val1 << " is not in the list.\n";
return;
}
if (!val2Node) {
std::cout << "Value " << val2 << " is not in the list.\n";
return;
}
int tempNodeVal = val1Node->value;
val1Node->value = val2Node->value;
val2Node->value = tempNodeVal;
}
void SinglyLinkedList::remove_nodes (int val) {
if (!head) {
std::cout << "List is empty.\n";
return;
}
std::shared_ptr<ListNode> prevNode = nullptr;
std::shared_ptr<ListNode> currNode = head;
while (currNode) {
if (currNode->value == val) {
// val found - remove
if (!prevNode) {
// delete head node
if (head == tail) {
head = nullptr;
tail = nullptr;
return;
}
head = head->next;
prevNode = currNode;
currNode = currNode->next;
prevNode->next = nullptr;
prevNode = nullptr;
} else if (currNode == tail) {
// delete tail node
tail = prevNode;
prevNode->next = nullptr;
currNode->next = nullptr;
} else {
prevNode->next = currNode->next;
currNode->next = nullptr;
currNode = prevNode->next;
}
} else {
// val not found
prevNode = currNode;
currNode = currNode->next;
}
}
}
void SinglyLinkedList::reverse () {
// O(n)
if (!head || head == tail) {
return;
}
std::shared_ptr<ListNode> currNode = head;
std::shared_ptr<ListNode> prevNode = nullptr;
std::shared_ptr<ListNode> nextNode = nullptr;
head = nullptr;
tail = head;
while (currNode) {
nextNode = currNode->next;
currNode->next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
head = prevNode;
}
SinglyLinkedList::~SinglyLinkedList () {
}
main.cpp
#include "SinglyLinkedList.hpp"
int main() {
// List init
SinglyLinkedList myList;
std::cout << "Print list: \n";
myList.print_list();
std::cout << "List size: " << myList.get_size() << "\n";
// Add nodes to the back of the list
myList.push_back(2);
myList.push_back(4);
myList.push_back(3);
myList.push_back(1);
std::cout << "Print list: \n";
myList.print_list();
std::cout << "List size: " << myList.get_size() << "\n";
// Add nodes to the front of the list
myList.push_front(5);
myList.push_front(7);
myList.push_front(6);
std::cout << "Print list: \n";
myList.print_list();
std::cout << "List size: " << myList.get_size() << "\n";
// Pop nodes from the front of the list
myList.pop_front();
myList.pop_front();
std::cout << "Print list: \n";
myList.print_list();
std::cout << "List size: " << myList.get_size() << "\n";
// Pop nodes from the back of the list
myList.pop_back();
myList.pop_back();
std::cout << "Print list: \n";
myList.print_list();
std::cout << "List size: " << myList.get_size() << "\n";
// Check if node with specific velue is in the list
int valToSearch = 3;
bool foundVal = myList.search(valToSearch);
if (foundVal) {
std::cout << valToSearch << " is in the list.\n";
} else {
std::cout << valToSearch << " is not in the list.\n";
}
// Swap the values of two nodes
myList.push_back(7);
myList.push_back(8);
myList.push_back(9);
myList.print_list();
myList.swap_values(9, 2);
std::cout << "Print list: \n";
myList.print_list();
// Remove nodes from the list
myList.push_back(9);
myList.push_back(3);
myList.push_back(9);
myList.print_list();
myList.remove_nodes(5);
myList.remove_nodes(9);
myList.remove_nodes(4);
std::cout << "Print list: \n";
myList.print_list();
// Reverse the list
myList.push_back(9);
myList.push_back(3);
myList.push_back(9);
myList.print_list();
myList.reverse();
std::cout << "Print list: \n";
myList.print_list();
}