Linked list written in c++

linked_list.cpp

#include <iostream>
#include <cstdlib>


class Node
{
public:
    Node* next;
    int data;
};

using namespace std;

class LinkedList
{
public:
    int length;
    Node* head;

    LinkedList();
    ~LinkedList();
    void add(int data);
    void print();
};

LinkedList::LinkedList(){
    this->length = 0;
    this->head = NULL;
}

LinkedList::~LinkedList(){
    std::cout << "LIST DELETED";
}

void LinkedList::add(int data){
    Node* node = new Node();
    node->data = data;
    node->next = this->head;
    this->head = node;
    this->length++;
}

void LinkedList::print(){
    Node* head = this->head;
    int i = 1;
    while(head){
        std::cout << i << ": " << head->data << std::endl;
        head = head->next;
        i++;
    }
}

int main(int argc, char const *argv[])
{
    LinkedList* list = new LinkedList();
    for (int i = 0; i < 100; ++i)
    {
        list->add(rand() % 100);
    }
    list->print();
    std::cout << "List Length: " << list->length << std::endl;
    delete list;
    return 0;
}

Very good your source code. I will help me to understand a bit more how works a list in C++

This is really useful, do you have any useful resources you could point me to that would help shed some light on linked lists some more? I'm just starting linked lists in my Data Structures course and would appreciate any help you could provide! Great source code.

Does your destructor have to loop through each node and delete it?

@SUSHSADA Yes, that leaves no data belonging to the list hanging around

Why you didn't implement in your destructor loop that delete all the nodes ? There is no memory problem in your currently implementation?

can you put some comments?

[email protected] This is my e-mail guys I need someone who can change ideas and try to develop coding skills with me. Please contact with me.

can you help me to develop a program to store soccer tournament full information like this

stop using old c++ and reimplement it again with cpp11… lol the code will not run

changing to the node class to struct would be nice

I think it would be better if the class was replaced with a struct as all the members of the class are public.

I compiled it using: g++ linked_list.cpp -o linked_list
Then run valgrind to check for memory leaks using: valgrind --leak-check=yes ./linked_list
and got:
...
==7352== LEAK SUMMARY:
==7352== definitely lost: 16 bytes in 1 blocks
==7352== indirectly lost: 1,584 bytes in 99 blocks
==7352== possibly lost: 0 bytes in 0 blocks
==7352== still reachable: 0 bytes in 0 blocks
==7352== suppressed: 0 bytes in 0 blocks
==7352==
...

Did I do something wrong? Because It seems to me that there are memory leaks, and none of the nodes where deleted.

such a good code in c++

The most beautiful code

@TheHolyJoker you did not do something wrong, this code leaks memory.
To fix it, we need to delete all the allocated nodes in the destructor.
Something like this:

LinkedList::~LinkedList() {
    Node* next = head;
    Node* cur = NULL;
    while (next != NULL) {
        cur = next;
        next = next->next;
        delete cur;
    }
}

How can we create linked list without classes

How can we create linked list without classes

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

Good information about the link list

Don't print your linkedList with print(). Add a friend operator<<.
Like so :

//declaration
friend ostream & operator<<(ostream & os, const LinkedList & l);

// implementation
ostream & operator<<(ostream & os, const LinkedList & l){
    Node* head = l.head;
    int i = 1;
    while(head->next){
        os << head->data << endl;
        head = head->next;
        i++;
    }
    return os;
}

Look at the while(head->next). Your implementation also prints the last element, which is NULL, so it prints rubbish.

Here is how to append data to the end of the list:

void LinkedList::append(int data)
{
    Node* node = this->head;

    while (node->next != NULL)
    {
        node = node->next;
    }

    node->next = new Node();
    node->next->data = data;
    node->next->next = NULL;
    this->length++;
}

However, the method gets quite slow when appending 100000+ items.
Anyone has an idea how to speed up the method?
How to avoid looping through the entire list just to find address of the end node?

herereeee...

Here is how to append data to the end of the list:

void LinkedList::append(int data)
{
    Node* node = this->head;

    while (node->next != NULL)
    {
        node = node->next;
    }

    node->next = new Node();
    node->next->data = data;
    node->next->next = NULL;
    this->length++;
}

However, the method gets quite slow when appending 100000+ items.
Anyone has an idea how to speed up the method?
How to avoid looping through the entire list just to find address of the end node?

Does this actually work on a newly created LinkedList object? The problem I am experiencing is that node will already be NULL such that trying to evaluate node->next in the while-loop condition will cause a segmentation fault.

I would suggest this modification such that it is also checked if the list is empty before appending a new node:

void LinkedList::append(int data) {
    Node* node = this->head;
    if (node == nullptr) {  // Check if list is empty
        node = new Node;
        this->head = node;
    } else {
        while (node->next != nullptr) {
            node = node->next;
        }
        node->next = new Node;
        node = node->next;
    }
    node->data = data;
    node->next = nullptr;
    this->length++;
}

Also regarding your other problem of avoiding to cycle through the whole list to append a new node, you could simply add a pointer to the end node and update it everytime you append a node. Similarly, in the code above the head pointer is updated every time a new node is prepended to the list.
Feel free to check out my implementation which is very similar to this one:
https://gist.github.com/Amadeeus/1c6dc6f5ea3d7b84bb979f7482b70342

thank you! Very useful

how do you create another list different from the already created using the same class

Can anyone explain me, if we create LinkedtList object then head (wiyh the help of default contructor ) will become null and data will be lost.

/*
I am getting error : In member function 'void linkedlist::add(std::string&)':
error: 'h' was not declared in this scope
can anyone explain me why i am getting this error message
*/
#include
#include
using namespace std;

//making class node
class node{ 
public:
friend class linkedlist;
node(){
    data = "0";
    next = NULL;
}
string data;
node* next;
};
//making class to linkedlist 
class linkedlist{

public:
linkedlist(){
    node* h = NULL;
}
//function to add data node in existing linked list
void add(string& str){
    node* newnode = new node;
    newnode->data = str;
    if(h !=NULL){
        h->next = newnode;
    }
    else{
        newnode->next = h->next;
        h->newnode;
    }
}
};

int main()
{
linkedlist l1;
string name;

//loop to enter data from user
while(true){
    cout<<"type \"q\" to exit or type name you want to add: ";
    cin>> name;
    if(name!="q"){
        l1.add(name);
    }
    else break;
}
return 0;
}