C++ Link List, finding the length of the list.

[Sebastian Kurpiel]

What's up guys,

I'm running into trouble when trying to run my length_list code, I've been told that I'm close but not sure where the problem is.

int Llist::length_list()
{
    int count = 1;
    Node* temp = Head;
    while (temp != NULL)
    {
        count++;
        temp = temp->link;
    }
    return count;
}

 

The rest of the code:

#include <iostream>

class Node
{

public:
    int data;
    Node * link;
};

class Llist
{
private:
    Node *Head, *Tail;
public:
    Llist();
    void Append(Node * NewNode);
    void Insert_at_Pos(Node * NewNode, int position);
    void DeleteNode(int position);
    void show_nodes();
    Node * search_for_node(int data);
    int length_list();
};

using namespace std;

Llist::Llist()
{
    Head = NULL;
}

void Llist::Append(Node * NewNode)
{
    if (Head == NULL)
    {
        Head = NewNode;
        Tail = NewNode;
    }
    else
    {
        Tail->link = NewNode;
        Tail = NewNode;
    }
}

void Llist::Insert_at_Pos(Node * NewNode, int position)
{
    Node *temp = Head;
    if (position == 1) //we will insert at the first position
    {
        NewNode->link = temp;
        Head = NewNode; //update the head
    }
    else
    {
        int count = 1, flag = 1;
        while (count != position - 1)
        {
            temp = temp->link;
            if (temp == NULL) { flag = 0; break; }
            count++;
        }
        if (flag == 1)
        {
            NewNode->link = temp->link;
            temp->link = NewNode;
        }
        else
            cout << "Position not found.\n";
    }
}

void Llist::DeleteNode(int position)
{
    Node *temp = Head;
    if (position == 1) //we will delete the first node
    {
        Head = temp->link;
        delete temp; //delete the node
    }
    else
    {
        int count = 1, flag = 1;
        Node *curr;
        while (count != position - 1)
        {
            temp = temp->link;
            if (temp == NULL) { flag = 0; break; }
            count++;
        }
        if (flag == 1)
        {
            curr = temp->link;
            temp->link = curr->link;
            delete curr;
        }
        else
            cout << "Position not found.\n";
    }
}

void Llist::show_nodes()
{
    int i = 1;
    Node * temp;
    temp = Head;
    cout << i << "\t" << temp->data << "\n";
    i++;
    while (temp->link != NULL)
    {
        temp = temp->link;
        cout << i << "\t" << temp->data << "\n";
        i++;
    }
}

/******************* Week 6, Exercise 1 *******************/
Node * Llist::search_for_node(int data)
{
    //make sure if you can't find the value print a statement that says so
    return NULL;
}

int Llist::length_list()
{
    int count = 1;
    Node* temp = Head;
    while (temp != NULL)
    {
        count++;
        temp = temp->link;
    }
    return count;
}

/******************* Week 6, Exercise 1 *******************/

int main()
{
    Llist x;
    
    Node *a = new Node{};
    x.Append(a);
    a->data = 10;
    a->link = nullptr;
    
    Node *b = new Node{};
    x.Append(b);
    b->data = 5;
    b->link = nullptr;

    Node *c = new Node{};
    c->data = 1;
    c - -> link = nullptr;
    x.Insert_at_Pos(c, 2);

    x.show_nodes();

    x.length_list(x);
    cout << "Length of Llist x is:" << count << endl;

    //create the linked list, called x
    //create a node to add to list, with data 10, link will be NULL, then append it
    //create a node to add to list, with data 5, link will be NULL, then append it
    //call show_nodes() function
    //create a node to add to list at 2nd position, data is 1 and link is NULL
    //call show_nodes() function
    //test the length_list function, print out should look like example output
    //test search_for_node function, search for 1, print if you found it like example output
    //delete a node at position 2, call show_nodes(), then test the length_list function again
    //test search_for_node function, look for 1, Should not find it; it is looking for the deleted node
    return 0;
}

[BlueChinchillaEatingDorito]

Count should start at 0 rather than 1. If you have NULL as the head, you'll have a list size of 1 which doesn't make sense.

[Sebastian Kurpiel]

Just now, BlueChinchillaEatingDorito said:

Count should start at 0 rather than 1. If you have NULL as the head, you'll have a list size of 1 which doesn't make sense.

 

After making that change I get these errors

[Mr_KoKa]

    c - -> link = nullptr; // shoudl be -> not - ->
    x.Insert_at_Pos(c, 2);

    x.show_nodes();

    x.length_list(x); //length_list doesnt take arguments, and it returns count
    cout << "Length of Llist x is:" << count << endl; // count variable is not defined the above line should be something like int count = x.length_list();

