[c++] Simple linked list in C++

I am about to create a linked that can insert and display until now:

struct Node {
    int x;
    Node *next;
};

This is my initialisation function which only will be called for the first Node:

void initNode(struct Node *head, int n){
    head->x = n;
    head->next = NULL;
}

To add the Node, and I think the reason why my linked list isn't working correct is in this function:

void addNode(struct Node *head, int n){
    struct Node *NewNode = new Node;
    NewNode-> x = n;
    NewNode -> next = head;
    head = NewNode;
}

My main function:

int _tmain(int argc, _TCHAR* argv[])
{
    struct Node *head = new Node;

    initNode(head, 5);
    addNode(head, 10);
    addNode(head, 20);
    return 0;
}

Let me run the program as I think it works. First I initialise the head Node as a Node like this:

head = [ 5 |  NULL ]

Then I add a new node with n = 10 and pass head as my argument.

NewNode = [ x | next ] where next points at head. And then I change the place where head is pointing to NewNode, since NewNode is the first Node in LinkedList now.

Why isn't this working? I would appreciate any hints that could make me move in the right direction. I think LinkedList is a bit hard to understand.

When I'm printing this, it only returns 5:

This question is related to c++ linked-list

The answer is


Both functions are wrong. First of all function initNode has a confusing name. It should be named as for example initList and should not do the task of addNode. That is, it should not add a value to the list.

In fact, there is not any sense in function initNode, because the initialization of the list can be done when the head is defined:

Node *head = nullptr;

or

Node *head = NULL;

So you can exclude function initNode from your design of the list.

Also in your code there is no need to specify the elaborated type name for the structure Node that is to specify keyword struct before name Node.

Function addNode shall change the original value of head. In your function realization you change only the copy of head passed as argument to the function.

The function could look as:

void addNode(Node **head, int n)
{
    Node *NewNode = new Node {n, *head};
    *head = NewNode;
}

Or if your compiler does not support the new syntax of initialization then you could write

void addNode(Node **head, int n)
{
    Node *NewNode = new Node;
    NewNode->x = n;
    NewNode->next = *head;
    *head = NewNode;
}

Or instead of using a pointer to pointer you could use a reference to pointer to Node. For example,

void addNode(Node * &head, int n)
{
    Node *NewNode = new Node {n, head};
    head = NewNode;
}

Or you could return an updated head from the function:

Node * addNode(Node *head, int n)
{
    Node *NewNode = new Node {n, head};
    head = NewNode;
    return head;
}

And in main write:

head = addNode(head, 5);

head is defined inside the main as follows.

struct Node *head = new Node;

But you are changing the head in addNode() and initNode() functions only. The changes are not reflected back on the main.

Make the declaration of the head as global and do not pass it to functions.

The functions should be as follows.

void initNode(int n){
    head->x = n;
    head->next = NULL;
}

void addNode(int n){
    struct Node *NewNode = new Node;
    NewNode-> x = n;
    NewNode->next = head;
    head = NewNode;
}

In a code there is a mistake:

void deleteNode ()
{
    for (Node * temp = head; temp! = NULL; temp = temp-> next)
        delete head;
}

It is necessary so:

for (; head != NULL; )
{
    Node *temp = head;
    head = temp->next;

    delete temp;
}

I'll join the fray. It's been too long since I've written C. Besides, there's no complete examples here anyway. The OP's code is basically C, so I went ahead and made it work with GCC.

The problems were covered before; the next pointer wasn't being advanced. That was the crux of the issue.

I also took the opportunity to make a suggested edit; instead of having two funcitons to malloc, I put it in initNode() and then used initNode() to malloc both (malloc is "the C new" if you will). I changed initNode() to return a pointer.

#include <stdlib.h>
#include <stdio.h>

// required to be declared before self-referential definition
struct Node;

struct Node {
    int x;
    struct Node *next;
};

struct Node* initNode( int n){
    struct Node *head = malloc(sizeof(struct Node));
    head->x = n;
    head->next = NULL;
    return head;
}

