Headlines
Loading...
Linked List Operations

Linked List Operations

Create and Display LL

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node *next;
}*first=NULL;

void create(int A[], int n)
{
int i;
struct Node *t ,*last;
first = (struct Node *)malloc(sizeof(struct Node));
first->data=A[0];
first->next=NULL;
last=first;

for(i=1; i<n; i++)
{
t = (struct Node*)malloc(sizeof(struct Node));
t->data=A[i];
t->next=NULL;
last->next=t;
last=t;
}
}

void Display(struct Node *p)
{
while(p!=NULL)
{
printf("%d->", p->data);
p=p->next;
}
}

int main()
{
int A[] = {1,2,3,4,5};
create(A, 5);
Display(first);
return 0;
}

Recursive Display in LL

void Display(struct Node *p)
{
if(p!=NULL)
{
printf("%d", p->data);
Display(p->next);
}
}

Count nodes in LL

int count(struct Node *p)
{
int count=0;
while(p!=NULL)
{
count++;
p=p->next;
}
return count;
}

// Using Recursion
int Rcount(struct Node *p)
{
if(p==0)
{
return 0;
}
return Rcount(p->next) + 1;
}

Sum of all elements in LL

int Add(struct Node *p)
{
int sum=0;
while(p!=NULL)
{
sum=sum+p->data;
p=p->next;
}
}

//Using Recursion
int RAdd(struct Node *p)
{
if(p==0)
{
return 0;
}
return RAdd(p->next)+p->data;
}

Maximum or Minimum element in LL

int Max(struct Node *p)
{
int max=MIN_INT; //sbse chota number ko max me store karaya hai
while(p!=NULL)
{

if(p->data>max)
{
max = p->data;
}

p=p->next;
}
return max;
}

//Using Recursion
int RMax(struct Node *p)
{
int x=0;

if(p==0)
{
return MIN_INT;
}

x = max(p->next)
if(x > p->data)
{
return x;
}
else
{
return p->data;
}
}

Searching in Linked List

// We can't do a binary search in LL 
// Linear search
struct Node * Search(struct Node *p, int key)
{
while(p!=0)
{
if(p->data==key)
{
return p;
}
p=p->next;
}
return NULL;
}

// Recursive function
struct Node * Search(struct Node *p, int key)
{
if(p==NULL)
{
return NULL;
}
if(key==p->data)
{
return p;
}
return Search(p->next, key)
}

// Improved Linear Search
// 1.Tranposition (We don't do)
// 2.Move to head

struct Node * Search(struct Node *p, int key)
{
struct Node *q = NULL;
while(p!=0)
{
if(p->data==key)
{
q->next=p->next;
p->next=first;
first=p;
return p;
}
q=p;
p=p->next;
}
return NULL;
}

Creating a LL

//1. Before first
//2. Inserting after given index
void Insert(struct Node *p, int index, int x)
{
struct Node *t;
if(index<0 || index > count(p))
{
return;
}
t=(struct Node *)malloc(sizeof(struct Node));
t->data=x;

// Before first
if(index==0)
{
t->next=first;
first=t;
}

// Inserting after given index
else
{
for(i=0;i<index-1;i++)
{
p=p->next;
}
t->next = p->next;
p->next=t;
}
}

Insert at Last in LL

void insertLast(int x)
{
struct Node *t, *last;
t=(struct Node *)malloc(sizeof(struct Node));
t->data=x;
t->next=NULL;

// No node in LL
if(first==NULL)
{
first=last=t;
}

// Already have node
else
{
last->next=t;
last=t;
}
}

Insert in sorted LL

void SortedInsert(struct Node *p, int x)
{
struct Node *t, *q=NULL;
t=(struct Node*)malloc(sizeof(struct Node));
t->data=x;
t->next=NULL;

if(first==NULL)
{
first=t;
}
else
{
while(p!=0 && p->data<x)
{
q=p;
p=p->next;
}
if(p==first)
{
t->next=first;
first=t;
}
else
{
t->next=q->next;
q->next=t;
}
}
}

Deleting from LL

// Deleting the node
// 1. Delete first node
// 2. Delete a node at given position

// 1. Delete first node
Node *p = first;
first=first->next;
free (p);

// 2. Delete a node at given position
Node *p = first;
Node *q = NULL;

for(int i=0; i<pos-1; i++)
{
q=p;
p=p->next;
}

q->next=p->next;
free (p);

Is LL sorted?

int isSorted(struct Node *p)
{
int x = INT_MIN;
while(p!=0)
{
if(p->data < x)
{
return 0;
}
x=p->data;
p=p->next;
}
return 1;
}

Congratulations to you, if you really understand this section. Any doubts? Then you can ask me in the comment section. 

As we covered Linked List, this is the right time to solve some Leetcode easy Linked List questions.

What's next?

Comming soon... 

0 Comments: