I am currently writing a program to mimic the functions of a linked list. I think the the code is crashing due to memory leaks, but I cannot figure out where they might be. I have tried deleting after every new, but when I delete it causes the functions to not operate correctly. I also think I my push_back() function may not be operating correctly, because my output does not match the output of std::list. Any help would be greatly appreciated. Thanks!
When I run the program this is the output I receive: 4000 33 100 3 33 100 423 423 100 33 200 100 4000 double free or corruption (fasttop) Aborted (core dumped)
This is the output I am expecting: 4000 33 100 3 33 100 423 423 100 423 33 200 100
Header File:
#ifndef MYLIST_H
#define MYLIST_H
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
using std::cerr;
using std::string;
template <typename T>
class Node
{
public:
T m_element;
Node<T> *m_prev;
Node<T> *m_next;
// Helps you make a dummy/sentinel/junk node
Node(Node<T> *in_prev, Node<T> *in_next):
m_prev(in_prev), m_next(in_next){}
Node(const T &x, Node<T> *in_prev, Node<T> *in_next):
m_element(x), m_prev(in_prev), m_next(in_next){}
};
template <typename T>
class MyList
{
private:
Node<T> *m_sentinel = nullptr;
int m_size;
public:
// A list size of 0 will have 1 sentinel node.
MyList();
~MyList();
MyList<T> & operator=(const MyList<T> &source);
MyList(const MyList<T> &source);
T & front();
T & back();
void assign(int count, const T &value);
// Default list size of 0, with one sentinel node, as above in constructor
void clear();
void push_front(const T &x);
void push_back(const T &x);
void pop_back();
void pop_front();
// Simplified version that only takes one int position.
// Inserts before element at position i.
// Not exactly like std::
// You do NOT need a special case for 0-big lists (i.e., no if size == 0)
// You should be able to insert in 0 big list.
void insert(int i, const T &x);
// Removes all elements in list that are equal to value.
// You do NOT need a special case for 0-big lists (i.e., no if size == 0).
void remove(T value);
// Removes element at position i.
void erase(int i);
void reverse();
bool empty();
int size();
// Mimicking C++ iterator trickery from here down.
// You don't need to edit these two.
int begin()
{
return 0;
}
int end()
{
return size();
}
};
#include "MyList.hpp"
#endif
HPP File:
template <typename T>
MyList<T>::MyList()
{
m_sentinel = new Node<T>(nullptr, nullptr);
m_sentinel->m_next = m_sentinel;
m_sentinel->m_prev = m_sentinel;
m_size = 0;
}
template <typename T>
MyList<T>::~MyList()
{
Node<T> *temp;
for(int i = 0; i < m_size; i++)
{
temp = m_sentinel->m_prev;
delete m_sentinel->m_prev;
m_sentinel->m_prev = temp->m_prev;
}
delete m_sentinel;
m_sentinel = nullptr;
}
template <typename T>
MyList<T> & MyList<T>::operator=(const MyList<T> &source)
{
this->~MyList();
Node<T>* tempNode = new Node<T>(nullptr, nullptr);
tempNode = source.m_sentinel->m_next;
m_sentinel = new Node<T>(nullptr, nullptr);
m_sentinel->m_next = m_sentinel;
m_sentinel->m_prev = m_sentinel;
for(int i = 0; i < source.m_size; i++)
{
this->push_back(tempNode->m_element);
tempNode = tempNode->m_next;
}
}
template <typename T>
MyList<T>::MyList(const MyList<T> &source)
{
*this = source;
}
template <typename T>
T & MyList<T>::front()
{
return m_sentinel->m_next->m_element;
}
template <typename T>
T & MyList<T>::back()
{
return m_sentinel->m_prev->m_element;
}
template <typename T>
void MyList<T>::assign(int count, const T &value)
{
while(m_size)
{
this->pop_back();
}
for(int i = 0; i < count; i++)
{
this->push_back(value);
}
m_size = count;
}
// Default list size of 0, with one sentinel node, as above in constructor
template <typename T>
void MyList<T>::clear()
{
while(m_size)
{
this->pop_back();
}
}
template <typename T>
void MyList<T>::push_front(const T &x)
{
Node<T> *tempNode = new Node<T>(x, m_sentinel, m_sentinel->m_next);
m_sentinel->m_next->m_prev = tempNode;
m_sentinel->m_next = tempNode;
m_size++;
}
template <typename T>
void MyList<T>::push_back(const T &x)
{
Node<T> *tempNode = new Node<T>(x, m_sentinel->m_prev, m_sentinel);
m_sentinel->m_prev = tempNode;
tempNode->m_prev->m_next = tempNode;
m_size++;
}
template <typename T>
void MyList<T>::pop_back()
{
//edit
if(m_size != 0)
{
//check if temp node is needed
//Node<T> *tempNode = m_sentinel->m_prev;
m_sentinel->m_prev = m_sentinel->m_prev->m_prev;
delete m_sentinel->m_prev->m_next;
m_sentinel->m_prev->m_next = nullptr;
m_sentinel->m_prev->m_next = m_sentinel;
//delete tempNode;
m_size--;
}
}
template <typename T>
void MyList<T>::pop_front()
{
if(m_size != 0)
{
m_size--;
m_sentinel->m_next = m_sentinel->m_next->m_next;
delete m_sentinel->m_next->m_prev;
m_sentinel->m_next->m_prev = nullptr;
m_sentinel->m_next->m_prev = m_sentinel;
}
}
// Simplified version that only takes one int position.
// Inserts before element at position i.
// Not exactly like std::
// You do NOT need a special case for 0-big lists (i.e., no if size == 0)
// You should be able to insert in 0 big list.
template <typename T>
void MyList<T>::insert(int i, const T &x)
{
if(i >= 0 && i < m_size)
{
Node<T> *tempNode = m_sentinel;
for(int j = 0; j < i; j++)
{
tempNode = tempNode->m_next;
}
Node<T> *insertNode = new Node<T>(x, tempNode, tempNode->m_next);
tempNode->m_prev->m_next = insertNode;
tempNode->m_next->m_prev = insertNode;
m_size++;
}
}
// Removes all elements in list that are equal to value.
// You do NOT need a special case for 0-big lists (i.e., no if size == 0).
template <typename T>
void MyList<T>::remove(T value)
{
Node<T> *currentNode = m_sentinel->m_next;
Node<T> *tempNode = currentNode->m_next;
int counter = m_size;
for(int i = 0; i < counter; i++)
{
if(currentNode->m_element == value)
{
currentNode->m_prev->m_next = currentNode->m_next;
currentNode->m_next->m_prev = currentNode->m_prev;
tempNode = currentNode->m_next;
m_size--;
delete currentNode;
currentNode = nullptr;
currentNode = tempNode;
}
else
{
currentNode = currentNode->m_next;
}
}
}
// Removes element at position i.
template <typename T>
void MyList<T>::erase(int i)
{
if(i >= 0 && i < m_size)
{
Node<T> *currentNode = m_sentinel->m_next;
for(int j = 0; j < i; j++)
{
currentNode = currentNode->m_next;
}
currentNode->m_prev->m_next = currentNode->m_next;
currentNode->m_next->m_prev = currentNode ->m_prev;
delete currentNode;
currentNode = nullptr;
m_size--;
}
}
template <typename T>
void MyList<T>::reverse()
{
Node<T> *nextNode = m_sentinel->m_next;
Node<T> *prevNode = m_sentinel->m_prev;
for(int i = 0; i < (m_size/2); i++)
{
std::swap(nextNode->m_element, prevNode->m_element);
nextNode = nextNode->m_next;
prevNode = prevNode->m_prev;
}
}
template <typename T>
bool MyList<T>::empty()
{
if(m_size==0)
{
return true;
}
else
{
return false;
}
}
template <typename T>
int MyList<T>::size()
{
return m_size;
}
Driver to test if MyList function works like std::list:
#include <list>
#include "MyList.h"
int main()
{
MyList<int> l;
//std::list<int> l;
l.push_back(4000);
l.push_back(200);
l.push_back(100);
cout << l.front() << endl;
l.front() = 33;
cout << l.front() << endl;
cout << l.back() << endl;
cout << l.size() << endl;
l.push_back(4000);
l.push_back(200);
l.push_back(100);
cout << l.front() << endl;
cout << l.back() << endl;
l.push_front(423);
cout << l.front() << endl;
MyList<int> sink;
sink = l;
cout << sink.front() << endl;
cout << sink.back() << endl;
l.insert(l.begin(), 3);
l.insert(l.end(), 20);
l.pop_front();
l.reverse();
int j = 0;
for(auto i = 0; i < l.size(); i++)
{
cout << l.back() << endl;
l.pop_back();
j++;
}
return 0;
}
Thanks!
UPDATED COPY CONSTRUCTOR AND ASSIGNMENT OPERATOR
template <typename T>
MyList<T> & MyList<T>::operator=(const MyList<T> &source)
{
MyList<T> temp(source);
std::swap(temp.m_sentinel, m_sentinel);
return *this;
}
template <typename T>
MyList<T>::MyList(const MyList<T> &source)
{
Node<T> *temp = source.m_sentinel;
m_sentinel = nullptr;
while(temp != nullptr)
{
push_back(temp->m_element);
}
}
Now it gives me a segfault and crashes when calling the push_back() function. I'm lost. I've tried implementing this several different ways but every time I either get a double free or a segfault.
