Linked List - some basic questions?

[Arslan7041]

Im just now starting to self-study linked lists. Please keep in mind that I am a complete novice as of now regarding this data structure.

I have some questions about the code below. I'd appreciate if someone could answer them.

I wrote it myself based on what little I've learned so far. It compiled fine but if you see something that could be improved, please let me know.

#include <iostream>
using namespace std;

// A simple struct for node
struct Node{

    int data;
    Node* next;

};

int main()
{
    // pointer to head node set to null for now;
    Node* A = 0;

    Node* temp;
    Node* temp1;

    // this loop is intended to create 5 Nodes with int data.
    for(int i = 1; i<=5; i++)
    {
        // if list is empty
        if(A == 0)
        {
            // create a node and fill with data
            temp = new Node;
            temp->data = i;
            temp->next = 0; // pointer set to null as its the last node

            A = temp; // A is now pointing to the frst node;
            cout << A->data << endl; // print out the integer in the first node.
        }

        else // if list is not empty
        {
            // create new node and fill with data;
            temp = new Node;
            temp->data = i;
            temp->next = 0; // point it to null, as this is now the final node.

            // travserse the list until you get to 'last' node
            temp1 = A;
            while(temp1->next != 0) // why cant we write "while(temp1 != 0)" for this?
            {
                temp1 = temp1->next; // temp1 itself is the thing being modified
                                    // so, again, why are we checking for temp1 -> next in the while condition

            }
            temp1->next = temp; // point the 'last' node to the next one.

            cout << temp1->data << endl; // print out the integer in the node.
        }
     }

    return 0;
}

My first question about the while conditions is in the comments of the code.

My second question is about my output, which was not what I expected:

1
1
2
3
4

I expected simply a listing of 1-5. But here 1 is printing out twice and I dont know why.

[booradley60]

In your "else" block, you're printing temp1->data. But temp1 is used to represent the second-to-last node in the list. The newest node in the list is represented by temp. So the first time through the loop you go into the "if" block and print your new node. Every other time you go into the "else" block, create a new node at the end of your list, and print whatever is in the second to last node. What if you change line 52 to cout << temp->data << endl;?

[Arslan7041]

That works! Thank you.

I will post something regarding the while condition in the next post...

[Arslan7041]

Okay, so a big thanks to booradley60 for helping me understand where I was going wrong.

I still have a question about the while condition for traversing the list though.

Here is the relevant snippet of the code:

while(temp1->next != 0) // why cant we write "while(temp1 != 0)" for this?
            {
                temp1 = temp1->next; // temp1 itself is the thing being modified
                                    // so, again, why are we checking for temp1 -> next in the while condition

            }

I tried changing the while(temp1->next != 0) to while(temp1 != 0) to see if it works, but my program crashed every time.

But im even more confused now, because I went back to my code and updated it. I added a Print function which traverses through the list and prints out each integer. Here it is below:

void print(Node* A)
{
    Node* temp = A;
    while(temp  != 0)
    {
        cout << temp->data << endl;
        temp = temp->next;
    }
}

Notice the while condition here: while(temp != 0) instead of while(temp->next != 0)

I ran the program with this function and it prints the integers 1-5 just fine. Why does this work here but it doesn't work on line 44 in the OP? After all, the two snippets of code are doing the exact same thing, that is, traversing through the list.

Am I missing something here?

[booradley60]

Yes. The key is what is the state of your pointer when you leave the while loop? In the first case:

while(temp1->next != 0)
{
    temp1 = temp1->next;
}

In this case, when the while loop exits, temp1 will be pointing at the last node in the list. This is important for the OP line 44 case because the first thing you do after that while loop is say temp1->next = temp; on line 50. temp1 better be pointing to a node object, or how will you assign its "next" member?

In the second case, you want to go all the way through the list and print everything, and you don't care about the state of the pointer afterward:

while(temp  != 0)
    {
        cout << temp->data << endl;
        temp = temp->next;
    }

When this loop completes, temp will be null. That's ok, you don't use that pointer once you finish the while loop.

Just to recap, the first while loop leaves you with a pointer that points to the last element in the list. The second while loop leaves you with a pointer that points to null ("past" the end of the list).

[Arslan7041]

Booradley60, thanks again, but I dont understand how that answers my question: Why does the first loop REQUIRE temp1->next != 0 while the second one works fine with temp != 0.

My confusion here is that both do the same exact thing (traverse through the list), yet they work with different conditions. I tried changing the first to look like the second, but my program crashes.

I hope you understand what Im asking here.

[booradley60]

This is where your mistake lies:

My confusion here is that both do the same exact thing (traverse through the list)

This statement incompletely captures what's going on with both. They traverse a list AND access the pointer traversing the list. The difference lies in the pointer access part.

