About Raw Pointers and Linked Lists

[bydrachen]

Hi again. I'm studying the linked lists in C and C++. Here, I tried to copy C code into C++ code. Because I'm experimenting with different structures.

My question was why the code goes an endless loop when I execute the commented delete line down there. I figured it out while typing this because it is deleting the whole node, not the pointer itself (am I right?). There is no need to delete the temp because it's always assigning to a new node. But is it causing a memory leak after the process is done? I read that I don't have to use smart pointers with linked lists (I still don't know how to use them or what's they actually). They say it makes things more complex.

The other thing is, is it OK to use nullptr instead of NULL while coding linked lists? I read that in modern C++, it's solving some problems. But can it cause different problems here?

#include <iostream>

class Node
{
public:

	int data;
	Node* next;

}*head = nullptr;

void create (int A[], int size)
{
	Node *temp, *last;

	head = new Node;
	head -> data = A[0];
	head -> next = nullptr;
	last = head;

	for (auto i {1}; i < size; i++)
	{
		temp = new Node;
		temp -> data = A[i];
		temp -> next = nullptr;

		last -> next = temp;
		last = temp;

		//delete temp;
	}
}

void display (Node* temp)
{
	while (temp != nullptr)
	{
		std::cout << temp -> data << " ";
		temp = temp ->next;
	}
}

int main ()
{
	int A[] {3,5,7,10,15};
	
	create (A, 5);
	display(head);
	
	return 0;
}

[Peter87]

My question was why the code goes an endless loop when I execute the commented delete line down there. I figured it out while typing this because it is deleting the whole node, not the pointer itself (am I right?).

You're right. delete doesn't destroy the pointer. It destroys the thing that the pointer points to. You don't want to do delete temp; on line 30 because then you'll destroy the node that you just inserted and last will be dangling which will lead to problems on the next iteration when you try to access the node that no longer exists. For you it happened to lead to an infinite loop but it's technically undefined behaviour so there are no guarantees what will happen.

But is it causing a memory leak ...

Yes. But you probably want to do the clean up (with delete) in a separate function when you're done using the linked list (if you wrote a LinkedList class this would normally be done in the destructor).

If you ever removed nodes before you're done using the linked list then you would also want to use delete to destroy those nodes.

... after the process is done?

The operating system will clean up all memory when the process has ended.

I read that I don't have to use smart pointers with linked lists (I still don't know how to use them or what's they actually). They say it makes things more complex.

Smart pointers are tools. You never have to use them but they can often help you write better code where you don't have to worry too much about memory leaks.

Note that when people talk about "smart pointers" I think they primarily think about std::unique_ptr.

The other thing is, is it OK to use nullptr instead of NULL while coding linked lists? I read that in modern C++, it's solving some problems. But can it cause different problems here?

It's recommended to use nullptr in C++ but it's not a big deal. It has some small advantages that you probably won't notice very often but there are no downsides as far as I am aware so why not use it.

[jonnin]

I highly recommend in c++ you do not use the global variable attached to a class.
that is

class foo
{..} x; //x is a global variable. worse, its hard to find and in a weird place. 

just make the variable normally: 
int main()
{
  foo x; //here
}

you may want some of the functions you write to be member functions. That is a big point of C++ over C.

if your linked list is not sorted, it is most efficient to work off the top (head).
eg insert:
new item
item -> next = head
head = item

and deleting: //as long as head isnt null
tmp = head->next
delete head;
head = tmp

if you do either of these off the middle or far end, there is a lot of extra code needed.

a lot of LL code is based off the idea of null moving into place 'naturally'.
if you loop to delete as I said above, when head->next is null, head gets assigned null from that.. do you see how it will move the null up into head and stop looping properly?

[seeplus]

Based upon OP then consider:

#include <iostream>

struct Node {
	int data {};
	Node* next {};

	Node(int d, Node* n) : data(d), next(n) {}
};

Node* head {};

void create(const int A[], size_t size) {
	for (size_t i {}; i < size; ++i)
		head = new Node(A[i], head);
}

void display(Node* temp = head) {
	for (; temp; temp = temp->next)
		std::cout << temp->data << ' ';

	std::cout << '\n';
}

void displayR(Node* temp = head) {
	if (temp) {
		const auto d { temp->data };

		displayR(temp->next);
		std::cout << d << ' ';
	}
}

void erase(Node* temp = head) {
	if (temp) {
		const auto nxt { temp->next };

		delete temp;
		erase(nxt);
	}
}

int main() {
	const int A[] {3, 5, 7, 10, 15};

	create(A, 5);
	display();
	displayR();
	erase();
}

15 10 7 5 3
3 5 7 10 15

and as a C++ class, then possibly:

#include <iostream>

class LL {
	struct Node {
		int data {};
		Node* next {};

		Node(int d, Node* n) : data(d), next(n) {}
	};

	Node* head {};

	static void dis(Node* temp) {
		if (temp) {
			const auto d { temp->data };

			dis(temp->next);
			std::cout << d << ' ';
		}
	}

public:
	LL() {}

	~LL() {
		while (head) {
			const auto nxt { head->next };

			delete head;
			head = nxt;
		}
	}

	LL(const LL&) = delete;
	LL& operator=(const LL&) = delete;

	void create(const int A[], size_t size) {
		for (size_t i {}; i < size; ++i)
			head = new Node(A[i], head);
	}

	void display() const {
		for (auto temp {head}; temp; temp = temp->next)
			std::cout << temp->data << ' ';

		std::cout << '\n';
	}

	void displayR() const {
		dis(head);
	}

};

int main() {
	const int A[] {3, 5, 7, 10, 15};

	LL ll;

	ll.create(A, 5);
	ll.display();
	ll.displayR();
}

[bydrachen]

Peter87, jonnin, seeplus; thanks for your big help. I can't still understand how are some people being this much helpful.