Linked List Basics
A linked list is the collection of a set of nodes that are connected continuously and those nodes contain its data(value) and address(the next link position). A linked list is a branch of linear data structure. It is mostly like an array but more than an array and it is faster also.
1. The first node is called the head node.
2. The last node is known as the tail node.
3. Every node contains an address except the last tail node.
Node is the merge block of data and address values in a linked list.
Why should we use a linked list but not an array?
1. The Linked list is made for the Dynamically Memory Allocation (DAM). The linked list dynamically allocates memory by directly accessing the address.
2. No need to be defined the size of a linked list.
3. It is faster than an array in all operations ( to insert data, to delete data, to search data, to update data).
4. As we know, a linked list directly accesses the memory location. So, the execution time to access the data in a linked list is very fast than an array.
Code for the Linked List
#include <stdio.h>
#include <stdlib.h>
struct node{
int key, data;
struct node *next;
};
struct node *start = NULL;
struct node *current = NULL;
bool isEmpty()
{
if(start == NULL)
return true;
return false;
}
void listInsert(int key, int data)
{
struct node *item;
item = (struct node *)malloc(sizeof(struct node));
item->key = key;
item->data = data;
item->next = start;
start = item;
}
void showList()
{
if(isEmpty())
{
printf("List is Empty\n");
}
else
{
current = start;
while(current != NULL)
{
printf("Key: %d\tData: %d\n", current->key, current->data);
current = current->next;
}
}
}
void listDeleteByKey(int key)
{
if(isEmpty())
{
printf("List is Empty\n");
}
else
{
struct node *prev = NULL;
current = start;
while(current != NULL)
{
if(current->key == key)
{
if(prev == NULL)
{
start = current->next;
}
else
{
prev->next = current->next;
}
break;
}
prev = current;
current = current->next;
}
if(current == NULL)
printf("Key NOT FOUND\n");
}
}
void listDeleteByData(int data)
{
if(isEmpty())
{
printf("List is Empty\n");
}
else
{
struct node *prev = NULL;
current = start;
while(current != NULL)
{
if(current->data == data)
{
if(prev == NULL)
{
start = current->next;
}
else
{
prev->next = current->next;
}
break;
}
prev = current;
current = current->next;
}
if(current == NULL)
printf("Data NOT FOUND\n");
}
}
bool findByKey(int key)
{
if(isEmpty())
{
printf("List is Empty\n");
}
else
{
current = start;
while(current != NULL)
{
if(current->key == key)
{
return true;
}
current = current->next;
}
return false;
}
}
bool findByData(int data)
{
if(isEmpty())
{
printf("List is Empty\n");
}
else
{
current = start;
while(current != NULL)
{
if(current->data == data)
{
return true;
}
current = current->next;
}
return false;
}
}
int main()
{
int c, choice, v;
bool exit_flag = false;
while(true)
{
printf("Enter Choice:\n");
printf("1\t-\tDisplay\n");
printf("2\t-\tSearch\n");
printf("3\t-\tInsert\n");
printf("4\t-\tDelete\n");
printf("5\t-\tUpdate\n");
printf("0\t-\tExit\n");
scanf("%d", &choice);
switch(choice)
{
case 1://display
showList();
break;
case 2://search
printf("1 - By Key\n");
printf("2 - By Data\n");
scanf("%d", &c);
if(c == 1)
{
printf("Enter Key to Search: ");
scanf("%d", &v);
if(findByKey(v))
printf("Key %d FOUND!\n", v);
else
printf("Key %d NOT FOUND!\n", v);
}
else if(c == 2)
{
printf("Enter Data to Search: ");
scanf("%d", &v);
if(findByData(v))
printf("Data %d FOUND!\n", v);
else
printf("Data %d NOT FOUND!\n", v);
}
else
printf("Invalid Choice\n");
break;
case 3://insert
printf("Enter (KEY, DATA): ");
scanf("%d %d", &c, &v);
listInsert(c, v);
printf("\nList after inserting (%d %d)\n", c, v);
showList();
printf("\n");
break;
case 4://delete
printf("1 - By Key\n");
printf("2 - By Data\n");
scanf("%d", &c);
if(c == 1)
{
printf("Enter Key to Delete: ");
scanf("%d", &v);
listDeleteByKey(v);
printf("\nList after deleting key %d\n", v);
showList();
printf("\n");
}
else if(c == 2)
{
printf("Enter Data to Delete: ");
scanf("%d", &v);
listDeleteByData(v);
printf("\nList after deleting data %d\n", v);
showList();
printf("\n");
}
else
printf("Invalid Choice\n");
break;
//case 5://update //Do it by yourself
// break;
case 0://exit
exit_flag = true;
break;
default:
printf("Invalid Choice\n");
}
if(exit_flag)
break;
}
return 0;
}