Thank you, next! Linked List in C++; Lesson 1

-
Couldn't let this opportunity just slide away! Lets talk about Linked List. 
Linked list is basically a linear data structure which doesn't require consecutive memory location unlike array, rather it use pointers to point at next node. So you could say its can be used as alternative to array.

 To understand the concept, lets consider a linked list with three nodes,including the head node,something like the figure bellow:


Here, each node consists of two parts, a part to store data and a part to store address of the next node, further we observe that there is a pointer that points to head node, this pointer is, you can say, the most important part of linked list as you can use this pointer to get to any node you want, also there is a pointer that points the last node,this pointer too, plays very important role. Other than taking you directly to last node, it helps in adding new nodes.

It may sound a bit overwhelming for now but trust me! Its very interesting concept, now lets move on to our code to understand linked list more efficiently.  
(I'll be using visual studio.)

Okay, we talked about linked list having two parts, one to store data and other to store address of the next node, but i mean what data type will support both data and a link?

data can be stored in int, char, string etc and a pointer can point address right!
So for this we'll create a structure, so we can save both data and address of next node.

We'll start as:

struct node
{
    int data; // for data
    node *next; // for pointing at next node
};

Here (say, our data is int type ), we'll store data in int type variable and save link in node type pointer. Now, lets perform two basic functions i.e input data and print data.

For this, lets create a class named as list. Further, lets create two functions, createnode() to create new nodes and disp() to display nodes. We'll also be using constructor to initiate head and tail pointer.
So our class will look something like this:

class list
{
private:

    node *head;
    node *tail;


public:
    list()
    {
        head = NULL;
        tail = NULL;
      
    }
void createnode()
{
   // code to create node
}

void disp()
{
    //code to display nodes
} 
};

Now lets first code createnode() function:

void createnode()
{
    int value; //1
    cout<<"Enter a value\n"; //2
    cin>>value; //3

    node *temp = new node; //4

    temp->data = value; //5
    temp->next = NULL; //6

    if (head == NULL)//7 decision
    {

        head = temp; //8
        tail = temp; //9
        temp = NULL; //10
    }
    else
    {

        tail->next= temp;//11
        tail = temp;//12

    }
}

So what we did here?
  • We first took a value from user that we'll be storing (line 1,2,3).
  • We created a new node named temp, so as temp is a new node it'll have both, a data part and an address part, i.e it'll have int data and node *next (line 4).
  • Next, we store data in temp's data part (line 5) and then null the next part of temp as we are yet to make a decision of its linking (line 6).
  • Now comes the decision point (line 7), either temp is the very first node, the head node, or its a new node next to head.So here we'll check if head pointer is null (as we initialized head pointer as null) or not. 
  • If head pointer is null then temp will, in fact, be the very first node, so head pointer will point at temp for now (line 8), and as temp is the very first and only node so, obvious enough,it'll be the last node, thus tail pointer will point at temp for now (line 9), also we'll be nullifying temp (line 10) as now next time when createnode() will be called, it'll be required to create node next to head.
  • if head pointer is not null then the next node will be created after head. Now here comes a major part. Right now, as head node is created, both head and tail node are pointing at previous temp i.e now our very first node the head node. So when we wrote   tail->next= temp; We are referring to the head node so this will store the address of (new) temp node in head node's next address(line 11).
  • Finally, the tail pointer is tasked to point at the newly created node, that is created right after head node(line 12). Now we have two nodes, a head node that head pointer is pointing at, a tail node(last node) that tail pointer is pointing at. Now understanding new node addition is crucial. Say you are creating your third node now, now line 11  tail->next= temp; isn't pointing at head node as in line 12 we tasked our code s finally moving our tail pointer to last node. So now tail pointer is pointing at last node, after the linking line 12 makes sure that newly added node is pointed by tail pointer and thus linking goes on while adding every new node as last node. 
Now lets code disp() function

void disp()
{
   

    node *temp = new node; // line 1
    temp= head; // line 2

    while (temp!= NULL) //line 3
    {

        cout << temp->data; //line 4
        temp = temp->next; //line 5
    }
}


So what we did here?
  • We created a new node of type node, i.e it will have both data part and pointer part (line 1).
  • Remember when we talked about head pointer being important, we'll now we'll be using it. Simply assign temp= head; This will make you new node as head node, think of it as all the data  and  next part of head node has been copied in new node temp (line 2).
  • Now comes printing of all nodes, so we'll start from head (line 2) till (temp!= NULL)(line 3) condition i.e until all nodes are printed.
  • Now currently temp has head node's data, so we'll print our first node's (head node's) data (line 4).
  • Next we need to print node next to head and so on, so for this we'll simply assign temp = temp->next; As right now temp had head node data and address, so its next part contain address of node 2 (node after head), so by assigning temp = temp->next;temp node will have copied data and next part of node 2, thus when you'll call disp() function again,it'll now print data of node 2 by using line 4 and will copy data and next part of node 3 in it by using line 5 and so on..
Now lets code our main function, which will call disp() and createnode() function at user's will.

 Our main function will look something like this:

 int main()
{
    list l;
    int choice;

    do
    {
        cout << "\nEnter 1 to create node\nEnter 2 to disp node\nEnter 0 to exit\n";
        cin >> choice;
        if (choice == 1)
        {
            l.createnode();
        }
        else if (choice == 2)
        {
            l.disp();
        }
      
    } while (choice != 0);

    getchar();

}

All we did in main function is,give user a choice to keep on adding and displaying nodes until he/she desires, this is another benefit of linked list over array.

The complete code will look something like this:

#include "pch.h"
#include <iostream>
using namespace std;
struct node
{
    int data;
    node *next;
};
class list
{
private:

    node *head;
    node *tail;


public:
    list()
    {
        head = NULL;
        tail = NULL;
       
    }
    void createnode()
    {

        int value; //1

        cout << "Enter a value\n"; //2

        cin >> value; //3


        node *temp = new node; //4

        temp->data = value; //5
        temp->next = NULL; //6


        if (head == NULL)//7 decision
        {

            head = temp; //8
            tail = temp; //9
            temp = NULL; //10
        }
        else
        {

            tail->next = temp;//11
            tail = temp;//12

        }
    }
void disp()
{
   

    node *temp = new node;// 1
    temp= head; //2

    while (temp!= NULL) //3
    {

        cout << temp->data;//4
        temp = temp->next;//5
    }
}

void insert_start(int value)
{
    node *temp = new node;
    temp->data = value;
    temp->next = head;
    head = temp;
}
};

int main()
{
    list l;
    int choice;

    do
    {
        cout << "\nEnter 1 to create node\nEnter 2 to disp node\nEnter 0 to exit\n";
        cin >> choice;
        if (choice == 1)
        {
            l.createnode();
        }
        else if (choice == 2)
        {
            l.disp();
        }
       
    } while (choice != 0);

    getchar();

} 

Final Output:

In next lesson, we'll be learning adding new nodes to existing linked list, inserting at a specific location etc. Stay tuned!

Comments

Post a Comment

Popular posts from this blog

Introduction to C#; Lesson 2

-
Image
Hope you are following us from our first post, if so! lets continue printing in c# lesson (windows form), if not, don't worry, you can start form the beginning, here is a link for you to review our first lesson: Introduction to C#; Lesson 1 Alright! lets begin our second lesson. As we learnt about printing in textbox, we decided to continue "printing" but in tools other than textbox, like message box and label. So basically today, we'll be introducing a c# tool known as label . Label: Lets give a quick introduction to label first, basically it can be used to Display text. Display text which can't be edited on run time by user like textbox i.e you can't just type your way to change it, rather you'll be required to take input in (say) textbox and then assigning it to label.        So yup! its mostly used to just print statement unless asked, e.g the text such as First Number, Second Number in figure bellow is displayed by using label, but do
Read more

Introduction to C#; Lesson 3

-
Image
Hope you are following us from our first post, if so! lets continue printing in c# lesson (windows form), if not, don't worry, you can start form the beginning, here is a link for you to review our first and second lesson: Introduction to C#; Lesson 1   Introduction to C#; Lesson 2   Alright! lets begin our third lesson. As we learnt about printing in textbox and label in previous lessons, lets move on to Messagebox in this lesson.    Messagebox: Lets give a quick introduction to Messagebox first, basically it can be used to : Display any message at run time such as Warnings Error message. Information, confirmation Prompting user to enter value and so on...  So basically if user leaves some value empty or something then messagebox comes in handy. As message box creates a pop-up screen on your window so user is bound to give attention to your message. User can't proceed until he/she reads the message and give appropriate input etc thus prompting use
Read more

Thank you, next! Linked List in C++; Lesson 4

-
Image
Hope you are following us from our first post about linked list, if so! lets continue with our linked list lesson, if not, don't worry, you can start form the beginning, here are links for you to review our previous lessons: Linked List; Lesson 1   Linked List; Lesson 2   Linked List; Lesson 3   Alright! lets begin our 4th lesson. As we previously learnt about creating nodes and printing by using concept of linked list, further we learnt about inserting new node at head position and a t some given/specified position. So today we'll try to insert nodes at: At position specified by user at run time.   At position specified by user at run time: If you understood lesson 3,this will be a piece of cake for you. So what we are trying to do here is just to replace a specific position in code with the position given at run time by user. For this you'll be codding insert() as follows: void insert() {     node *temp = new node; //1     node *temp1
Read more