c++ linked list

C++ Linked list

Linked list is a data structure.
It is pretty much like an array that change its sizes.
Each componet of linked list is called a node.
Nodes are linked pointers.

Building linked list is a really good pointer practice. You need to very familiar with pointers to bulid it.

Whenever you are stuck with it, draw it like following.
I think it is the best way to solve any problem with linked list.

          head node                                                                                                                   last node

Every node has next pointer which points to the next node.
The last node's next is null; null indicates the last node of the linked list
----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.


 #include <iostream>

using namespace std;

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

// initialize linked list
void initNode( struct Node * node, int val )
{
    node -> data = val;
    node -> next = NULL;

}
// add node
void addNode ( struct Node * node, int val)
{
    // create new node
    // this node will be placed at the end of node
    // that's why newNode -> next is NULL
    Node * newNode = new Node;
    newNode -> data = val;
    newNode -> next = NULL;

    Node * tmp = node;
    //move to the end of linked list
    while ( true ) {
        // when program gets to the end of linked list add new node
        // this new node become the end of linked list
        if ( tmp -> next == NULL ){
            tmp -> next = newNode;
            return;
        }
        tmp = tmp -> next;
    }

}

// add node at the beginning of linked list
void addNodeAtFirst ( struct Node * node, int val)
{
    // make a copy of the first node
    Node * newNode = new Node;
    newNode -> data = node -> data;
    newNode -> next = node -> next;

    // change the fist node of linked lisk to the val
    // point the head of node to new node
    node -> data = val;
    node -> next = newNode;
  

}

// delete all node
void deleteAllNode ( struct Node * node)
{
    Node * tmp = node;

    // delete all node
    // loop stop when it reaches to the last node
    while (tmp -> next != NULL){
        Node * helper = tmp;
        tmp = tmp-> next;
        delete helper;
    }

    // delete the last node
    delete tmp;
}

// print all node
void printNode( struct Node * node)
{
    // case when there is no item in the linked list
    if(node == NULL){
        cout << "there is no item" << endl;
    }
    // print node until the program reaches to the last node
    else{
        Node * tmp = node;
        while ( tmp -> next != NULL){
            cout << tmp -> data << endl;
            tmp = tmp ->next;
        }

        // print last node
        cout << tmp -> data << endl;
    }
}

// seach for specific node
bool searchNode ( struct Node * node, int val)
{
    Node * tmp = node;
    //checking everything except last one

    while( tmp -> next != NULL){
        if (tmp -> data == val){
            return true;
        }
        tmp = tmp-> next;
    }

    //checking the last one
    if( tmp -> data == val)
        return true;
    else
        return false;
}

// delete certain node
void deleteNode ( struct Node * node, int val)
{
    Node * tmp = node;
    Node * tmp2 = node;

    // seach for node
    // tmp and tmp2 point same node for the first node of the linked list
    // after that
    // tmp points the current node
    // tmp2 points the previous node
    while ( tmp -> next != NULL){
        if (tmp -> data == val){
            tmp2 -> next = tmp-> next;
            cout << "delete " << tmp -> data << endl;
            delete tmp;
            return;
        }
        tmp2 = tmp;
        tmp = tmp ->next;
    }

    // after the loop, tmp points the last node of linked list
    // you do not have to worry about tmp2 at this point.
    // becuase tmp already checked it.
    if (tmp -> data == val){
        cout << "delete "  << tmp -> data << endl;
        delete tmp;
        return;
    }

    else{
        cout << "there is no such val, cannot delete the request val" << endl;
    }

}


int main()
{
    // If node is empty, you cannot print the linked list ( you will get the error)
    // other than that, feel free to play with it

    Node * head = new Node();
    initNode( head, 10);
    addNode( head,  6);
    addNode( head, 3);
    addNode( head, 67);
    addNodeAtFirst (head, 99);
    printNode( head );
    deleteAllNode( head );

    cout << "new start" << endl;
    head = new Node();
    initNode( head, 5 );
    addNode ( head, 65);
    addNode ( head, 75);
    printNode( head );

    cout << "search 6. Since there is no 6 in the linked list, the following funtion return 0" << endl;
    cout << searchNode( head, 6) << endl;
    cout << "search 5. the following function return 1" << endl;
    cout << searchNode( head, 5) << endl;

    deleteNode( head, 65);
    deleteNode( head, 75);
    deleteNode( head, 5);

    printNode( head );
  

}