stuck in linked list basics

[Reddevil1003]

here how head->next is getting address of tail.. nowhere we have specified head->next=tail or head->next=tmp;

i understand first call to add() head-> shows null but on second call how does it connects to node tails.

  #include <iostream>
#include<conio.h>

using namespace std;

struct node
{
    int a;
    node* next;
};

class linked_list
{
private:
    node* head; node* tail;
public:
    linked_list()
    {
        head=NULL;
        tail=NULL;
    }


    void add(int n)
    {
        node* tmp= new node;
        tmp->a=n;
        tmp->next=NULL;
        if(head==NULL)
            {
                head=tmp;
                tail=tmp;
            }
        else
            {
                tail->next=tmp;
                tail=tail->next;
            }
            cout<<head->a<<"\t\t"<<head->next<<endl;                // here how head->next is getting address of  tail.. nowhere we have specified head->next=tail or head->next=tmp;
            getch();
    }

    void display()
    {
        node *tmp;
        tmp=head;
        while(tmp!=NULL)
        {
            cout<<tmp->a<<endl;
            tmp=tmp->next;
        }
    }



};











int main()
{
    linked_list a;
    a.add(10);
    a.add(20);
    a.display();
    return 0;
}

[salem c]

> here how head->next is getting address of tail..
> nowhere we have specified head->next=tail or head->next=tmp;
Try adding a 3rd node.

With only two nodes, head points to the first one, and tail points to the second one, which is also the last one, which is also the one immediately after the head.

[coder777]

The reason is that you first set head and tail to the same thing (line 19/20). The second add() modifies the node both are pointing to.

[seeplus]

Don't use NULL - use nullptr instead for C++.

#include <iostream>
//#include <conio.h>

using namespace std;

struct node
{
	int a {};
	node* next {};
	node(int aa) : a(aa) {}
};

class linked_list
{
private:
	node* head {};
	node* tail {};

public:
	linked_list() {}

	~linked_list() {
		while (head != nullptr) {
			const auto current {head};

			head = head->next;

			delete current;
		}
	}

	void add(int n) {
		const auto tmp {new node {n}};

		if (head == nullptr)
			head = tail = tmp;
		else
			tail = tail->next = tmp;

		//cout << head->a << "\t\t" << head->next << endl;                // here how head->next is getting address of  tail.. nowhere we have specified head->next=tail or head->next=tmp;
		//getch();
	}

	void display() {
		for (auto tmp = head; tmp != nullptr; tmp = tmp->next)
			cout << tmp->a << '\n';
	}
};

int main()
{
	linked_list la;

	la.add(10);
	la.add(20);
	la.add(30);
	la.display();
	return 0;
}

[Handy Andy]

Hello Reddevil1003,

Sorry this took awhile. I am a bit rusty with linked lists.

I offer this not as the best way, but as a guide to compare your original code against to see what you are doing wrong.

#include <iostream>
//#include <limits>  // <--- May be needed for the "cin.ignore()".

using namespace std;  // <--- Best not to use.

struct node
{
    int num{};
    node* next{ nullptr };
};

class linked_list
{
    private:  // <--- Not required as this section is private by default. OK if you leave.
        node* head;
        node* tail;
        node* current;

    public:
        linked_list() : head(nullptr), tail(nullptr), current(nullptr) {}  // <--- Either one works.
        //linked_list()
        //{
        //    head = nullptr;
        //    tail = nullptr;
        //    current = nullptr;
        //}

        ~linked_list()  // <--- Overloaded dtor to free memory created by "new". The "delete" is a must have.
        {
            for (node* temp = head; temp->next != nullptr;)
            {
                current = temp->next;

                delete temp;

                temp = current;
            }
        }

