I'm implementing a linkedlist in C++ with the essential functionalities.
I would like to know what is good in this code and what is bad. In terms of everything (memory usage, functions implementations and optimization, naming conventions, etc...)
I also would like to know how to apply the modern c++ concepts to such code. (Smart pointers, constexpr, lambda expressions, etc...)
Header file:
#ifndef BLINKEDLIST_H
#define BLINKEDLIST_H
#include <memory>
struct Node
{
int key;
Node* next;
};
class BLinkedlist
{
public:
BLinkedlist();
void push_back(int value);
void push_front(int value);
void insert(int idx, int value);
int pop_front();
int pop_back();
void erase(int idx);
int remove_value(int value); //removes the first item in the list with this value
void display();
bool empty();
int value_at(int idx);
int value_n_from_end(int idx);
int front();
int back();
void reverse();
private:
int size;
Node* head;
Node* tail;
};
#endif // BLINKEDLIST_H
Source file:
#include "blinkedlist.h"
#include <stdexcept>
#include <iostream>
BLinkedlist::BLinkedlist():size(0), head(nullptr), tail(nullptr)
{
}
void BLinkedlist::push_back(int value)
{
Node* newNode = new Node();
newNode->key = value;
if(head != nullptr)
{
tail->next = newNode;
}
else
{
head = newNode;
}
tail = newNode;
newNode->next = nullptr;
++size;
}
void BLinkedlist::push_front(int value)
{
Node* newNode = new Node();
newNode->key = value;
if(head != nullptr)
{
newNode->next = head;
}
else
{
newNode->next = nullptr;
tail = newNode;
}
head = newNode;
++size;
}
void BLinkedlist::insert(int idx, int value)
{
if(idx < 0 || idx > size)
{
throw std::out_of_range("Index is out of range!");
}
else
{
Node* newNode = new Node();
newNode->key = value;
if(idx == 0)
{
push_front(value);
}
else if(idx == size)
{
push_back(value);
}
else
{
Node* curr = head;
int i = idx-1;
while(i > 0)
{
curr = curr->next;
--i;
}
newNode->next = curr->next;
curr->next = newNode;
++size;
}
}
}
int BLinkedlist::pop_front()
{
if(head != nullptr && size >= 2)
{
int val = head->key;
head = head->next;
--size;
return val;
}
else if(head != nullptr && size == 1)
{
int val = head->key;
head = nullptr;
tail = nullptr;
--size;
return val;
}
else
{
throw std::logic_error("List is already empty!");
}
}
int BLinkedlist::pop_back()
{
if(head != nullptr && size > 2)
{
int val;
Node* curr = head;
while(curr->next->next != nullptr)
{
curr = curr->next;
}
val = curr->next->key;
curr->next = nullptr;
tail = curr;
--size;
return val;
}
else if(head != nullptr && size == 2)
{
int val = head->next->key;
tail = head;
--size;
return val;
}
else if(head != nullptr && size == 1)
{
int val = head->key;
head = nullptr;
tail = nullptr;
--size;
return val;
}
else
{
throw std::logic_error("List is already empty!");
}
}
void BLinkedlist::erase(int idx)
{
if(idx < 0 || idx > size)
{
throw std::out_of_range("Index is out of range!");
}
else
{
if(idx == 0)
{
pop_front();
}
else if(idx == size)
{
pop_back();
}
else
{
Node* curr = head;
int i = idx-1;
while(i > 0)
{
curr = curr->next;
--i;
}
curr->next = curr->next->next;
--size;
}
}
}
int BLinkedlist::remove_value(int value)
{
Node* curr = head;
int i = 0;
while(curr != nullptr)
{
if(curr->key == value)
{
erase(i);
return i;
}
curr = curr->next;
++i;
}
return -1;
}
void BLinkedlist::display()
{
Node* curr = head;
while(curr != nullptr)
{
std::cout << curr->key << std::endl;
curr = curr->next;
}
}
bool BLinkedlist::empty()
{
return size == 0;
}
int BLinkedlist::value_at(int idx)
{
Node* temp = head;
if(idx < 0 || idx > size)
{
throw std::out_of_range("Index is out of range!");
}
else
{
int i = idx;
while(i != 0 && temp != nullptr)
{
temp = temp->next;
--i;
}
return temp->key;
}
}
int BLinkedlist::value_n_from_end(int idx)
{
if(idx < 0 || idx > size)
{
throw std::out_of_range("Index is out of range!");
}
else
{
int forwardIdx = size - idx;
if(idx == 0)
return tail->key;
Node* curr = head;
while(forwardIdx > 0)
{
curr = curr->next;
--forwardIdx;
}
return curr->key;
}
}
int BLinkedlist::front()
{
return head->key;
}
int BLinkedlist::back()
{
return tail->key;
}
void BLinkedlist::reverse()
{
Node* next = nullptr;
Node* prev = nullptr;
Node* curr = head;
while(curr != nullptr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}
And usage:
#include <iostream>
#include "blinkedlist.h"
int main()
{
BLinkedlist list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);
list.push_back(5);
list.push_back(6);
list.display();
std::cout << "----------------------" << std::endl;
list.reverse();
list.display();
return 0;
}
Any notes and suggestions are much appreciated.
newto allocate Nodes but neverdeleteany, which (arguably) makes the question borderline off topic. Edit your question to address this problem. \$\endgroup\$unique_ptrized version I created on Compiler Explorer actually fixes all the leaks. \$\endgroup\$