A linked list is a linear data structure, in this data structure, the elements are stored at contiguous memory locations. A linked list comes into action to cover all the backdrops of arrays. In arrays, we have to allocate the memory before entering the elements, when we don't know the exact memory requirements, the memory will be wasted. And also to add an element to an array when the whole array is filled is a complex and memory wastage process.
 |
How to declare a node In a Linked List?
struct Node {
int data; //Field to store data
Node* next; //Field to store address of the next Node
};
Insertion Of Data at Head In Linked List:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = new Node(); // Allocating memory for head node
void insert(int x){
Node* temp = new Node();
temp->data=x;
temp->next=head; // head will be the next of the new node
head=temp; // new node will be the head
}
void print(){
Node* temp = head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<"\n";
}
int main()
{
head = NULL;
cout<<"How many nodes? \n";
int n,x;
cin>>n;
for(int i=0;i<n;i++){
cout<<"Enter the data \n";
cin>>x;
insert(x);
print();
}
return 0;
}
Output:
 |
| Output |
Insertion at Given position (nth position): Linked List
#include<stdio.h>
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = new Node();
void print(){
Node* temp = head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<"\n";
}
void insert(int data, int n){
int i;
Node* temp1 = new Node();
temp1->data=data;
temp1->next=NULL;
if(n==1){
temp1->next=head;
head=temp1;
return;
}
Node* temp2 = head;
for(i=0;i<n-2;i++){
temp2=temp2->next;
}
temp1->next=temp2->next;
temp2->next= temp1;
}
int main(){
head=NULL;
insert(4,1); //4
insert(6,2); // 4 6
insert(7,1); // 7 4 6
print();
}
Deleting A Node at Nth Position: Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = new Node();
void Delete(int n){
Node *temp1 = head;
if(n==1){
head=temp1->next;
free(temp1);
return;
}
for(int i=0;i<n-2;i++){
temp1 = temp1->next;
}
Node *temp2 = temp1->next; //nth node
temp1->next = temp2->next;
free(temp2);
}
void insert(int x,int n){
Node *temp1 = new Node();
temp1->data=x;
temp1->next = NULL;
if(n==1){
temp1->next=head;
head=temp1;
return;
}
Node *temp2 = head;
for(int i=0;i<n-2;i++){
temp2=temp2->next;
}
temp1->next= temp2->next;
temp2->next=temp1;
}
void print(){
Node *temp = head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<"\n";
}
int main()
{
head = NULL;
insert(3,1);
insert(2,2);
insert(5,1);
insert(6,4);
print();
Delete(2);
print();
}
Output:
 |
| Deleting A node from the linked list at nth position |
Reversing A Linked List Using Iteration Method: Linked List Data Structure
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head;
void print(){
Node* temp = head;
while(temp!=NULL){
cout<<temp->data;
temp=temp->next;
}
cout<<"\n";
}
void insert(int data, int n){
Node* temp1 = new Node();
temp1->data=data;
temp1->next=NULL;
if(n==1){
temp1->next=head;
head=temp1;
return;
}
Node* temp2 = head;
for(int i=0;i<n-2;i++){
temp2=temp2->next;
}
temp1->next=temp2->next;
temp2->next=temp1;
}
void Delete(int n){
Node* temp1=head;
if(n==1){
head = temp1->next;
free(temp1);
return;
}
for(int i=0;i<n-2;i++){
temp1=temp1->next;
}
Node* temp2 = temp1->next;
temp1->next=temp2->next;
free(temp2);
}
void reverse(){
Node *current, *next, *prev; //three pointers to store the addresses
current = head;
prev = NULL;
while(current!=NULL){
next = current->next; //next stores the address of the next node of the current node
current->next= prev; /* reversing the list by assigning the previous node to the current
node, current node is stored in the next node and it helps to access the next node even the link has brokent */
prev=current;
current = next;
}
head=prev;
}
int main()
{
head = NULL;
insert(3,1);
insert(5,2);
insert(7,3);
print();
reverse();
print();
Delete(2);
print();
reverse();
print();
return 0;
}
Linked List Implementation Using Python
class Node:
def __init__(self,data,next):
self.data = data
self.next = next
class Linkedlist:
def __init__(self):
self.head = None
def Insert_at_begin(self, data):
node = Node(data, self.head)
self.head = node
def print(self):
if self.head is None:
print("Linked List is Empty")
return
llstr = ''
temp = self.head
while temp:
llstr += str(temp.data) + ' '
temp = temp.next
print(llstr)
def Insert_at_end(self,data):
if self.head is None:
self.head = Node(data,None)
return
temp = self.head
while temp.next:
temp= temp.next
temp.next = Node(data, None)
if __name__ == '__main__':
Llist= Linkedlist()
Llist.Insert_at_begin(4)
Llist.Insert_at_begin(5)
Llist.Insert_at_end(6)
Llist.Insert_at_begin(3)
Llist.Insert_at_begin(2)
Llist.Insert_at_end(7)
Llist.print()
OutPut:
Linked List Full Implementation in C++:
#include<iostream>
using namespace std;
struct Node { //Node Structure
int data;
Node* next;
};
Node* GetNewNode(int data){ // Function to return a new node with data
Node* newNode = new Node();
newNode->data=data;
newNode->next = NULL;
return newNode;
}
Node* head = NULL; // Declaring head globally
void Display(){ //function to print all the elements in the linked list
if(head==NULL) return;
cout<<"Linked List Items: ";
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
void InsertAtHead(int data){ // function to insert data at head
cout<<"Inserted "<<data<<endl;
if(head==NULL){
head= GetNewNode(data);
Display();
return;
}
Node* temp = GetNewNode(data);
temp->next = head;
head= temp;
Display();
}
void InsertAtN(int data,int n){ //function to insert data at nth position
Node* newNode = GetNewNode(data);
if(n==1){
newNode->next=head;
head=newNode;
return;
}
Node* temp=head;
for(int i=0;i<n-2;i++){
temp=temp->next;
}
cout<<"Inserted "<<newNode->data<<" at "<<n<<endl;
newNode->next=temp->next;
temp->next=newNode;
Display();
}
void DeleteAtHead(){ // function to delete head node
if(head==NULL) return;
Node* temp=head;
cout<<temp->data<<" Deleted at Head" <<endl;
head=temp->next;
delete temp;
Display();
}
void DeleteAtN(int n){ // function to delete node at nth position
Node* temp1 = head;
if(n==1){
head= temp1->next;
cout<<"Deleted "<<temp1->data<<" at head "<<endl;
Display();
delete temp1;
return;
}
for(int i=0;i<n-2;i++){
temp1=temp1->next;
}
Node* temp2 = temp1->next;
cout<<"Deleted "<<temp2->data<<" at "<<n<<endl;
temp1->next = temp2->next;
delete temp2;
Display();
}
void ReverseList(){ // function to reverse the linkedlist
Node *current, *prev, *next;
current = head;
prev = NULL;
while(current!=NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head=prev;
Display();
}
int main() {
InsertAtHead(4);
InsertAtHead(3);
InsertAtHead(2);
InsertAtHead(1);
InsertAtN(5,5);
InsertAtN(333,2);
InsertAtN(74,4);
DeleteAtHead();
DeleteAtHead();
DeleteAtN(1);
ReverseList();
}
Linked List Output:
No comments:
Post a Comment