Linked Lists
Linked List is a very commonly used linear data structure which consists of group of nodes in a sequence.
Each node holds its own data and the address of the next node hence forming a chain like structure.
Linked Lists are used to create trees and graphs.
Application Of Linked List :
1. Linked lists are used to implement stacks, queues, graphs, etc.
2. Linked lists let you insert elements at the beginning and end of the list.
3. In Linked Lists we don’t need to know the size in advance.
Types of Linked Lists:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
1. Singly Linked List :
The operations we can perform on singly linked lists are insertion, deletion and traversal.
Singly linked lists contain nodes which have a data part as well as an address part i.e. next, which points to the next node in the sequence of nodes.
node means for example consider 1 box is called node . so we devide that box in two parts half part store data , and another half part store address of next block .
2. Doubly Linked List :
In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.
Take same above example in doubly Linked list instead of two parts we have 3 parts of box .
That means our node (box) is divided in 3 parts :
1. Address (This address is for previous box(node))
2. Data
3. Address (This address is for next node)
Circular Linked List :
In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
This is same like singly list but main difference is last box address part connect first box (node) .
The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player’s chance ends.
Why Linked List? :
Arrays can be used to store linear data of similar types, but arrays have the following limitations.
1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2. Insertion deletion operation is very costly in array because we have to lots of shifting and if suppose size of array is too large its storing 1 lakh record then how worst it is for sort we have to shift 1 lakh times .
For example, in a system, if we maintain a sorted list of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].
And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).
Note : Exam will not ask coding questions on data structure but you will get lots of benefits in CDAC so watch videos very carefully .
Linked List vs. Array :
Note : Exam will ask some objectives on this so read carefully .
1. An array is the data structure that contains a collection of similar type data elements whereas the Linked list is considered as non-primitive data structure contains a collection of unordered linked elements known as nodes.
2. In a linked list though, you have to start from the head and work your way through until you get to the fourth element.
3. Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower.
4. In the array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location within the square bracket.
5. Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.
6. Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.
7. In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.
9. Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.
10. The requirement of memory is less due to actual data being stored within the index in the array. As against, there is a need for more memory in Linked Lists due to storage of additional next and previous referencing elements.
11. In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list
Lets take an Programming example for singly list :
Write C Program for Singly Linked List Insert, Delete, Display and Count
* Remember in c we have learned every thing so i hope you can very easily understand below code . *
* Its very easy what we did here for each operation created one function and from our switch case we are
calling them . *
#include
#include
#include
struct node {
int value;
struct node *next;
};
void insert();
void display();
void delete();
int count();
typedef struct node DATA_NODE;
DATA_NODE *head_node, *first_node, *temp_node = 0, *prev_node, next_node;
int data;
int main() {
int option = 0;
printf("Singly Linked List Example - All Operations\n");
while (option < 5) { printf("\nOptions\n"); printf("1 : Insert into Linked List \n"); printf("2 : Delete from Linked List \n"); printf("3 : Display Linked List\n"); printf("4 : Count Linked List\n"); printf("Others : Exit()\n"); printf("Enter your option:"); scanf("%d", &option); switch (option) { case 1: insert(); break; case 2: delete(); break; case 3: display(); break; case 4: count(); break; default: break; } } return 0; } void insert() { printf("\nEnter Element for Insert Linked List : \n"); scanf("%d", &data); temp_node = (DATA_NODE *) malloc(sizeof (DATA_NODE)); temp_node->value = data;
if (first_node == 0) {
first_node = temp_node;
} else {
head_node->next = temp_node;
}
temp_node->next = 0;
head_node = temp_node;
fflush(stdin);
}
void delete() {
int countvalue, pos, i = 0;
countvalue = count();
temp_node = first_node;
printf("\nDisplay Linked List : \n");
printf("\nEnter Position for Delete Element : \n");
scanf("%d", &pos);
if (pos > 0 && pos <= countvalue) { if (pos == 1) { temp_node = temp_node -> next;
first_node = temp_node;
printf("\nDeleted Successfully \n\n");
} else {
while (temp_node != 0) {
if (i == (pos - 1)) {
prev_node->next = temp_node->next;
if(i == (countvalue - 1))
{
head_node = prev_node;
}
printf("\nDeleted Successfully \n\n");
break;
} else {
i++;
prev_node = temp_node;
temp_node = temp_node -> next;
}
}
}
} else
printf("\nInvalid Position \n\n");
}
void display() {
int count = 0;
temp_node = first_node;
printf("\nDisplay Linked List : \n");
while (temp_node != 0) {
printf("# %d # ", temp_node->value);
count++;
temp_node = temp_node -> next;
}
printf("\nNo Of Items In Linked List : %d\n", count);
}
int count() {
int count = 0;
temp_node = first_node;
while (temp_node != 0) {
count++;
temp_node = temp_node -> next;
}
printf("\nNo Of Items In Linked List : %d\n", count);
return count;
}
Queue
A queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.
Queue follows the First In First Out(FIFO) rule – the item that goes in first is the item that comes out first too.
What Is Queue :
In programming terms, putting an item in the queue is called an “enqueue” and removing an item from the queue is called “dequeue”.
Enqueue: Add element to end of queue .
Dequeue: Remove element from front of queue.
IsEmpty: Check if queue is empty.
IsFull: Check if queue is full.
Peek: Get the value of the front of queue without removing it.
How Queue Works ? :
Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue.
When initializing the queue, we set the value of FRONT and REAR to -1.
On enqueing an element, we increase the value of REAR index and place the new element in the position pointed to by REAR.
On dequeueing an element, we return the value pointed to by FRONT and increase the FRONT index.
Before enqueing, we check if queue is already full.
Before dequeuing, we check if queue is already empty.
When enqueing the first element, we set the value of FRONT to 0.
When dequeing the last element, we reset the values of FRONT and REAR to -1.
Implementation using C programming :
#include<stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main()
{
//deQueue is not possible on empty queue
deQueue();
//enQueue 5 elements
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
//6th element can't be added to queue because queue is full
enQueue(6);
display();
//deQueue removes element entered first i.e. 1
deQueue();
//Now we have just 4 elements
display();
return 0;
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!");
else {
if(front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void deQueue(){
if(front == -1)
printf("\nQueue is Empty!!");
else{
printf("\nDeleted : %d", items[front]);
front++;
if(front > rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",items[i]);
}
}
Note : Please dont skip any videos think like you are in classroom so you cant miss it . this Tutorial are very very great available on internet . Please let me know if you have any doubts