Singly linked list add at end

[4ET0pfjN]

Hi, I'm trying to add items to end of list. I have a front and end pointers to keep track of list, but it doesn't compile.

struct sll_node//singly linked list node
{
 string data;
 sll_node *next;
}

function to add node at end of list:
===================================

void add_at_end(string node_data, sll_node *front, sll_node *end)
{
	//NB: it's these little things that I screw up on
	//	like if asked quickly do we include asterisk in declaring a new node
	//	it's yes BUT do you know why????
	sll_node *newNode = new sll_node;
	newNode->data = node_data;
	newNode->next = NULL;
	
	//If list is empty, then head and tail pts to the newNode
	if ( front == NULL && end == NULL )
	{
		front = newNode;
		end = newNode;
	}
	
	//Else the list is not empty, so just update tail ptr and leave head ptr alone!
	else
	{
		end->next = newNode;
		end = newNode;
	}
}

int main()
{
 sll_node *front = new sll_node;
 sll_node *end = new sll_node;
 front = NULL;
 end = NULL;

 add_at_end("A", front, end);
 add_at_end("AA", front, end);
 add_at_end("DDEE", front, end);

 return 0;
}

[kbw]

You need to pass in the front and end pointers by reference; that is, you need to pass in the address of the pointer. They're being treated as local variables within the function as it stands.

[4ET0pfjN]

I changed in main:

add_at_end("A", &front, &end);
add_at_end("AA", &front, &end);
add_at_end("DDEE", &front, &end);

but it's not working still

[4ET0pfjN]

hi kbw,

plz show me what you mean

[kbw]

I have updated add_at_end to take the address of the head/end and updated the calls to add_at_end. I also added a print function to print the list after each add.

#include <iostream>
#include <string>

using namespace std;

struct sll_node
{
	string data;
	sll_node *next;
};

void add_at_end(string node_data, sll_node **front, sll_node **end)
{
	//NB: it's these little things that I screw up on
	//	like if asked quickly do we include asterisk in declaring a new node
	//	it's yes BUT do you know why????
	sll_node *newNode = new sll_node;
	newNode->data = node_data;
	newNode->next = NULL;
	
	//If list is empty, then head and tail pts to the newNode
	if (*front == NULL && *end == NULL)
	{
		*front = newNode;
		*end = newNode;
	}
	
	//Else the list is not empty, so just update tail ptr and leave head ptr alone!
	else
	{
		(*end)->next = newNode;
		*end = newNode;
	}
}

ostream& print(ostream& os, sll_node* p)
{
	while (p)
	{
		os << p->data << '\n';
		p = p->next;
	}

	os << '\n';
	return os;
}

int main()
{
	sll_node *front = 0;
	sll_node *end = 0;

	add_at_end("A", &front, &end);
	print(cout, front);

	add_at_end("AA", &front, &end);
	print(cout, front);

	add_at_end("DDEE", &front, &end);
	print(cout, front);

	return 0;
}

[4ET0pfjN]

so when we pass by reference (the ** in the add_to_end function), is it b/c we don't know what mem address user will user for the node pointers, i don't even know what i'm saying.

[4ET0pfjN]

hi kbw, i hope you can explain the changes you made.

[kbw]

Your linked list nodes are sll_node.

Each node, the head and the end values are of type sll_node*.

You have an append function called add_at_end which takes the head, end and payload data. This function is correct, except it doesn't update head and end. It doesn't do so because they are passed by value.

Look at this example:

#include <iostream>

using namespace std;

void reset_ptr1(void* ptr)
{
    ptr = 0;
}

void reset_ptr2(void** ptr)
{
    *ptr = 0;
}

int main()
{
    void* p = (void*)main; // just some non zero value

    reset_ptr1(p);
    cout << p << endl;

    reset_ptr2(&p);
    cout << p << endl;

    return 0;
}

reset_ptr1 does the right thing, but the pointer is passed in by value, so the called value is never updated.

reset_ptr2 does the right thing and the address of the pointer is passed in. This causes the value in the caller to be updated.

[4ET0pfjN]

Late reply, but why does it have to be *front = newNode from your changes:

if (*front == NULL && *end == NULL)
{
	*front = newNode;
	*end = newNode;
}

because I thought front is a pointer so we want it to store memory address of newNode...i'm confused now b/c isn't *front = newNode the dereference operator...