You are using a loop to advance a pointer through a list. As long as that pointer points to a valid node, you can do something (i.e. you access the pointer to manipulate or examine the object it points to) with it. Take note of when you do something with the pointer.

In your first sample:

while(temp1->next != 0)
{
    temp1 = temp1->next;
}

//at this point, you've failed to satisfy the loop condition
//and that's why you've exited it.
//temp1->next points to null but temp1 still points to
//a valid node. The next line is your "do something" step, and
//it occurs after the loop.
temp1->next = temp;

In your second sample:

while(temp  != 0)
{
    //at this point, the loop condition has protected
    //you from getting here if temp is NULL. That is
    //important because this is where the
    //"do something" step is
    cout << temp->data << endl;
    temp = temp->next;
}

So the biggest difference between the two different operations is when you do an action to the pointer you're advancing.

The first operation accesses the pointer after the loop, so you must have a loop condition that leaves you with a valid pointer when the loop is over.

The second operation accesses the pointer inside the loop, so your loop condition can check for null to prevent accessing a null pointer.

[Arslan7041]

Ah, I see. Thats a subtle point, so thank you for making it clear for me.

Im still learning, so I'll probably be back with more Q's.

[Arslan7041]

Okay, so below is a code that inserts a node at at the beginning of a list, then prints out the updated list:

#include <iostream>
using namespace std;

// A simple struct for node
struct Node{

    int data;
    Node* next;

};

void print();
void Insert(int);

Node* head; // pointer to head (first node), global variable

int main()
{
    // pointer to head node set to null for now;
    head = 0;

    cout << "How many numbers? ";
    int n;
    cin >> n;

    int x;

    // this loop is intended to create n Nodes with int data.
    for(int i = 1; i<=n; i++)
    {
        cout << "\nEnter number: ";
        cin >> x;
        Insert(x);
        print();
    }

    return 0;
}

void Insert(int x)
{
    Node* temp = new Node;

    temp->data = x;
    temp->next = head;
    head = temp;
}

void print()
{
    Node* temp = head;
    cout << "The list is: ";
    while(temp != 0)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << "\n";
}

I need to know if Im understanding the Insert function correctly. Here is my break down of it:

When the list is initially empty, Insert is called and a new node is made. Line 45 makes it so that its pointer is pointing to null (because head initially is pointing to null). Head is then set to point to this new node by line 46.

So now we have head pointing to the first node, and first node pointing to null.

When the Insert function is called a second time, head will be pointing to the first node. Thus, when a new node is created, line 45 will makes its pointer point to wherever head is pointing to (and head, of course, is pointing to the first node. Thus, this newly created node is pointing to the first node). Once this link is established, line 46 makes head point to the newly created node, making it the new first node.

This can continue for any number of nodes.

Am I understanding this correctly?

The basic crux of the function is that when a pointer is assigned to another pointer, they end up pointing to the same thing.

[Arslan7041]

My code below is not working.

When I declare pToHead as a global variable, its works fine. But when I declare it within main and pass it to other functions, the list does not print any numbers. I think I may be passing the pointer incorrectly. Can anyone tell me what exactly is wrong with my code?

#include <iostream>
using namespace std;

// A simple struct for node
struct Node{

    int data;
    Node* next;

};

void print(Node*);
void Insert_Beginning(Node*, int);

int main()
{
    Node* pToHead;
    pToHead = 0; // pointer to head node set to null for now;

    cout << "How many numbers? ";
    int n;
    cin >> n;

    int x;

    // this loop is intended to create n Nodes with int data.
    for(int i = 1; i<=n; i++)
    {
        cout << "\nEnter number: ";
        cin >> x;
        Insert_Beginning(pToHead, x);
        print(pToHead);
    }

    return 0;
}

void Insert_Beginning(Node* pToHead, int x)
{
    Node* temp = new Node;

    temp->data = x;
    temp->next = pToHead;
    pToHead = temp;
}

void print(Node* pToHead)
{
    Node* temp = pToHead;
    cout << "The list is: ";
    while(temp != 0)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << "\n";
}

[Arslan7041]

Never mind, figured out what I was doing wrong. I was passing the pToHead by value, when I should have been passing it by reference.

[dhayden]

You're making very good progress understanding linked lists. Congratulations.

A few things to consider doing:

Use a for loop to go through the list. This way you separate the "loopiness" code from the "what to do for each node" code. For example, to print the list:

void print(Node* pToHead)
{
    cout << "The list is: ";
    // This line contains all the code to walk through the list
    for (Node * tmp = pToHead; temp != 0; temp = temp->next)
    {
        // This line contains the code that shows what you do with each node.
        cout << temp->data << " ";
    }
    cout << "\n";
}