I commented all that is wrong with the code.

[Sebastian Kurpiel]

@Mr_KoKa my c++ savior, thanks for the help and @BlueChinchillaEatingDorito, awesome name, thanks for the help.

So I wrote my search_for_node part and I ran into the error where it says "Tail" is not declared in class node... 

the snippet of code

Node * Llist::search_for_node(int data)
{
    Node* temp = Head;
    while (temp != NULL){
        if (temp->data == data)
        {
            return temp;
        }
        else
        {
            cout << "Can't find value in any of the nodes." << endl;
        }
}
    temp = temp->Tail;
    //make sure if you can't find the value print a statement that says so
    return NULL;
}

[Mr_KoKa]

I haven't check if your searching algorithm is alright but what is wrong for sure:

temp = temp->Tail;

Notice that temp is Node, and nodes have no Tail, you probably meant

temp = this->Tail;

_{Edit: Now I know that the above wasn't what you wanted to do.}

 

Is that function not finished? I don't see sense to assigning list's tail to temp, because it is left unused.

You're also not progressing in your loop, you keep comparing same temp node's data with data. You probably should do temp = temp->link at the end of the loop, and that is probably what you wanted to do with that temp->Tali, but it is not even inside loop, brace closing loop body is just before.

 

Edit: Also that else inside loop is unnecessary, as it will say that there is no such data every node it doesn't match.

[Sebastian Kurpiel]

1 minute ago, Mr_KoKa said:

I haven't check if your searching algorithm is alright but what is wrong for sure:

temp = temp->Tail;

Notice that temp is Node, and nodes have no Tail, you probably meant

temp = this->Tail;

_{Edit: Now I know that the above wasn't what you wanted to do.}

 

Is that function not finished? I don't see sense to assigning list's tail to temp, because it is left unused.

You're also not progressing in your loop, you keep comparing same temp node's data with data. You probably should do temp = temp->link at the end of the loop, and that is probably what you wanted to do with that temp->Tali, but it is not even inside loop, brace closing loop body is just before.

 

Edit: Also that else inside loop is unnecessary, as it will say that there is no such data every node it doesn't match.

 

That was the fix, thanks again my friend.

[trag1c]

Assuming you created a contiguous block of memory and that each member of the list is the same size (I didnt go through the code as I am at work) you could simply divide the offset from the beginning to the end by the size of a single element.

 

 

[Mr_KoKa]

1 hour ago, trag1c said:

Assuming you created a contiguous block of memory and that each member of the list is the same size (I didnt go through the code as I am at work) you could simply divide the offset from the beginning to the end by the size of a single element.

 

 

It is linked list, each element of the list is allocated separately. And each element points at next or/and previous.

[Sebastian Kurpiel]

Just now, Mr_KoKa said:

It is linked list, each element of the list is allocated separately. And each element points at next or/and previous.

Would the same code for work for a double link list?

[Mr_KoKa]

Just now, Sebastian Kurpiel said:

Would the same code for work for a double link list?

Not 100% but it would be very similar. Now your node has link and it points to next element, for double linked list you would probably need to change link to next and add prev pointer to point at previous. It's easy to apply those changes, but your functions right now wouldn't take any advantage of having both directions.

[Sebastian Kurpiel]

42 minutes ago, Mr_KoKa said:

Not 100% but it would be very similar. Now your node has link and it points to next element, for double linked list you would probably need to change link to next and add prev pointer to point at previous. It's easy to apply those changes, but your functions right now wouldn't take any advantage of having both directions.

 

 

Could you explain the prev pointer, would it be prev-> previous?

snippet 

DLL_Node * DList::search_for_node(int data)
{
    DLL_Node* temp = Head;
    while (temp != NULL) {
        if (temp->data == data)
        {
            cout << "Match found!" << endl;
            return temp;
        }
        temp = temp->next;
        *prev -> previous
    }
    cout << "No match found for the data..." << endl;
    return NULL;
}

int DList::length_list()
{
    int count = 0;
    DLL_Node* temp = Head;
    while (temp != NULL)
    {
        count++;
        temp = temp->next;
    }
    return count;

#include <iostream>

class DLL_Node
{
public:
    int data;
    DLL_Node *prev, *next;
    DLL_Node() { prev = next = NULL; }
};

class DList
{
private:
    DLL_Node *Head, *Tail;
public:
    DList() { Head = Tail = NULL; }
    void Append(DLL_Node *NewNode);
    DLL_Node* GetNode();
    void Create();
    void Traverse();
    void Delete_Pos(int pos);
    void Insert_Pos(DLL_Node * NewNode, int pos);
    DLL_Node * search_for_node(int data);
    int length_list();

};

using namespace std;

void DList::Append(DLL_Node *NewNode)
{
    if (Head == NULL)
    {
        Head = NewNode;
        Tail = NewNode;
    }
    else
    {
        Tail->next = NewNode; //add to end
        NewNode->prev = Tail;
        Tail = NewNode;
    }
}

DLL_Node* DList::GetNode()
{
    DLL_Node *NewNode;
    NewNode = new DLL_Node;
    cout << "Enter data ";
    cin >> NewNode->data;
    NewNode->next = NewNode->prev = NULL;
    return NewNode;
}

void DList::Create()
{
    char ans;
    DLL_Node *NewNode;
    while (1)
    {
        cout << "Any more nodes to add (Y/N)? ";
        cin >> ans;
        if ((ans == 'n') || (ans == 'N'))
            break;
        NewNode = GetNode();
        Append(NewNode);
    }
}

void DList::Traverse()
{
    DLL_Node *Curr;
    Curr = Head;
    if (Curr == NULL) cout << "List is empty\n";
    else
    {
        while (Curr != NULL)
        {
            cout << Curr->data << "\t";
            Curr = Curr->next;
        }
    }
}

void DList::Delete_Pos(int pos)
{
    int count = 1;
    DLL_Node *temp = Head;
    if (pos == 1)
    {
        Head = Head->next;
        Head->prev = NULL;
        delete temp;
    }
    else
    {
        while (count != pos)
        {
            temp = temp->next;
            if (temp != NULL)
                count++;
            else
                break;
        }
        if (count == pos)
        {
            if (temp == Tail)
            {
                Tail = temp->prev;
                (temp->prev)->next = NULL;
                delete temp;
            }
            else
            {
                (temp->prev)->next = temp->next;
                (temp->next)->prev = temp->prev;
                delete temp;
            }
        }
        else cout << "The node to be deleted is not found." << endl;
    }
}

void DList::Insert_Pos(DLL_Node * NewNode, int pos)
{
    DLL_Node *temp = Head;
    int count = 1;

    if (Head == NULL)
        Head = Tail = NewNode;
    else if (pos == 1) //the node will be new head
    {
        NewNode->next = Head;
        Head->prev = NewNode;
        Head = NewNode;
    }
    else
    {
        while (count != pos) //increment to position
        {
            temp = temp->next;
            if (temp != NULL)
                count++;
            else
                break;
        }
        if (count == pos)
        {
            (temp->prev)->next = NewNode;
            NewNode->prev = temp->prev;
            NewNode->next = temp; //wasn't in book
            temp->prev = NewNode;
        }
        else
            cout << "The node position is not found" << endl;
    }
}

/******************* Week 6, Exercise 2 *******************/
DLL_Node * DList::search_for_node(int data)
{
    DLL_Node* temp = Head;
    while (temp != NULL) {
        if (temp->data == data)
        {
            cout << "Match found!" << endl;
            return temp;
        }
        temp = temp->next;
        *prev -> previous
    }
    cout << "No match found for the data..." << endl;
    return NULL;
}

int DList::length_list()
{
    int count = 0;
    DLL_Node* temp = Head;
    while (temp != NULL)
    {
        count++;
        temp = temp->next;
    }
    return count;
}
/******************* Week 6, Exercise 2 *******************/

int main()
{
    DList x;
    
    x.Create();
    
    x.Traverse();

    DLL_Node *memes = new DLL_Node{};
    memes->data = 10;
    
    x.Insert_Pos(memes, 2);

    x.Traverse();

    //Create a DList object called x
    //Call Create() function
    //When Create() function is called create Nodes with data being: 12,56,98,33,65
    //Call Traverse() function
    //Create a DLL_Node with data being 10
    //Insert said not at 2nd postion by calling Insert_Pos function
    //Call Traverse() function
    return 0;
}

 

[Mr_KoKa]

Quick explanation would be

//Linked list node
struct Node {
	int data;
	Node *link;
}

//Double linked list node
struct Node {
	int data
	Node *next;
	Node *prev;
}

First node on the list would have prev set to null, and last node (as on single linked list) would have next set to null.

[Nineshadow]

Or you could keep a member field to keep track of the length. You increment it when you add a node and so on.

[mathijs727]

17 hours ago, Nineshadow said:

Or you could keep a member field to keep track of the length. You increment it when you add a node and so on.

Easier and faster (O(1) vs O(N)).