Also, is it ok with

if (*front->next == NULL & *end->next == NULL )

[kbw]

You're passed the address of a pointer. So to change the value of the pointer, you need to dereference it.

It's no different with an int.

void add(int* value, int operand)
{
    (*value) += operand;
}

int main()
{
    int i = 0;
    add(&i, 5);
    return 0;
}

Compare that with the pointer example above:
http://www.cplusplus.com/forum/general/69711/#msg372422

[4ET0pfjN]

So shouldn't it be: void add(int **value, int operand)?

[kbw]

No.

Your pointer type is sll_node*. The a pointer to one of those is sll_node**.

A pointer to an int is int*.

[4ET0pfjN]

I don't know why this is so complicated for me, there's pass by value, pass by reference and pass by address...i'm going to have to look up myself, appreciate all your help and patience thanks

[kbw]

It is tricky, it all comes form C and that is necessarily a primitive language.

C has no pass by reference, it only has pass by value.

Internally, languages that pass by reference pass the address of the variable. It's just syntactic sugar to not dereference the parameter in the function.

Although C has no pass by reference, it does achieve the same effect by allowing you to pass the address of a variable. The catch is that in the function, you need to explicitly dereference the variable before you use it.

The example I gave uses this method to pass in the pointer. However, as C++ provides pass by reference, you can do the same thing using references. I tend to use typedefs to simplify type declarations. Here's the original post with references.

#include <iostream>
#include <string>

using namespace std;

struct sll_node
{
        string data;
        sll_node *next;
};
typedef sll_node* psll_node;

void add_at_end(string node_data, psll_node &front, psll_node &end)
{
        //NB: it's these little things that I screw up on
        //      like if asked quickly do we include asterisk in declaring a new node
        //      it's yes BUT do you know why????
        sll_node *newNode = new sll_node;
        newNode->data = node_data;
        newNode->next = NULL;

        //If list is empty, then head and tail pts to the newNode
        if (front == NULL && end == NULL)
        {
                front = newNode;
                end = newNode;
        }

        //Else the list is not empty, so just update tail ptr and leave head ptr alone!
        else
        {
                end->next = newNode;
                end = newNode;
        }
}

ostream& print(ostream& os, sll_node* p)
{
        while (p)
        {
                os << p->data << '\n';
                p = p->next;
        }

        os << '\n';
        return os;
}

int main()
{
        sll_node *front = 0;
        sll_node *end = 0;

        add_at_end("A", front, end);
        print(cout, front);

        add_at_end("AA", front, end);
        print(cout, front);

        add_at_end("DDEE", front, end);
        print(cout, front);

        return 0;
}

[4ET0pfjN]

just curious, when we want to add a new node, we create a new node structure and then make tail pointer point to it, but shouldn't we also delete the pointer to which tail pointer points to now since it's unnecessary, I mean:

node *newNode;
(*newNode).data = "hello";
(*newNode).next = NULL;
(*tail).next = newNode;
tail = newNode;

**So shouldn't we delete newNode pointer, not where it points to i mean, but the pointer itself for memory sake...

i hope my use of pointers above in code snippet is right

[kbw]

I'm not sure what part of the post is new so I'll deal with all of it.

when we want to add a new node, we create a new node structure and then make tail pointer point to it,

Yes, and you also point the last element of the list to the node as you've done in your example code.

The example code doesn't show the allocation, but you do correctly make the allocation in your original post.

node *newNode = new node;

**So shouldn't we delete newNode pointer

No. The linked list is a series of linked nodes. When you allocate newNode from the heap, that memory/object becomes the next link in the linked list.

You only delete the memory when you delete a link from the linked list.

[Gaminic]

In all fairness, rather than dealing with pass-by-references issues, you should have wrapped it all into a List class and made "add_at_end" a member function.

[4ET0pfjN]

i hope i make sense, i mean that since when we set: tail = newNode, we are making tail pointer point to address allocated by the newNode, so can't we just delete newNode since it's address is stored by tail? I think i'm thinking overboard with this pointers stuff...

[4ET0pfjN]

what if I just enter:

node *newNode;
newNode->data = "hello";

w/o entering node *newNode = new node; since it still compiles or is just good programming practice...

[cire]

Because then you're writing to memory you don't own and Bad Things will happen. The address held by newNode could point anywhere.