Your first post showed inserting at the end of the list by walking through the list. I realize that you were doing this for your own education, but I want to point out that this is very inefficient. For example, consider what would happen if you had to insert 100,000 items in a list. To insert the 90,000th item, you'd walk thorugh 89,999 items to find the last one. Then to insert the 90,001th item, you'd walk through 90,000 items, etc. Thus insertions would become very slow.

So singly linked lists are good when inserting at the FRONT of the list. If you need to insert at the end of the list, you should keep a separate tail pointer. std::list does this.

[Arslan7041]

Thank you dhayden for your encouragement. I've implemented the for-loop for printing and it works beautifully, so thank you for that as well.

Now moving on.

Im having a bit of trouble with a new function im trying to make called Insert_At_n, which simply inserts a newly created node at the nth position (with first node being n=1).

I tried running the program with it but it ends up crashing. I've gone through the code several times but cannot seem to find where I've gone wrong with my logic. Here it is below, comments included:

// insert int data at position n
void Insert_At_n(Node* &pToHead, int data, int n)
{
    Node* temp = new Node;
    Node* temp1;

    temp->data = data;
    if(n == 1)
    {
        temp->next = pToHead; // set link field of new node to whatever pToHead was linked to
        pToHead = temp // point pToHead to new node
        return;
    }

    temp1 = pToHead; // set to first node
    for(int i=0; i<n-2; n++) // go to n-1th node
    {
        temp1 = temp1->next;
    }

    temp->next = temp1->next; // set link field of new node to whatever n-1th node was pointing to
    temp1->next = temp; // link n-1th node to new node
}

The functions calls in main look like this:

    Insert_At_n(pToHead, -100, 2);
    Insert_At_n(pToHead, 100, 3);

Can someone please look through the code here and let me know where im going wrong? Thank you.

[cire]

I tried running the program with it but it ends up crashing.

As presented, this won't compile. It's missing a semi-colon on line 11. It's helpful to supply the code you're using that reproduces the problem.

That said, you're not making any effort to ensure there are n-1 elements in the list. Do you do so before the call to Insert_At_n?

Untested:

void Insert_At_n(Node* &pToHead, int data, int n)
{
    if (n <= 0)
    {
        std::cerr << "Insert_At_n called with invalid parameter: n <= 0\n";
        return;
    }

    if (n == 1)
    {
        Node * node = new Node{ data, pToHead };
        pToHead = node;
        return;
    }

    Node* insert_after = pToHead;

    for (unsigned i = 1; i < n-1 && insert_after; ++i)
        insert_after = insert_after->next;

    if (!insert_after)
    {
        std::cerr << "Insert_At_n called with invalid parameter: n == " << n << '\n';
        return;
    }

    Node* node = new Node{ data, insert_after->next };
    insert_after->next = node;
}

[dhayden]

There's actually a much easier way to do this in C++. I think they don't teach this is books because it requires the ability to take the address of a variable and some languages don't allow that.

The trick is that rather than using a pointer to the previous node in the list, you use a pointer to the pointer to the node. So this pointer either points to the head, or it points to the "next" pointer in a node. Here is code to insert at the n'th position, or at the end if n is too big. Note that n starts at 0 in this code. I strongly recommend that you use this convention since arrays use it.

#include <iostream>

using namespace std;

// A simple struct for node
struct Node{
    int data;
    Node* next;
};


void insertAtN(Node * &head, int data, int n)
{
    Node **headOrNext;
    Node *p;

    for (headOrNext = &head; p = *headOrNext; headOrNext = &p->next) {
        if (--n < 0) break;
    }

    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = *headOrNext;
    *headOrNext = newNode;
}

void print(Node* head)
{
    cout << "The list is: ";
    for (Node * p = head; p != 0; p = p->next) {
        cout << p->data << ' ';
    }
    cout << '\n';
}

int main(){
    Node *head = 0;

    insertAtN(head, 2, 0);      // list is 2
    insertAtN(head, 1, 0);      // list is 1 2
    insertAtN(head, 3, 1);      // list is 1 3 2
    insertAtN(head, 4, 3);      // list is 1 3 2 4
    print(head);
}

[Arslan7041]

@cire, I must have deleted the semicolon by accident when adding in the comments. Anyway, I've added the semicolon back. But the problem is still the same, the program crashed when running.

I think I understand what you are doing in your code, but I'd still like to know why my own code is not working.

@dhayden. Im actually unsure of what you are doing in your code. Seems like an interesting approach, but I'll have to take a look at it later when I have more time.

For now, an explanation of why my own code crashes would be appreciated. Keep in mind that I call the InsertAtN function after inserting a few nodes via the Insert_Beginning function. After this, the insertAtN function is called with valid n values, but it still crashes.

