Noob learns to code in 3 months

The Partridge Family were neither partridges nor a family. Discuss.
User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: Noob learns to code in 3 months

Post by Yumtard » September 11th, 2017, 8:46 pm

^ muchos no buenos

So I missed todays lecture about linked lists due to being ill. But a classmate sent me the assignment.
Fighting throught the illnes by cycling sleep with doing assignment.
Have 3 tasks on the assignment

task 1: make a singly linked list with these functions:
Prepend(value)
Append(value)
Clear()
PopFront()
PopBack()
PrintItems()

task 2: implement a doubly linked list class with the same functions as in task 1

task 3: use templates to allow construction of a linked list containing any data type

I've finshed task 1, think I'm not leaking any memory

Node.h (made 2 constructors and Node* prev so I wont have to make a whole new Node class for task 2)

Code: Select all

#pragma once

class Node
{
public:
	Node(Node* next_in, int value_in);
	Node(Node* next_in, Node* prev_in, int value_in);
	Node* next = nullptr;
	Node* prev = nullptr;
	int value;
};
Node.cpp

Code: Select all

#include "Node.h"

Node::Node(Node * next_in, int value_in)
	:
	next(next_in),
	prev(nullptr),
	value(value_in)
{}

Node::Node(Node * next_in, Node * prev_in, int value_in)
	:
	next(next_in),
	prev(prev_in),
	value(value_in)
{}

SinglyLinkedList.h

Code: Select all

#pragma once

#include "Node.h"
#include <iostream>

class SinglyLinkedList
{
public:
	SinglyLinkedList();
	~SinglyLinkedList();
	void Prepend(int value_in);
	void Append(int value_in);
	void Clear();
	void PopFront();
	void PopBack(); 
	void PrintItems();

private:
	Node* m_First = nullptr;
};
SinglyLinkedList.cpp

Code: Select all

#include "SinglyLinkedList.h"

SinglyLinkedList::SinglyLinkedList()
{
	m_First = nullptr;
}

SinglyLinkedList::~SinglyLinkedList()
{
	Clear();
	delete m_First;
}

void SinglyLinkedList::Prepend(int value_in)
{
	m_First = new Node(m_First, value_in);
}

void SinglyLinkedList::Append(int value_in)
{
	if (!m_First)
	{
		Prepend(value_in);
	}
	else
	{
		Node* node;
		for (node = m_First; node->next; node = node->next);
		node->next = new Node(nullptr, value_in);
	}
}

void SinglyLinkedList::Clear()
{
	if (m_First)
	{
		Node* curNode = m_First;
		Node* prevNode = nullptr;

		while (curNode)
		{
			prevNode = curNode;
			curNode = curNode->next;
			delete prevNode;
			prevNode = nullptr;
		}
	}
}

void SinglyLinkedList::PopFront()
{
	if (m_First)
	{
		if (m_First->next)
		{
			Node* first = m_First;
			m_First = m_First->next;
			delete first;
			first = nullptr;
		}
		else
		{
			delete m_First;
			m_First = nullptr;
		}
	}
}

void SinglyLinkedList::PopBack()
{
	if (m_First)
	{
		if (m_First->next)
		{
			Node* last = m_First;
			Node* prev = m_First;
			for (; last->next; prev = last, last = last->next);
			delete last;
			last = nullptr;
			prev->next = nullptr;
		}
		else
		{
			delete m_First;
			m_First = nullptr;
		}
	}
}

void SinglyLinkedList::PrintItems()
{
	if (!m_First)
	{
		std::cout << "List is empty.\n";
	}
	else
	{
		for (Node* i = m_First; i; i = i->next)
		{
			std::cout << i->value << std::endl;
		}
	}
}

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Noob learns to code in 3 months

Post by albinopapa » September 11th, 2017, 9:36 pm

Looks solid to me.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: Noob learns to code in 3 months

Post by Yumtard » September 11th, 2017, 11:35 pm

Thanks papa! That feels reassuring :)

Doubly linked was a bit of a brain teaser.. this seems to work though.
Added a function init() to this class.

Code: Select all

#include "DoublyLinkedList.h"

DoublyLinkedList::DoublyLinkedList()
{
	Init();
}

DoublyLinkedList::~DoublyLinkedList()
{
	Clear();
	delete m_First;
	m_First = nullptr;
}

void DoublyLinkedList::Init()
{
	m_First = new Node;
	m_First->next = m_First;
	m_First->prev = m_First;
}

void DoublyLinkedList::Prepend(int value_in)
{
	if (!m_First)
	{
		Init();
	}

	Node* node = new Node(m_First->next, m_First, value_in);
	m_First->next = node;
}

