Linked List in C++:
Today, we will learn about linked list in C++ basic programming. As you know, Arrays have limited size instead of linked list is flexible. First we need to understand its structure and rules to utilize it, Let’s see;
Linked List Structure:
Linked list is look like a chain node structure. Every node have two portions “Object” and “Next”. Object field hold the actual list element and “Next” field hold the address of the next node. These nodes work together in the form of chain.
Above image is expressing the definition of node in linked list. After know about each node structure, Go ahead with linked list structure. While constructing linked list, we uses few nodes names in linked list such as, Head node, Current node, Last current node and variable Size. Assume that, If you have some numbers (1,2,3,4,5) and want to store these numbers in a memory using linked list.
You can clearly see in the below image, Initial node is always known as header node. Which node, where pointer exist currently is known as current node.
In the above image, header node hold two elements 1 and next node address. Similarly, Every node ahead of header node hold previous node address and an object. Take the above 5 nodes example and its process below.
Header node hold second node address and object 1.
Second node hold third node address and object 2.
Third node hold forth node address and object 3.
Fourth node hold fifth node address and object 4.
Fifth node hold fifth node address and object 5.
This process will continuously work till the last node and we can store infinite integers because linked list is not bound like arrays.
Note:
First node should be exist there as a head node, otherwise we won’t know where the start of this list. Current is a pointer, not an index. Next field in the last node points to nothing, we will place the memory address NULL, Which is inaccessible.
Adding New Node in Linked List:
After getting little bit knowledge, Now we are going to create or add a new node inside linked list. This procedure consists on some steps. Suppose that, we have a number (8) and want to add this one inside linked list. So, first we need to create new node and find the destination, where you want to insert it. Before going ahead, see the below image steps.
In above image, You can clearly review these steps. We add a new node in the previous linked list example. For adding a new node among two existed nodes, New node address will be put in the previous node next field and Next node address will be placed in new node next field. That’s it. Keep remember, now new node will be known as current node. And size will also increase from 5 to 6 nodes.
Linked List Simple Program:
We implement the above given linked list in C++ code, which will help you to understand this logic. Review the below C++ Program.
#include using namespace std; class Node{ int object; Node *next; public: Node(){ object =0; next = NULL; } void setObject(int object){ this->object = object; } void setNext(Node *next){ this->next = next; } int getObject(){ return object; } Node * getNext(){ return next; } }; class List{ Node *headNode; Node * currentNode; Node * lastCurrentNode; int size; public: List(){ headNode = new Node(); currentNode = NULL; lastCurrentNode = NULL; size = 0; } int length(){ return size; } void head(){ currentNode = headNode; lastCurrentNode = headNode; } bool next(){ if (currentNode == headNode && lastCurrentNode==headNode){ currentNode = currentNode->getNext(); return true; } if (currentNode -> getNext() == NULL){ return false; } else{ lastCurrentNode = currentNode; currentNode = currentNode->getNext(); return true; } } int get(){ return currentNode->getObject(); } void display(){ head(); while(currentNode->getNext() != NULL){ next(); cout << get() << "t"; } cout << endl; } void insert(int data){ Node *newNode = new Node(); newNode -> setObject(data); newNode -> setNext(currentNode); lastCurrentNode -> setNext(newNode); lastCurrentNode = newNode; size++; } void add(int data){ Node *newNode = new Node(); newNode->setObject(data); if (currentNode == NULL){ currentNode = newNode; lastCurrentNode = headNode; headNode->setNext(currentNode); } else{ lastCurrentNode = currentNode; currentNode = newNode; lastCurrentNode->setNext(currentNode); } size++; } }; main(){ List l; l.head(); l.add(1); l.add(2); l.add(3); l.insert(8); l.add(4); l.add(5); l.display(); cout << endl << "Size of linked list = " << l.length(); cout << endl; }
Above mentioned program output will look like this on run time,
Simply you can evaluate the sorting of these numbers (1,2,3,4,5), which we discussed a couple of seconds ago in above statement. This program will also determine the size of linked list objects. You can enhance or edit this program for more practice.
Hopefully, You will understand with ease. Don’t forget to practice because practice makes a man perfect. If you found any unusual error then let us know, we will assist you. 😉