[Arslan7041]

UPDATE: So I've done some testing with my code. I inserted 5 nodes via the Insert_Beginning function. Then I called the InsertAtN function with different values of n. I found that the code works for n=1 and n=2, but crashed for any other valid values of n.

So Im guessting there is something wrong with my for-loop?

[cire]

Arslan7041 wrote:

I think I understand what you are doing in your code, but I'd still like to know why my own code is not working.

for (int i = 0; i<n - 2; n++) // go to n-1th node

If you'd taken the hint and instrumented your code to check for failure points as I did mine, you probably would've realized that you're updating the wrong variable here. Note that the loop doesn't execute at all for values where n <=2.

[Arslan7041]

Sorry for the late reply. Been busy with work.

Thank you cire, I've fixed the loop.

Also, the loop is only meant to handle cases where n>2. The case for n=1 and n=2 is already taken care of outside the loop. Note that my linked list index begins at 1, not 0.

My code works perfectly now. I'll be writing more functions so I'll probably be back if I run into more trouble.

Thank you all for your help.

[Arslan7041]

So I've added a Delete_At_n function which takes the head pointer and an index n, and deletes the node at index n. Once again, my index starts at 1, not 0.

The function seems to work fine.

Here is the full code below. Please take a look especially at the Delete_At_n function and suggest any improvements:

#include <iostream>
using namespace std;

// A simple struct for node
struct Node{

    int data;
    Node* next;

};

void print(Node* &);
void Insert_Beginning(Node* &, int);
void Insert_End(Node* &, int);
void Insert_At_n(Node* &, int, int);
void Delete_At_n(Node* &, int);

int main()
{
    Node* pToHead;
    pToHead = 0; // pointer to head node set to null for now;

    cout << "How many numbers? ";
    int n;
    cin >> n;

    int x;

    // this loop is intended to create 2n Nodes with int data.
    for(int i = 1; i<=n; i++)
    {
        cout << "\nEnter number: ";
        cin >> x;
        Insert_Beginning(pToHead, x);
        //Insert_End(pToHead, x);
        print(pToHead);
    }

    Insert_At_n(pToHead, 100, 1);
    print(pToHead);
    Insert_At_n(pToHead, 200, 2);
    print(pToHead);
    Insert_At_n(pToHead, 300, 3);
    print(pToHead);
    Insert_At_n(pToHead, 800, 2);
    print(pToHead);

    Delete_At_n(pToHead, 2);
    print(pToHead);
    Delete_At_n(pToHead, 4);
    print(pToHead);
    Delete_At_n(pToHead, 1);
    print(pToHead);


    return 0;
}

void Insert_Beginning(Node* &pToHead, int x)
{
    Node* temp = new Node;

    temp->data = x;
    temp->next = pToHead;
    pToHead = temp;
}

void Insert_End(Node* &pToHead, int x)
{
    Node* temp = new Node;
    Node* temp1;

    temp->next = 0;
    temp->data = x;

   if(pToHead == 0)
    pToHead = temp;

    else
    {
        temp1 = pToHead;
            while(temp1->next != 0)
            {
                temp1 = temp1->next;
            }

        temp1->next = temp;
    }



}

// insert int data at position n
void Insert_At_n(Node* &pToHead, int data, int n)
{
    Node* temp = new Node;
    Node* temp1;

    temp->data = data;
    temp->next = 0;
    if(n == 1)
    {
        temp->next = pToHead; // set link field of new node to whatever pToHead was linked to
        pToHead = temp; // point pToHead to new node
        return;
    }

    temp1 = pToHead;
    for(int i=0; i<n-2; i++) // go to n-1th nodel
    {
        temp1 = temp1->next;
    }

    temp->next = temp1->next; // set link field of new node to whatever n-1th node was pointing to
    temp1->next = temp; // link n-1th node to new node
}

void Delete_At_n(Node* &pToHead, int n)
{
    if(pToHead == 0)
        return;

    Node* temp = pToHead;

    if(n==1) // special case for deleting first node;
    {
        pToHead = temp->next; // point pToHead to wherever first node was linked to
        return;
    }

    for(int i=0; i<n-2; i++)   // go to n-1th node
    {
        temp = temp->next;
    }

    temp->next = temp->next->next; // point n-1th node to whatever nth node is pointing to
    return;
}

void print(Node* &pToHead)
{
    cout << "The list is: ";
    for(Node* temp = pToHead; temp != 0; temp = temp->next)
        cout << temp->data << " ";

    cout << "\n";
}

Notice that I decided to forgo the option of creating a temp2 variable, and instead moved up 2 nodes by writing temp->next->next. I figured its better this way.

Next I'll try to do an exercise on reversing the list.