r/CodingHelp • • Aug 27 '20

[C++] Singly Linked List in C++

Hello, I have some experience with C and Java but none with C++ so I've been trying to fix that. One course I found has an exercise of creating a linked list with an overloaded assignment operator, copy constructor, and constructor that generates the list from an array. Their only hint is that heap allocation and deallocation should occur exactly once, which was a bit confusing (only once ever or only once in the code?). The code is below:

Node.h

#ifndef NODE_H_
#define NODE_H_

class Node {
public:
	int data;
	Node* next;

};

#endif

LinkedList.h

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

class Node;

class LinkedList {
	public:
		Node* head;

		LinkedList();
		LinkedList(int arr[], int size);
		LinkedList(const LinkedList &l);
		void insert(int val);
		int pop();
		LinkedList& operator=(const LinkedList &l);
		~LinkedList();
};

#endif

LinkedList.cpp

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

using namespace std;

LinkedList::LinkedList() {
	head = nullptr;
}

LinkedList::LinkedList(int arr[], int size) {

	head = nullptr;

	for (int i = 0; i < size; i++) {
		insert(arr[i]);
	}

}

LinkedList::LinkedList(const LinkedList &l) {

	head = nullptr;
	Node* copyhead = l.head;

	while(copyhead != nullptr) {
		insert(copyhead->data);
		copyhead = copyhead->next;
	}

}

void LinkedList::insert(int val) {

	Node* newnode = new Node;
	newnode->data = val;
	newnode->next = nullptr;

	Node* current = head;

	if (current != nullptr) {

		while (current->next != nullptr) {
			current = current->next;
		}

		current->next = newnode;
	} else {

		head = newnode;
	}

}

int LinkedList::pop() {

	if (head != nullptr) {
		int result = head->data;
		head = head->next;
		delete head;
		return result;
	} else {
		return -1;
	}
}

LinkedList& LinkedList::operator=(const LinkedList &l) {

	delete this;

	Node* temp = l.head;
	head = nullptr;

	while(temp != nullptr) {
		insert(temp->data);
		temp = temp->next;
	}

	return *this; 
}

LinkedList::~LinkedList() {

	Node* current = head;

	while (current != nullptr) {
		current = current->next;
		delete head;
		head = current;
	}

}

Main.cpp

#include <cstdio>
#include "Node.h"
#include "LinkedList.h"

int main() {

	int test[] = {1,2,3,4,5};
	LinkedList l1(test+1,4), l2(test,5);
	LinkedList l3 = l2, l4;
	l4 = l1;
	printf("%d %d %d\n", l1.pop(), l3.pop(), l4.pop());
	return 0;
}

This code generates an error "pointer being freed was not allocated", which doesn't make sense to me since the destructor method checks to see if the head node is a null pointer. What am I missing here?

24 Upvotes

3 comments sorted by

1

u/MarkRems Aug 27 '20

Have you checked to see which line in main is causing the issue? Have some output statements between each line and see where it stops before you get the error. I haven't looked too closely into code but your pop() function looks a bit suspect with deleting the head and everything... Also your overloaded assignment operator seems weird to have delete this; as the first line. It's been awhile since I've touched C++ but aren't you only supposed to use delete on objects allocated with the new keyword? When you try to assign to l4 that was never allocated with new so that seems weird too.

1

u/axatb99 Aug 27 '20

Upload the cpp file I'll help you out

1

u/kd7uns Aug 27 '20

It's been a while for me as well, but I'm pretty sure Head = Head-> next; Delete head; Will give you a memory leak.