How to implement Singly Link List using C++ with Examples

Singly Link List
Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Singly Link List is one of the common data structures. Hello Programmers. Hopefully, you are doing well. In this tutorial, I am going to show you how to implement a singly link list using C++. I will also show you a couple of functions related to the Link List.

Well, before diving into the tutorial you have to knowledge about pointers and structure. I assume you are familiar with pointers and how to allocate space using pointers as well as structure.

Read More : Implement a Binary tree with inOrder postOrder preOrder

Singly Link List using C++

Well, first you have to define a structure. In this structure take an integer variable and take a pointer variable for your node.

Define Structure
typedef struct Node{
    int data;
    struct Node *next;
}node;

Well, now you have to take a global node variable and also take a integer variable to start your list. Initially count is equal to zero.

node *head;
int count = 0;

Then you have to define a void function to initialize *head pointer value. Your function looks like this

void initial(){
    head = 0;
}

Well, now you may create a function for insert data in the first position of your list. Your function should take an integer value and its data type will void.

Insert First Position of List

void insertFirst(int val){
    node *newNode;
    newNode = new node;
    newNode->data = val;
    newNode->next = head;
    head = newNode;
    count ++;
}

Let me explain, what I have done in this insertFirst function. Well, first I’ve taken a node variable for our new node. Then using new keyword allocated space for the next node. After then the new node’s data part assigns our value which is the parameter of insertFirst function. Then new node’s next part assigns a head pointer(which is a global pointer variable). Finally, the head is equal to the new node.

You may noticed that after inserting value count value is incrementing . Using this count variable we will get the length of our list. Make a funciton to get the length of list.

int lengthOfList(){
    return count;
}

Insert Last Position of List

Well, now I will show you how to insert data in the last of a link list. Let’s create a function which name is insertLast. Which also takes a value as a parameter. Looks the following code

void insertLast(int val){
    if(head == 0){
        insertFirst(val);
    }else{
        node *newNode,*temp;
        newNode = new node;
        newNode->data = val;
        newNode->next = 0;
        temp = head;
        while(temp->next !=0){
            temp = temp->next;
        }
        temp->next = newNode;
        count++;
    }
}

Well, let me explain what I have done with this function. First I am checking that the head (global variable) is equal to zero or not. If the head is equal to zero that means our list is empty, we have to insert the first position. To do that I am calling insertFirst function which was created before. Well in this else portion that means our list isn’t empty.

Insert a specific position

void insertAfterPosition(int pos,int val){
    int index =1;
    if(pos == 0){
        cout<<"Position Can't be Zero!!\n";
        return;
    }
    if(pos == 1){
        insertFirst(val);
        return;
    }
    if(lengthOfList() < pos){
        cout<<"Invalid Position!"<<endl;
    }else{
        node *temp,*newNode;
        temp = head;
        while(index<pos-1){
            temp = temp->next;
            index++;
        }
        newNode = new node;
        newNode->data = val;
        newNode->next = temp->next;
        temp->next = newNode;
        count++;
    }
}

Our inserting function has been done. Now I will show you to display the values of list. Well, let’s make a function for display our data.

Display Data

void display(){
    if (head == 0){
        cout<<"Empty List"<<endl;
    }else{
        cout<<"Display : ";
        node *temp;
        temp = head;
        while(temp != 0){
            cout<<temp->data<<" ";
            temp = temp->next;
        }
    }
    cout<<endl;
}

Using this function you can see your list’s data.Now I will show you how to delete first node of our list. To do that,let’s make a fucniton.

Delete First Node

void deleteFirstNode(){
    if(head == 0){
        cout<<"Empty List"<<endl;
    }
    node *temp;
    temp = head;
    head = head->next;
    free(temp);
}

Well, For deleting last node we have to make a function. Looks the following code.

Delete Last Node

void deleteLastNode(){
     if(head == 0){
        cout<<"Empty List"<<endl;
    }
    node *temp,*prev;
    temp = head;
    while(temp->next != 0){
            prev = temp;
        temp = temp->next;
    }
    if(head == temp){
        head = 0;
    }else{
        prev->next = 0;
    }
    free(temp);
}

Using this function you will be able delete the last node of our list. Well , now I will show you how to delete a specific by postion. Let’s make a fucntion. Which take a perameter, this parameter is the position of our specific node.

Delete Node By Positon

void deleteNodeByPosition(int pos){
    if(head == 0){
        cout<<"Empty List"<<endl;
        return;
    }
    if(pos> lengthOfList()){
        cout<<"\nInvalid Position\n";
        return;
    }
    if(pos == 1){
        deleteFirstNode();
        return;
    }
    int index = 1;
    node *temp,*prevNode,*nextNode;
    temp = head;
    while(index < pos-1){
        temp = temp->next;
          //cout<<"t "<<temp->data;
        index++;
    }
    prevNode = temp;
    nextNode = prevNode->next;
    temp->next = nextNode->next;
    free(nextNode);
}

Well, Our insertions and deletaions part has been done. Now, I will show you how to search a node by value.

Search A Node by value

int searchNodePositionByValue(int val){
    if(head == 0){
        return -1;
    }
    node *temp;
    int index = 1;
    temp = head;
    while(temp != 0){
        if(temp->data == val){
            return index;
        }
        else if(temp->next == 0){
            return -2;//-2 for invalid input
        }
        index ++;
        temp = temp->next;
    }
}

Well, Now I will show you how to get maxium value form the list. Follow this code

int getMaximumValue(){
    int max = INT_MIN;
    node *temp;
    temp = head;
    while(temp != 0){
        if(max < temp->data){
            max = temp->data;
        }
        temp = temp->next;
    }
    return max;
}

Get Node by value

node *getNodeByValue(int val){
    node *temp;
    int index = 1;
    temp = head;
    while(temp != 0){
        if(temp->data == val){
            return temp;
        }
        else if(temp->next == 0){
            return NULL;//-2 for invalid input
        }
        index ++;
        temp = temp->next;
    }
}

Well, Our all function almost done. In this last fucntion I will show you that how to change a node’s value.

void changeNodeValue(int oldVal, int newVal){
   getNodeByValue(oldVal)->data = newVal;
}

Basically this is a bit complex function. Let me explain about this funciton(changeNodeValue). This function take two parameter which are old value and new value. Inside the I call another function which return a node the i override node->data value new value.

Hope this tutotial will help you.

Github : https://github.com/AR-Shahin/Data_Structure_and_Algorithm/blob/main/Link_list/singlyList.txt

Read More : The complexity of an Algorithm 

Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published. Required fields are marked *