cft

Linked List for Beginners!

Here I will discuss about basics of Linked List and some Operations like Insertion, Deletion and Searching.


user

Daksh Rao

3 years ago | 3 min read

You must be familiar with Array's, it's a continous linear/multidimensional data type. While Linked Lists are linear non continous data type. As its name suggestes "Linked" means different data locations are linked using pointers.

📷
📷"Image source GFG"


Above is the view of A simple Linked List. Here "A" is our head container and "D" is our tail container. Each container stores two things one is the data and second is the address of next linked container. So in this case "A" stores address of "B", "B" stores address of "C" and "D" stores NULL. These containers are known as nodes.


Creating a Node
Since node is storing two different data types, we can use struct or class. Here, I am using class method to create a node class.

class node{
public:
int data;
node *next;

//Constructor
node(int d){
data=d;
next=NULL;
}
};

"next" variable will store the address of next linked node and "data" will store int data. Constructor will be used to insert data in our node.


Inserting Data
Data can be inserted in 3 ways :-

  • At Head
  • In Middle of Two Nodes
  • At Tail

Inserting At Head
Assume we add a node "E" at head in above A-B-C-D Linked List. New list formed will be E-A-B-C-D.

void insertAtHead(node *&head,int d){
if(head==NULL){
//we are insering first node
head = new node(d);
return;
}
//creating new node that is going to insert.
node *n = new node(d);
n->next=head;//passing address of previous node to new head
head=n; //setting new node as head
}

Note, here we are passing node by reference not by value, as our actual value of head will be shifted from "A" to "E".
"->" is used to access members of class using pointers.

DRIVER FUNCTION
int main(){
node *head=NULL;
insertAtHead(head,3);
insertAtHead(head,2);
insertAtHead(head,1);
insertAtHead(head,0);

return 0;
}

This will give us the linked list 0-1-2-3 and if we add insertAtHead(head,5) new linked list will be 5-0-1-2-3. I am leaving Inserting at Tail and in Middle of two Nodes as practice questions for you.
For printing this Linked List we can create a Function as

void print(node *head){
while(head != NULL){
cout<<head->data<<"-";
head = head->next;
}
}



Deletion
Like of insertion, deletion can be done on a Head or Tail

void deleteHead(node* &head){
if(head==NULL){
//if there's no node then exit the function
return;
}
//creating a temp node to store address of 1st node
node *temp = head->next;
delete head;
//marking 1st node as new head
head = temp;
}

Note, Indexing here is done as of Array(from 0).
If we call it using deleteHead(head,5), the above linked list will be shown as 0-1-2-3.


Searching
Linked list can be searched in two ways either iterative or by using recursion. It will be easier to know iterative first, So let's discuss it.

bool search(node*head,int key){
while(head!=NULL){
if(head->data == key){
return true;
}else{
head = head->next;
}
}
return false;
}

If "head node" contains the key then we will return "true" else we will update the value of "head" to "head->next".
Note, here we are passing by value so the actual value of "head" remains unchanged.

Congrats, You just completed the basics of Linked Lists !
Feedback would be highly appreciated.

Upvote


user
Created by

Daksh Rao

I am a developer from Hisar, currently pursuing Computer Engg. from IKGPTU. I am a multitasker guy and sometime this kills me but that's the fun in it. Being Pressured by the the technologies!


people
Post

Upvote

Downvote

Comment

Bookmark

Share


Related Articles