Linked List in C++ | Data Structure

What is Linked List?

Linked list is a very important  data structure in any programming language. It can handle data very efficiently and in a very structured manner.Linked list is an ordered and structured set of data elements, each containing a link or an address to its successor (Next Data Element) and sometimes its predecessor(Previous Data Element). Linked List can store any data you want, but you have to declare it while coding. The very best advantage of using Linked List is the Dynamic Memory Allocation, which makes it more efficient to use. Another advantage of using a linked list is that you can implement many other Data Structures (Stack,Queue,Tree, etc.) using Linked List. The most amazing and last but not the least, you can change the size of Linked List at run. This benefit of using linked list makes it the most awesome data structure and also a bit difficult to implement.

Structure of Linked List

The structure is very simple. This data structure is base on some called a “NODE”. NODE is something like a unit of this data structure. It’s plays a very important role in the making of a list.The Node contains two parts

  • Data  part or information part
  • Link part or address part

Linked List

Linked list is simply Connection of some node attached together in a chain like a iron chain.Each of the node contains the address or link to the next Node.As we know that memory is Dynamically allocated in List so we need to use pointers.

But for making a List efficient we need to use another Pointer which points towards the first node it is sometimes called Head pointer, front pointer or start pointer.

Linked List

Implementation

It can be implemented by two programming techniques.

  • Procedural Programming (The traditional c)
  • OOP(Object Oriented Programming)

But at first we will deal with how we can create a single Node in c++

code

/*
*@Author=abdul_aziz
*@Program=Linked List
*@description= A simple program to explain how to make a single node

*/

#include <iostream>
#include <string>

using namespace std;

struct Node{
int data;
Node *link;
};
int main () {

Node* ptr;
ptr=new Node;
ptr->data=10;
ptr->next=NULL;
cout <<ptr->data;
delete ptr;

return 0;
}

Explanation

  1. First of all you have to make a structure using struct keyword in c++. This structure will contain two things
    • First the data part with it’s data type.This defines the type of data you are going to use.
    • Second is the Pointer part which will point towards the next node of the list and we can make more nodes by repeating this.
  2. Now you can make a pointer in main function to allocate dynamic memory of Node type to the use it.

Some Basic Operations

There are some basic operations in a List

  1. Insert
  2. Delete
  3. Traversing

Code

#include <iostream>
#include <string>

using namespace std;
struct Node{
int data;
Node* link;
};
Node* start=NULL;
Node* createNode(){
Node* temp;
temp=new Node;
return temp;
}
void insertNode() {
Node* temp,*t;
temp=createNode();
cout << "Enter a number: "<<endl;
cin>>temp->data;
temp->link=NULL;
if (start==NULL) {
start=temp;
} else {
t=start;
while(t->link!=NULL) {
t=t->link;
}
t->link=temp;
}
}
void deletingFirstNode(){
if (start==NULL) {
cout << "List is empty"<<endl;
} else {
Node *temp;
temp=start;
start=start->link;
temp->link=NULL;
delete temp;
}

}
void traversing() {
Node *temp=start;
cout <<endl<<"Traversing"<<endl;
if (start==NULL) {
cout << "List is empty"<<endl;
} else {
while (temp!=NULL) {
cout << temp->data<<endl;
temp=temp->link;
}
}
}
int main () {
// Here you can call any function

return 0;
}
All this code is written using procedural programming technique here is the OOP (Object Oriented Programming) based code as well.

Linked List in OOP (Object Oriented Programming)

#include <iostream>
#include <string>

using namespace std;
class Node{
public:
int data;
Node* next;
};
class SingleLinkedList{
public:
bool isEmpty(Node* head){
if (head==NULL) {
return true;
} else{
return false;
}
}
void insertAsFirstElement(Node *&head,Node *&last,int data){
Node *temp=new Node;
temp->data=data;
temp->next=NULL;
head= temp;
last=temp;
cout << "New element inserted"<<endl;
}

void insert(Node *&head,Node *&last,int data){

if(isEmpty(head)) {
insertAsFirstElement(head,last,data);
} else {
Node *temp=new Node;
temp->data=data;
temp->next=NULL;
last->next=temp;
last=temp;
}
}
void remove(Node *&head,Node *&last){
if (isEmpty(head)) {
cout << "The list is already empty"<<endl; 
} else if(head==last) {
delete head;
head==NULL;
last==NULL;
} else{
Node* temp=head;
head=head->next;
delete temp; 
}
}
void showList(Node *current){
if (isEmpty(current)){ 
cout << "The list is empty"<<endl;
} else {
cout << "The list contains"<<endl;
while(current!=NULL) {
cout <<current->data;
current=current->next;
}
}
}

};
int main () {
Node* head=NULL;
Node* last=NULL;
int number=10;
SingleLinkedList s;
s.insertAsFirstElement(head,last,number);
s.showList(head);

return 0;
}

You can Copy this if you want. If you have any questions or doubts about it, you can comment anytime..Stay tuned stay blessed 😊

3 Comments

Add a Comment

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