void DoublyLinkedList::Append(int value_in)
{
	if (!m_First)
	{
		Init();
	}

	Node* node = new Node(m_First, m_First->prev, value_in);
	m_First->prev->next = node;
	m_First->prev = node;
}

void DoublyLinkedList::Clear()
{
	if (m_First->next != m_First)
	{
		Node* curNode = m_First->next;
		Node* prevNode = nullptr;

		while (curNode != m_First)
		{
			prevNode = curNode;
			curNode = curNode->next;
			delete prevNode;
			prevNode = nullptr;
		}
		delete m_First;
		m_First = nullptr;
	}
}

void DoublyLinkedList::PopFront()
{
	if (m_First->next != m_First)
	{
		Node* first = m_First->next;
		m_First->next = first->next;
		first->next->prev = m_First;
		delete first;
		first = nullptr;
	}
}

void DoublyLinkedList::PopBack()
{
	if (m_First->next != m_First)
	{
		Node* last = m_First->prev;
		m_First->prev = last->prev;
		last->prev->next = m_First;
		delete last;
		last = nullptr;
	}
}

void DoublyLinkedList::PrintItems()
{	
	if (m_First->next != m_First)
	{
		for (Node* i = m_First->next; i != m_First; i = i->next)
		{
			std::cout << i->value << std::endl;
		}
	}
	else
	{
		std::cout << "List is empty." << std::endl;
	}
}
Just templates left now

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: Noob learns to code in 3 months

Post by Yumtard » September 12th, 2017, 12:10 am

Wait, if I do a tempalte class I need to write template <class T> before every single function of that class??? or am I doing something wrong??

Code: Select all

template <class T>
DoublyLinkedList<T>::DoublyLinkedList()
{
	Init();
}

template <class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
	Clear();
	delete m_First;
	m_First = nullptr;
}
etcetc

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: Noob learns to code in 3 months

Post by Yumtard » September 12th, 2017, 12:26 am

Double wait... I can't do template and implement the functions in a cpp file?? I need to implement the functions in the h file?

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Noob learns to code in 3 months

Post by chili » September 12th, 2017, 1:05 am

Template classes and template functions are completely separate bro. And yeah, you need to put the whole thing in the .h file for a template. The compiler needs access to the entire implementation at the time of compilation.
Chili

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: Noob learns to code in 3 months

Post by Yumtard » September 12th, 2017, 11:12 am

Alrighty. It feels kinda dirty do have so much code in the h file but oh well. Here's my final code for the assignments


Singly linked

Code: Select all

#pragma once

#include <iostream>

template <class T>
class SinglyLinkedList
{
private:
	class Node
	{
	public:
		Node(Node* next_in = nullptr, T data_in = T())
			:
			next(next_in),
			data(data_in)
		{}
		Node* next;
		T data;
	};

private:
	Node* m_First = nullptr;

public:
	SinglyLinkedList()
	{
		m_First = nullptr;
	}
	~SinglyLinkedList()
	{
		Clear();
		delete m_First;
		m_First = nullptr;
	}
	void Prepend(T data_in)
	{
		m_First = new Node(m_First, data_in);
	}
	void Append(T data_in)
	{
		if (!m_First)
		{
			Prepend(data_in);
		}
		else
		{
			Node* node;
			for (node = m_First; node->next; node = node->next);
			node->next = new Node(nullptr, data_in);
		}
	}
	void Clear()
	{
		if (m_First)
		{
			Node* curNode = m_First;
			Node* prevNode = nullptr;

			while (curNode)
			{
				prevNode = curNode;
				curNode = curNode->next;
				delete prevNode;
				prevNode = nullptr;
			}
			m_First = nullptr;
		}
	}
	void PopFront()
	{
		if (m_First)
		{
			if (m_First->next)
			{
				Node* first = m_First;
				m_First = m_First->next;
				delete first;
				first = nullptr;
			}
			else
			{
				delete m_First;
				m_First = nullptr;
			}
		}
	}
	void PopBack()
	{
		if (m_First)
		{
			if (m_First->next)
			{
				Node* last = m_First;
				Node* prev = m_First;
				for (; last->next; prev = last, last = last->next);
				delete last;
				last = nullptr;
				prev->next = nullptr;
			}
			else
			{
				delete m_First;
				m_First = nullptr;
			}
		}
	}
	void PrintItems()
	{
		if (!m_First)
		{
			std::cout << "List is empty.\n";
		}
		else
		{
			for (Node* i = m_First; i; i = i->next)
			{
				std::cout << i->data << std::endl;
			}
		}
	}
};
Doubly linked

Code: Select all

#pragma once

#include <iostream>