        void add(int number)
        {
            if (head == nullptr)
            {
                head = new node;

                tail = new node;
                
                head->num = number;

                head->next = tail;

                //std::cout << '\n'; // <--- Used as a break point for testing. Comment or remove when finished.
            }
            else
            {
                current = tail;

                current->next = new node;

                current->num = number;

                tail = current->next;

                //std::cout << '\n'; // <--- Used as a break point for testing. Comment or remove when finished.
            }

            // <--- The following lines are useful for testing, but not compleetly necessary for a normal run.

            //cout << current->num << "\t\t" << current->next << '\n';  // here how head->next is getting address of  tail.. nowhere we have specified head->next=tail or head->next=tmp;

            //// A fair C++ replacement for "system("pause")". Or a way to pause the program.
            //// The next line may not be needed. If you have to press enter to see the prompt it is not needed.
            ////std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');  // <--- Requires header file <limits>.
            //std::cout << "\n Press Enter to continue: ";
            //std::cin.get();
        }

    void display()
    {
         current = head;

        while (current->next != nullptr)
        {
            cout << current->num << '\n';
            current = current->next;
        }
    }
};

int main()
{
    linked_list nums;

    //nums.add(10);

    //nums.add(20);

    for (int num = 0; num < 10; num++)
    {
        nums.add(num + 1);
    }

    std::cout << "\n Your list contains:\n";

    nums.display();

    // A fair C++ replacement for "system("pause")". Or a way to pause the program.
    // The next line may not be needed. If you have to press enter to see the prompt it is not needed.
    //std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');  // <--- Requires header file <limits>.
    std::cout << "\n\n Press Enter to continue: ";
    std::cin.get();

    return 0;
}

The for loop in "main" I did for testing. You do not have to keep it.

"conio.h" may be nice for "getch()", but not everyone has this header file available.

salem c once wrote:

#include<conio.h>
Obsolete since 1990, when the world stopped using DOS as a primary operating system.

The code at lines 71 - 75 and again at the bottom of main I came up with to replace the "getch()" function. I mostly use the code at the end of "main" during debugging and comment it out when I am done with it. It can also be a good place for a break point during debugging.

Andy

[seeplus]

@Andy. Add for an empty list is not usual as you are creating two new nodes - one for head which holds the data and one for tail which has no data - when only one node needs to be created to which both head & tail point. So there's a problem with the destructor. As you are having an extra node for the tail, the destructor doesn't delete that.

[Handy Andy]

@seeplus,

Thanks for the input. I know the idea of the dtor is correct, but I was not sure if I did it correctly. First time I tried something like that.

Also add is incorrect when there are no nodes. You are creating two new nodes - one for head and one for tail - when only one node should be created to which both head & tail point.

I think I see your point here. I will have to ponder it a bit.

It has been a few years since I dealt with linked lists in C so I am a bit rusty, but it is coming back.

Andy

[seeplus]

I think I see your point here. I will have to ponder it a bit.

See my previous code for a possible way.

[Reddevil1003]

thanks guys for the quick replies. i took me a while to figure this one out as i was confusing pointers for objects. so i made this simple code to understand

#include <iostream>

// linked list


using namespace std;


struct node                     
{
    int a {};                   
    node* next{};              
};

int main()
{
    node *h,*n,*t;      // we create three node pointers. h for iterating through all the nodes, n will point to new node, and t will connect the nodes by giving next pointer address of next node
    n = new node;
    n->a=10;
    h=t=n;             // all 3 pointers point to first node
    //-------------
    n = new node;      // n points to newly created node
    n->a=20;
    t->next=n;         // t gives address of this node to previously created node(as t is still pointing to previous node till this step) thus connecting the nodes.
    t=t->next;         // t now itself points to this node
    //----------------
    n = new node;
    n->a=30;
    t->next=n;
    t=t->next;
    //---------------
    n = new node;
    n->a=40;
    t->next=n;
    n->next=nullptr;

    for(auto tmp=h;tmp!=nullptr;tmp=tmp->next)   // here we use h to traverse through all the connecting nodes as h is still pointing to very first node.
    {
        cout<<tmp->a<<endl;
    }





    return 0;
}

and seeplus i dont get what this does ->node(int aa) : a(aa) {} and there is no code in constructor.

[seeplus]

node(int aa) : a(aa) {}

This is a class constructor that takes one argument of type int and sets the class variable a to that value. There's no code in the constructor body as it's not required as a is set in the initialisation list.
The other variables in the class are set to their values when they are defined.

It''s used with new when creating a new mode so that the created node has the data set.