void addNode(struct Node **head, int n){
 struct Node *NewNode = initNode( n );
 NewNode -> next = *head;
 *head = NewNode;
}

int main(int argc, char* argv[])
{
    struct Node* head = initNode(5);
    addNode(&head,10);
    addNode(&head,20);
    struct Node* cur  = head;
    do {
        printf("Node @ %p : %i\n",(void*)cur, cur->x );
    } while ( ( cur = cur->next ) != NULL );

}

compilation: gcc -o ll ll.c

output:

Node @ 0x9e0050 : 20
Node @ 0x9e0030 : 10
Node @ 0x9e0010 : 5

Below is a sample linkedlist

    #include <string>
    #include <iostream>

    using namespace std;


    template<class T>
    class Node
    {
    public:
        Node();
        Node(const T& item, Node<T>* ptrnext = NULL);
        T value;
        Node<T> * next;
    };

    template<class T>
    Node<T>::Node()
    {
        value = NULL;
        next = NULL;
    }
    template<class T>
    Node<T>::Node(const T& item, Node<T>* ptrnext = NULL)
    {
        this->value = item;
        this->next = ptrnext;
    }

    template<class T>
    class LinkedListClass
    {
    private:
        Node<T> * Front;
        Node<T> * Rear;
        int Count;
    public:
        LinkedListClass();
        ~LinkedListClass();
        void InsertFront(const T Item);
        void InsertRear(const T Item);
        void PrintList();
    };
    template<class T>
    LinkedListClass<T>::LinkedListClass()
    {
        Front = NULL;
        Rear = NULL;
    }

    template<class T>
    void LinkedListClass<T>::InsertFront(const T  Item)
    {
        if (Front == NULL)
        {
            Front = new Node<T>();
            Front->value = Item;
            Front->next = NULL;
            Rear = new Node<T>();
            Rear = Front;
        }
        else
        {
            Node<T> * newNode = new Node<T>();
            newNode->value = Item;
            newNode->next = Front;
            Front = newNode;
        }
    }

    template<class T>
    void LinkedListClass<T>::InsertRear(const T  Item)
    {
        if (Rear == NULL)
        {
            Rear = new Node<T>();
            Rear->value = Item;
            Rear->next = NULL;
            Front = new Node<T>();
            Front = Rear;
        }
        else
        {
            Node<T> * newNode = new Node<T>();
            newNode->value = Item;
            Rear->next = newNode;
            Rear = newNode;
        }
    }
    template<class T>
    void LinkedListClass<T>::PrintList()
    {
        Node<T> *  temp = Front;
        while (temp->next != NULL)
        {
            cout << " " << temp->value << "";
            if (temp != NULL)
            {
                temp = (temp->next);
            }
            else
            {
                break;
            }
        }
    }

    int main()
    {
        LinkedListClass<int> * LList = new LinkedListClass<int>();
        LList->InsertFront(40);
        LList->InsertFront(30);
        LList->InsertFront(20);
        LList->InsertFront(10);
        LList->InsertRear(50);
        LList->InsertRear(60);
        LList->InsertRear(70);
        LList->PrintList();
    }

The addNode function needs to be able to change head. As it's written now simply changes the local variable head (a parameter).

Changing the code to

void addNode(struct Node *& head, int n){
    ...
}

would solve this problem because now the head parameter is passed by reference and the called function can mutate it.


Here is my implementation.

#include <iostream>

using namespace std;

template< class T>
struct node{
    T m_data;
    node* m_next_node;

    node(T t_data, node* t_node) :
        m_data(t_data), m_next_node(t_node){}

    ~node(){
        std::cout << "Address :" << this << " Destroyed" << std::endl;
    }
};

template<class T>
class linked_list {
public:
    node<T>* m_list;

    linked_list(): m_list(nullptr){}

    void add_node(T t_data) {
        node<T>* _new_node = new node<T>(t_data, nullptr);
        _new_node->m_next_node = m_list;
        m_list = _new_node;
    }


    void populate_nodes(node<T>* t_node) {
        if  (t_node != nullptr) {
            std::cout << "Data =" << t_node->m_data
                      << ", Address =" << t_node->m_next_node
                      << std::endl;
            populate_nodes(t_node->m_next_node);
        }
    }

    void delete_nodes(node<T>* t_node) {
        if (t_node != nullptr) {
            delete_nodes(t_node->m_next_node);
        }
        delete(t_node);
    }

};


int main()
{
    linked_list<float>* _ll = new linked_list<float>();

    _ll->add_node(1.3);
    _ll->add_node(5.5);
    _ll->add_node(10.1);
    _ll->add_node(123);
    _ll->add_node(4.5);
    _ll->add_node(23.6);
    _ll->add_node(2);

    _ll->populate_nodes(_ll->m_list);

    _ll->delete_nodes(_ll->m_list);

    delete(_ll);

    return 0;
}

enter image description here


I think that, to make sure the indeep linkage of each node in the list, the addNode method must be like this:

void addNode(struct node *head, int n) {
  if (head->Next == NULL) {
    struct node *NewNode = new node;
    NewNode->value = n;
    NewNode->Next = NULL;
    head->Next = NewNode;
  }
  else 
    addNode(head->Next, n);
}

You should take reference of a head pointer. Otherwise the pointer modification is not visible outside of the function.

void addNode(struct Node *&head, int n){
    struct Node *NewNode = new Node;
 NewNode-> x = n;
 NewNode -> next = head;
 head = NewNode;
}

link list by using node class and linked list class

this is just an example not the complete functionality of linklist, append function and printing a linklist is explained in the code

code :

#include<iostream>
using namespace std;

Node class

class Node{
    public:
    int data;
    Node* next=NULL;
    Node(int data)
        {
            this->data=data;


        }   
    };

link list class named as ll

class ll{
    public:
        Node* head;

ll(Node* node)
    {
        this->head=node;
    }

void append(int data)
    {
        Node* temp=this->head;
        while(temp->next!=NULL)
            {
                temp=temp->next;
            }
        Node* newnode= new Node(data);
        // newnode->data=data;
        temp->next=newnode;
    }
void print_list()
    {   cout<<endl<<"printing entire link list"<<endl;
        Node* temp= this->head;
        while(temp->next!=NULL)
            {
                cout<<temp->data<<endl;
                temp=temp->next;
            }
        cout<<temp->data<<endl;;

    }
};

main function

int main()
{
  cout<<"hello this is an example of link list in cpp using classes"<<endl;
  ll list1(new Node(1));
  list1.append(2);
  list1.append(3);
  list1.print_list();
  }

thanks ???

screenshot https://i.stack.imgur.com/C2D9y.jpg


Use:

#include<iostream>

using namespace std;

struct Node
{
    int num;
    Node *next;
};

Node *head = NULL;
Node *tail = NULL;

void AddnodeAtbeggining(){
    Node *temp = new Node;
    cout << "Enter the item";
    cin >> temp->num;
    temp->next = NULL;
    if (head == NULL)
    {
        head = temp;
        tail = temp;
    }
    else
    {
        temp->next = head;
        head = temp;
    }
}

void addnodeAtend()
{
    Node *temp = new Node;
    cout << "Enter the item";
    cin >> temp->num;
    temp->next = NULL;
    if (head == NULL){
        head = temp;
        tail = temp;
    }
    else{
        tail->next = temp;
        tail = temp;
    }
}

void displayNode()
{
    cout << "\nDisplay Function\n";
    Node *temp = head;
    for(Node *temp = head; temp != NULL; temp = temp->next)
        cout << temp->num << ",";
}

void deleteNode ()
{
    for (Node *temp = head; temp != NULL; temp = temp->next)
        delete head;
}

int main ()
{
    AddnodeAtbeggining();
    addnodeAtend();
    displayNode();
    deleteNode();
    displayNode();
}