template <class T>
class DoublyLinkedList
{
private:
	class Node
	{
	public:
		Node(Node* next_in = nullptr, Node* prev_in = nullptr, T data_in = T())
			:
			next(next_in),
			prev(prev_in),
			data(data_in)
		{}
		Node* next;
		Node* prev;
		T data;
	};

private:
	Node* m_First = nullptr;

public:
	DoublyLinkedList()
	{
		Init();
	}
	~DoublyLinkedList()
	{
		Clear();
		delete m_First;
		m_First = nullptr;
	}
	void Init()
	{
		m_First = new Node;
		m_First->next = m_First;
		m_First->prev = m_First;
	}
	void Prepend(T data_in)
	{
		if (!m_First)
		{
			Init();
		}

		Node* node = new Node(m_First->next, m_First, data_in);
		m_First->next = node;
	}
	void Append(T data_in)
	{
		if (!m_First)
		{
			Init();
		}

		Node* node = new Node(m_First, m_First->prev, data_in);
		m_First->prev->next = node;
		m_First->prev = node;
	}
	void Clear()
	{
		if (m_First->next != m_First)
		{
			Node* curNode = m_First->next;
			Node* prevNode = nullptr;

			while (curNode != m_First)
			{
				prevNode = curNode;
				curNode = curNode->next;
				delete prevNode;
				prevNode = nullptr;
			}
			delete m_First;
			m_First = nullptr;
		}
	}
	void PopFront()
	{
		if (m_First->next != m_First)
		{
			Node* first = m_First->next;
			m_First->next = first->next;
			first->next->prev = m_First;
			delete first;
			first = nullptr;
		}
	}
	void PopBack()
	{
		if (m_First->next != m_First)
		{
			Node* last = m_First->prev;
			m_First->prev = last->prev;
			last->prev->next = m_First;
			delete last;
			last = nullptr;
		}
	}
	void PrintItems()
	{
		if (m_First && m_First->next != m_First)
		{
			for (Node* i = m_First->next; i != m_First; i = i->next)
			{
				std::cout << i->data << std::endl;
			}
		}
		else
		{
			std::cout << "List is empty." << std::endl;
		}
	}
};

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: Noob learns to code in 3 months

Post by Yumtard » September 12th, 2017, 12:00 pm

nvm made some small changes. Realized the program wasn't completely safe. It crashed if you tried to clear or pop an already cleared list. So added else conditions to those functions

if (m_First && m_First->next != m_First)
{
Node* last = m_First->prev;
m_First->prev = last->prev;
last->prev->next = m_First;
delete last;
last = nullptr;
}
else
{
std::cout << "List is already empty." << std::endl;
}

Think I'm also gonna add deep copy or at least make it not allowed to try and do list1 = list2.
The assignment doesn't mention it but it says "retain program stability" and this, I guess would add to the stability of the program


Edit:
Just added this in private: for singly and doubly linked so it gives an error if someone tries to list1 = list2. That wil do for this assignment imo

DoublyLinkedList(const DoublyLinkedList&) {};
DoublyLinkedList& operator=(const DoublyLinkedList&) { return *this; };

User avatar
Yumtard
Posts: 575
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

Re: Noob learns to code in 3 months

Post by Yumtard » September 12th, 2017, 4:11 pm

Aparently we're starting the math course next week!
Good thing I studied some maths this summer.
Will do some repetition over the weekend after I've watched the last few episodes of intermediate.

Enough spamming for today!

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Noob learns to code in 3 months

Post by albinopapa » September 12th, 2017, 9:18 pm

Yumtard wrote:nvm made some small changes. Realized the program wasn't completely safe. It crashed if you tried to clear or pop an already cleared list. So added else conditions to those functions

if (m_First && m_First->next != m_First)
{
Node* last = m_First->prev;
m_First->prev = last->prev;
last->prev->next = m_First;
delete last;
last = nullptr;
}
else
{
std::cout << "List is already empty." << std::endl;
}

Think I'm also gonna add deep copy or at least make it not allowed to try and do list1 = list2.
The assignment doesn't mention it but it says "retain program stability" and this, I guess would add to the stability of the program


Edit:
Just added this in private: for singly and doubly linked so it gives an error if someone tries to list1 = list2. That wil do for this assignment imo

DoublyLinkedList(const DoublyLinkedList&) {};
DoublyLinkedList& operator=(const DoublyLinkedList&) { return *this; };

Code: Select all

DoublyLinkedList(const DoublyLinkedList&) = delete;
DoublyLinkedList& operator=(const DoublyLinkedList&) = delete;
The way you did it is the old way, you can disable those functions with = delete.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply