Singly Linked list
In a singly linked list, we omit the prev pointer in each element
Address of the head node give us access of the complete list
Array VS linked list
| Array | Linked list | |
|---|---|---|
| Cost of accessing an element | Ο(1) | Ο(n) in average case |
| Memory requirement | fixed size | no unused memory , extra memory for pointer variables, more flexible |
| Cost of Inserting element at beginning | Ο(n) | Ο(1) |
| Inserting element at the end | ① Ο(1) if array isn't full. ② Ο(n) if array is full. | Ο(n) |
| Inserting element at ith element | Ο(n) | Ο(n) |
How to create a linked list
Implement in C :
1.create a node first:
struct Node
{
int data;
struct Node* next;
}* head;
2.Put your element in the list:
void Put(int x)
{
struct Node* temp =(struct Node*)malloc(sizeof(struct Node)); //create a node
temp->data=x; //put in the data
temp->next=head; //make next node as head
head=temp; //let head point to the next node
}
3.Traverse the linked list
psudocode first:
node* temp=A
while( temp -> link != NULL)
{
temp=temp -> link;
print" temp ->data
}
In C code:
void Display()
{
struct Node* temp=head;
printf("Current list is ");
while(temp !=NULL) //traverse
{
printf("%d",temp->data);
temp=temp->next;
}
printf("\n");
}
4.Free memory
psudocode first:
node = head
while node != null:
temp = node
node = node.next
free temp
head = null
In C code:
void Free(struct Node*head)
{
struct Node*temp;
while(head != NULL)
{
temp=head;
head=head->next;
free(temp);
}
head=NULL;
}
View complete C code of create linked list here.
Inserting into a linked list
LIST -Insert (L, x)
next [x ]←head [L]
if head [L]≠NIL
then prev [head [L ]]←x
head [L]←x
prev [x]←NIL
Implement in C:
void Insert(int data,int n)
{
struct Node* temp1=(struct Node*)malloc(sizeof(struct Node));
temp1->data=data;
temp1->next=NULL;
if(n == 1)
{
temp1->next=head;
head=temp1;
return;
}
struct Node* temp2=(struct Node*)malloc(sizeof(struct Node));
temp2=head;
int i;
for(i=0; i<n-2; i++)
{
temp2 = temp2->next;
}
temp1->next = temp2->next;
temp2->next = temp1;
}
View complete C code of insertion here.
Searching a linked list
List _ Search(L, k)
x ←head[L]
while x≠NIL and key[x]≠k
do x←next[x]
return x
It takesΘ(n) time in the worst case.
**Implement in C: **
void Search(int n)
{
while(head != NULL)
{
if(head ->data == n)
{
printf("element found\n");
return;
}
head =head->next;
}
printf("element don't exist in this list");
}
View complete C code of Search particular element in linked list here.
Delete
Delete at nth position :
void Delete(int n)
{
struct Node* temp1=head;
if(n==1)
{
head=temp1->next;
free(temp1);
return;
}
int i;
for(i=0; i<n-2; i++)
{
temp1=temp1->next;
}
struct Node*temp2 = temp1-> next;
temp1->next = temp2->next;
free(temp2);
}
**View complete Delete code here. **
Sort linked list
We use merge sort to sort linked list
1.Split your list into two parts
void split(struct node* Node,struct node **front,struct node **back)
{
struct node* a;
struct node* b;
if(Node==NULL || Node->next==NULL)
{
*front=Node;
*back=NULL;
}
else
{
a=Node;
b=Node->next;
while(b != NULL)
{
b=b->next;
if(b!= NULL)
{
a=a->next;
b=b->next;
}
}
*front=Node;
*back =a->next;
a->next= NULL;
}
}
struct node* merge(struct node *a,struct node *b)
{
struct node* list=NULL;
if(a==NULL)
{
return b;
}
else if(b==NULL)
{
return a;
}
if(a->data > b->data)
{
list=b;
list->next=merge(a,b->next);
}
else
{
list=a;
list->next=merge(a->next,b);
}
return list;
}
void mergesort(struct node** Node)
{
head=*Node;
struct node* a=NULL;
struct node* b=NULL;
if(head==NULL || head->next== NULL)
{
return;
}
split(head,&a,&b);
mergesort(&a);
mergesort(&b);
*Node=merge(a,b);
}
Complete code here
