Priority Queue is more specialized data structure than Queue. Like ordinary queue, priority queue has same method but with a major difference. In Priority queue items are ordered by key value so that item with the lowest value of key is at front and item with the highest value of key is at rear or vice versa. So we’re assigned priority to item based on its key value. Lower the value, higher the priority. Following are the principal methods of a Priority Queue.
Basic Operations
insert / enqueue − add an item to the rear of the queue.
remove / dequeue − remove an item from the front of the queue.
Priority Queue Representation
We’re going to implement Queue using array in this article. There is few more operations supported by queue which are following.
Peek − get the element at front of the queue.
isFull − check if queue is full.
isEmpty − check if queue is empty.
Insert / Enqueue Operation
Whenever an element is inserted into queue, priority queue inserts the item according to its order. Here we’re assuming that data with high value has low priority.
voidinsert(int data){int i =0;if(!isFull()){// if queue is empty, insert the data if(itemCount ==0){
intArray[itemCount++]= data;}else{// start from the right end of the queue for(i = itemCount -1; i >=0; i--){// if data is larger, shift existing item to right end if(data > intArray[i]){
intArray[i+1]= intArray[i];}else{break;}}// insert the data
intArray[i+1]= data;
itemCount++;}}}
Remove / Dequeue Operation
Whenever an element is to be removed from queue, queue get the element using item count. Once element is removed. Item count is reduced by one.
intremoveData(){return intArray[--itemCount];}
Demo Program
PriorityQueueDemo.c
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>#define MAX 6int intArray[MAX];int itemCount =0;intpeek(){return intArray[itemCount -1];}
bool isEmpty(){return itemCount ==0;}
bool isFull(){return itemCount == MAX;}intsize(){return itemCount;}voidinsert(int data){int i =0;if(!isFull()){// if queue is empty, insert the data if(itemCount ==0){
intArray[itemCount++]= data;}else{// start from the right end of the queue for(i = itemCount -1; i >=0; i--){// if data is larger, shift existing item to right end if(data > intArray[i]){
intArray[i+1]= intArray[i];}else{break;}}// insert the data
intArray[i+1]= data;
itemCount++;}}}intremoveData(){return intArray[--itemCount];}intmain(){/* insert 5 items */insert(3);insert(5);insert(9);insert(1);insert(12);// ------------------// index : 0 1 2 3 4 // ------------------// queue : 12 9 5 3 1 insert(15);// ---------------------// index : 0 1 2 3 4 5 // ---------------------// queue : 15 12 9 5 3 1if(isFull()){printf("Queue is full!\n");}// remove one item int num =removeData();printf("Element removed: %d\n",num);// ---------------------// index : 0 1 2 3 4 // ---------------------// queue : 15 12 9 5 3 // insert more itemsinsert(16);// ----------------------// index : 0 1 2 3 4 5// ----------------------// queue : 16 15 12 9 5 3// As queue is full, elements will not be inserted. insert(17);insert(18);// ----------------------// index : 0 1 2 3 4 5// ----------------------// queue : 16 15 12 9 5 3printf("Element at front: %d\n",peek());printf("----------------------\n");printf("index : 5 4 3 2 1 0\n");printf("----------------------\n");printf("Queue: ");while(!isEmpty()){int n =removeData();printf("%d ",n);}}
If we compile and run the above program then it would produce following result −
Queue is full!
Element removed: 1
Element at front: 3
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 3 5 9 12 15 16
A queue is an abstract data structure that contains a collection of elements. Queue implements the FIFO mechanism i.e the element that is inserted first is also deleted first.
Queue can be one linear data structure. But it may create some problem if we implement queue using array. Sometimes by using some consecutive insert and delete operation, the front and rear position will change. In that moment, it will look like the queue has no space to insert elements into it.
Even if there are some free spaces, that will not be used due to some logical problems. To overcome this problem, we will use the circular queue data structure.
What is Circular Queue?
A circular queue is a type of queue in which the last position is connected back to the first position to make a circle. It is also known as a Ring Buffer. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using a circular queue, we can use the space to insert elements.
It is a linear data structure that follows the FIFO mechanism. The circular queue is a more efficient way to implement a queue in a fixed size array. In a circular queue, the last element points to the first element making a circular link.
Representation of Circular Queue
Following is the representation of a circular queue, where the front is the index of the first element, and the rear is the index of the last element.
Operations on Circular Queue
There are mainly four operations that can be performed on a circular queue:
Enqueue: Insert an element into the circular queue.
Dequeue: Delete an element from the circular queue.
Front: Get the front element from the circular queue.
Rear: Get the last element from the circular queue.
Circular Queue using Array
Following is the implementation of a circular queue using an array:
Enqueue Operation on Circular Queue
Enqueue operation is used for inserting an element into the circular queue. The steps to perform the enqueue operation are as follows:
Algorithm for Enqueue Operation
Following are the steps to perform the enqueue operation on a circular queue:
1.Initialize an array or any data structure to store the elements of the circular queue.
2.Initialize two variables front and rear.
3.Check if the circular queue is full.
4.If it is not full, and if the front is -1, set the front to 0.
5.Increment the rear by 1 and store it in the rear index.
6.Update the rear index using rear = (rear + 1) % SIZE.
We have provided the implementation of Enqueue operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
Dequeue operation is used for deleting an element from the circular queue. The steps to perform the dequeue operation are as follows:
Algorithm for Dequeue Operation
Following are the steps to perform the dequeue operation on a circular queue:
1.Check if the circular queue is empty.
2.If the queue is not empty, store the element at the front index.
3.If the front and rear are equal, set the front and rear to -1.
4.Else, increase the front index by 1 using the formula front = (front + 1) % SIZE.
5.At last print the deleted element.
We have provided the implementation of Dequeue operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
Code for Dequeue Operation in Circular Queue
Following are the programs to remove a element from the circular queue −
Front operation is used to get the front element from the circular queue. The steps to perform the front operation are as follows:
Algorithm for Front Operation
1.Check if the circular queue is empty.
2.If not empty, print the front index element/
We have provided the implementation of Front operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
Code for Front Operation in Circular Queue
Following are the programs to look at the front element of the circular queue −
Rear operation is used to get the last element from the circular queue. The steps to perform the rear operation are as follows:
Algorithm for Rear Operation
1.Check if the circular queue is empty..
2.If it is not empty, print the element at the rear index.
We have provided the implementation of Rear operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
Code for Rear Operation in Circular Queue
Following are the programs to looka at the rear element−
//C Program#include <stdio.h>#include <stdlib.h>structNode{int data;structNode* link;};structNode* front =NULL;structNode* rear =NULL;// Check if the queue is emptyintisEmpty(){return front ==NULL;}// Adding an elementvoidenQueue(int value){structNode* newNode =(structNode*)malloc(sizeof(structNode));
newNode->data = value;
newNode->link =NULL;if(isEmpty()){
front = newNode;}else{
rear->link = newNode;}
rear = newNode;
rear->link = front;printf("\n Inserted -> %d", value);}// Deleting an elementintdeQueue(){int value;if(isEmpty()){printf("\n Queue is Empty!!");return-1;}else{structNode* temp = front;
value = temp->data;if(front == rear){
front = rear =NULL;}else{
front = front->link;
rear->link = front;}free(temp);return value;}}// Display the queuevoiddisplay(){structNode* temp = front;if(isEmpty()){printf("\n Queue is Empty!!\n");}else{printf("\n Front -> ");do{printf("%d ", temp->data);
temp = temp->link;}while(temp != front);printf("\n");}}intmain(){enQueue(14);enQueue(22);enQueue(6);// Display elements present in the queueprintf("Initial Queue ");display();// Deleting elements from queueprintf("\nElement Removed = %d",deQueue());// Display elements present in the queueprintf("\nQueue after deletion an element: ");display();// Inserting elements to queueenQueue(9);//Showing the rear of the queueprintf("\nRear Element = %d", rear->data);enQueue(20);//Showing the front of the queueprintf("\nFront Element = %d", front->data);printf("\nFinal Queue ");display();return0;}
Output
The output obtained is as follows −
Inserted -> 14
Inserted -> 22
Inserted -> 6Initial Queue
Front -> 14 22 6
Element Removed = 14
Queue after deletion an element:
Front -> 22 6
Inserted -> 9
Rear Element = 9
Inserted -> 20
Front Element = 22
Final Queue
Front -> 22 6 9 20
Time Complexity of Circular Queue
Following are the time complexities of the circular queue:
Enqueue Operation: The time complexity of the enQueue operation is O(1) as we can insert an element at the rear end of the queue in constant time.
Dequeue Operation: The time complexity of the deQueue operation is O(1) as we can delete an element from the front end of the queue in constant time.
Front Operation: The time complexity of the front operation is O(1) as we can get the front element of the queue in constant time.
Rear Operation: The time complexity of the rear operation is O(1) as we can get the rear element of the queue in constant time.
Applications of Circular Queue
Following are some of the applications of a circular queue:
Memory Management: Circular queues are used in memory management to manage the memory efficiently. It is used to allocate memory to the processes when they are in need of memory.
Buffer Management: These queues are also useful in buffer management. Consider a situation where data is produced at a faster rate than it is consumed. In such cases, a circular queue is used to store the data temporarily.
Operating System: Suppose your system has a lot of processes to execute. In such cases, for the better management of processes, the operating system uses a circular queue to allocate the CPU to the processes.
Traffic Management: Traffic singals are controlled by the circular queue. Let’s say there are three signals, red, yellow, and green. The signals are in a circular queue. When the green signal is on, the next signal will be yellow, and then red. This process will continue in a circular manner.
Multimedia Player: When we play songs in a multimedia player, the songs are played in a circular manner. Once the last song is played, the first song will be played next. This is done using a circular queue.
In general, when certain tasks are repeated in a circular manner, a circular queue is used to manage the tasks efficiently. Also, when the data is produced at a faster rate than it is consumed, a circular queue is used to store the data temporarily.
A queue is a linear data structure where elements are stored in the FIFO (First In First Out) principle where the first element inserted would be the first element to be accessed. A queue is an Abstract Data Type (ADT) similar to stack, the thing that makes queue different from stack is that a queue is open at both its ends. The data is inserted into the queue through one end and deleted from it using the other end. Queue is very frequently used in most programming languages.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.
Representation of Queues
Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked lists, or pointers. As a small example in this tutorial, we implement queues using a one-dimensional array.
Basic Operations in Queue
Queue operations also include initialization of a queue, usage and permanently deleting the data from the memory.
The most fundamental operations in the queue ADT include: enqueue(), dequeue(), peek(), isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the queue.
Queue uses two pointers − front and rear. The front pointer accesses the data from the front end (helping in enqueueing) while the rear pointer accesses data from the rear end (helping in dequeuing).
Queue Insertion Operation: Enqueue()
The enqueue() is a data manipulation operation that is used to insert elements into the stack. The following algorithm describes the enqueue() operation in a simpler way.
Algorithm
1. START
2. Check if the queue is full.
3. If the queue is full, produce overflow error and exit.
4. If the queue is not full, increment rear pointer to point
the next empty space.
5. Add data element to the queue location, where the rear
is pointing.
6. return success.
7. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>#define MAX 6int intArray[MAX];int front =0;int rear =-1;int itemCount =0;
bool isFull(){return itemCount == MAX;}
bool isEmpty(){return itemCount ==0;}intremoveData(){int data = intArray[front++];if(front == MAX){
front =0;}
itemCount--;return data;}voidinsert(int data){if(!isFull()){if(rear == MAX-1){
rear =-1;}
intArray[++rear]= data;
itemCount++;}}intmain(){insert(3);insert(5);insert(9);insert(1);insert(12);insert(15);printf("Queue: ");while(!isEmpty()){int n =removeData();printf("%d ",n);}}
Output
Queue: 3 5 9 1 12 15
Queue Deletion Operation: dequeue()
The dequeue() is a data manipulation operation that is used to remove elements from the stack. The following algorithm describes the dequeue() operation in a simpler way.
Algorithm
1. START
2. Check if the queue is empty.
3. If the queue is empty, produce underflow error and exit.
4. If the queue is not empty, access the data where front
is pointing.
5. Increment front pointer to point to the next available
data element.
6. Return success.
7. END
Example
Following are the implementations of this operation in various programming languages −
The peek() is an operation which is used to retrieve the frontmost element in the queue, without deleting it. This operation is used to check the status of the queue with the help of the pointer.
Algorithm
1. START
2. Return the element at the front of the queue
3. END
Example
Following are the implementations of this operation in various programming languages −
An expression is any word or group of words or symbols that generates a value on evaluation. Parsing expression means analyzing the expression for its words or symbols depending on a particular criterion. Expression parsing is a term used in a programming language to evaluate arithmetic and logical expressions.
The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression. These notations are −
Infix Notation
Prefix (Polish) Notation
Postfix (Reverse-Polish) Notation
These notations are named as how they use operator in expression. We shall learn the same here in this chapter.
Infix Notation
We write expression in infix notation, e.g. a – b + c, where operators are used in-between operands. It is easy for us humans to read, write, and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption.
Prefix Notation
In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known as Polish Notation.
Postfix Notation
This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is equivalent to its infix notation a + b.
The following table briefly tries to show the difference in all three notations −
Sr.No.
Infix Notation
Prefix Notation
Postfix Notation
1
a + b
+ a b
a b +
2
(a + b) ∗ c
∗ + a b c
a b + c ∗
3
a ∗ (b + c)
∗ a + b c
a b c + ∗
4
a / b + c / d
+ / a b / c d
a b / c d / +
5
(a + b) ∗ (c + d)
∗ + a b + c d
a b + c d + ∗
6
((a + b) ∗ c) – d
– ∗ + a b c d
a b + c ∗ d –
Parsing Expressions
As we have discussed, it is not a very efficient way to design an algorithm or program to parse infix notations. Instead, these infix notations are first converted into either postfix or prefix notations and then computed.
To parse any arithmetic expression, we need to take care of operator precedence and associativity also.
Precedence
When an operand is in between two different operators, which operator will take the operand first, is decided by the precedence of an operator over others. For example −
As multiplication operation has precedence over addition, b * c will be evaluated first. A table of operator precedence is provided later.
Associativity
Associativity describes the rule where operators with the same precedence appear in an expression. For example, in expression a + b − c, both + and − have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c.
Precedence and associativity determines the order of evaluation of an expression. Following is an operator precedence and associativity table (highest to lowest) −
Sr.No.
Operator
Precedence
Associativity
1
Exponentiation ^
Highest
Right Associative
2
Multiplication ( ∗ ) & Division ( / )
Second Highest
Left Associative
3
Addition ( + ) & Subtraction ( − )
Lowest
Left Associative
The above table shows the default behavior of operators. At any point of time in expression evaluation, the order can be altered by using parenthesis. For example −
In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c.
Postfix Evaluation Algorithm
We shall now look at the algorithm on how to evaluate postfix notation −
Step 1. Scan the expression from left to right
Step 2. If it is an operand push it to stack
Step 3. If it is an operator pull operand from stack and
perform operation
Step 4. Store the output of step 3, back to stack
Step 5. Scan the expression until all operands are consumed
Step 6. Pop the stack and perform operation
Expression Parsing – Complete implementation
Following are the complete implementations of Expression Parsing (Conversion from infix notations to postfix notations) in various programming languages −
A stack is a linear data structure where elements are stored in the LIFO (Last In First Out) principle where the last element inserted would be the first element to be deleted. A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages. It is named stack because it has the similar operations as the real-world stacks, for example − a pack of cards or a pile of plates, etc.
Stack is considered a complex data structure because it uses other data structures for implementation, such as Arrays, Linked lists, etc.
Stack Representation
A stack allows all data operations at one end only. At any given time, we can only access the top element of a stack.
The following diagram depicts a stack and its operations −
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation.
Basic Operations on Stacks
Stack operations are usually performed for initialization, usage and, de-initialization of the stack ADT.
The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the stack.
Stack uses pointers that always point to the topmost element within the stack, hence called as the top pointer.
Stack Insertion: push()
The push() is an operation that inserts elements into the stack. The following is an algorithm that describes the push() operation in a simpler way.
Algorithm
1. Checks if the stack is full.
2. If the stack is full, produces an error and exit.
3. If the stack is not full, increments top to point next
empty space.
4. Adds data element to the stack location, where top
is pointing.
5. Returns success.
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>int MAXSIZE =8;int stack[8];int top =-1;/* Check if the stack is full*/intisfull(){if(top == MAXSIZE)return1;elsereturn0;}/* Function to insert into the stack */intpush(int data){if(!isfull()){
top = top +1;
stack[top]= data;}else{printf("Could not insert data, Stack is full.\n");}}/* Main function */intmain(){int i;push(44);push(10);push(62);push(123);push(15);printf("Stack Elements: \n");// print stack datafor(i =0; i <8; i++){printf("%d ", stack[i]);}return0;}
Output
Stack Elements:
44 10 62 123 15 0 0 0
Note − In Java we have used to built-in method push() to perform this operation.
Stack Deletion: pop()
The pop() is a data manipulation operation which removes elements from the stack. The following pseudo code describes the pop() operation in a simpler way.
Algorithm
1. Checks if the stack is empty.
2. If the stack is empty, produces an error and exit.
3. If the stack is not empty, accesses the data element at
which top is pointing.
4. Decreases the value of top by 1.
5. Returns success.
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>int MAXSIZE =8;int stack[8];int top =-1;/* Check if the stack is empty */intisempty(){if(top ==-1)return1;elsereturn0;}/* Check if the stack is full*/intisfull(){if(top == MAXSIZE)return1;elsereturn0;}/* Function to delete from the stack */intpop(){int data;if(!isempty()){
data = stack[top];
top = top -1;return data;}else{printf("Could not retrieve data, Stack is empty.\n");}}/* Function to insert into the stack */intpush(int data){if(!isfull()){
top = top +1;
stack[top]= data;}else{printf("Could not insert data, Stack is full.\n");}}/* Main function */intmain(){int i;push(44);push(10);push(62);push(123);push(15);printf("Stack Elements: \n");// print stack datafor(i =0; i <8; i++){printf("%d ", stack[i]);}/*printf("Element at top of the stack: %d\n" ,peek());*/printf("\nElements popped: \n");// print stack datawhile(!isempty()){int data =pop();printf("%d ",data);}return0;}
Note − In Java we are using the built-in method pop().
Retrieving topmost Element from Stack: peek()
The peek() is an operation retrieves the topmost element within the stack, without deleting it. This operation is used to check the status of the stack with the help of the top pointer.
Algorithm
1. START
2. return the element at the top of the stack
3. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>int MAXSIZE =8;int stack[8];int top =-1;/* Check if the stack is full */intisfull(){if(top == MAXSIZE)return1;elsereturn0;}/* Function to return the topmost element in the stack */intpeek(){return stack[top];}/* Function to insert into the stack */intpush(int data){if(!isfull()){
top = top +1;
stack[top]= data;}else{printf("Could not insert data, Stack is full.\n");}}/* Main function */intmain(){int i;push(44);push(10);push(62);push(123);push(15);printf("Stack Elements: \n");// print stack datafor(i =0; i <8; i++){printf("%d ", stack[i]);}printf("\nElement at top of the stack: %d\n",peek());return0;}
Output
Stack Elements:
44 10 62 123 15 0 0 0
Element at top of the stack: 15
Verifying whether the Stack is full: isFull()
The isFull() operation checks whether the stack is full. This operation is used to check the status of the stack with the help of top pointer.
Algorithm
1. START
2. If the size of the stack is equal to the top position of the stack,
the stack is full. Return 1.
3. Otherwise, return 0.
4. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>int MAXSIZE =8;int stack[8];int top =-1;/* Check if the stack is full */intisfull(){if(top == MAXSIZE)return1;elsereturn0;}/* Main function */intmain(){printf("Stack full: %s\n",isfull()?"true":"false");return0;}
Output
Stack full: false
Verifying whether the Stack is empty: isEmpty()
The isEmpty() operation verifies whether the stack is empty. This operation is used to check the status of the stack with the help of top pointer.
Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>int MAXSIZE =8;int stack[8];int top =-1;/* Check if the stack is empty */intisempty(){if(top ==-1)return1;elsereturn0;}/* Main function */intmain(){printf("Stack empty: %s\n",isempty()?"true":"false");return0;}
Output
Stack empty: true
Stack Complete implementation
Following are the complete implementations of Stack in various programming languages −
#include <stdio.h>int MAXSIZE =8;int stack[8];int top =-1;/* Check if the stack is empty */intisempty(){if(top ==-1)return1;elsereturn0;}/* Check if the stack is full */intisfull(){if(top == MAXSIZE)return1;elsereturn0;}/* Function to return the topmost element in the stack */intpeek(){return stack[top];}/* Function to delete from the stack */intpop(){int data;if(!isempty()){
data = stack[top];
top = top -1;return data;}else{printf("Could not retrieve data, Stack is empty.\n");}}/* Function to insert into the stack */intpush(int data){if(!isfull()){
top = top +1;
stack[top]= data;}else{printf("Could not insert data, Stack is full.\n");}}/* Main function */intmain(){push(44);push(10);push(62);push(123);push(15);printf("Element at top of the stack: %d\n",peek());printf("Elements: \n");// print stack datawhile(!isempty()){int data =pop();printf("%d\n",data);}printf("Stack full: %s\n",isfull()?"true":"false");printf("Stack empty: %s\n",isempty()?"true":"false");return0;}
Output
Element at top of the stack: 15
Elements:
15123
62
10
44
Stack full: false
Stack empty: true
Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list.
Singly Linked List as Circular
In singly linked list, the next pointer of the last node points to the first node.
Doubly Linked List as Circular
In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.
As per the above illustration, following are the important points to be considered.
The last link’s next points to the first link of the list in both cases of singly as well as doubly linked list.
The first link’s previous points to the last of the list in case of doubly linked list.
Basic Operations in Circular Linked List
Following are the important operations supported by a circular list.
insert − Inserts an element at the start of the list.
delete − Deletes an element from the start of the list.
display − Displays the list.
Circular Linked List – Insertion Operation
The insertion operation of a circular linked list only inserts the element at the start of the list. This differs from the usual singly and doubly linked lists as there is no particular starting and ending points in this list. The insertion is done either at the start or after a particular node (or a given position) in the list.
Algorithm
1. START
2. Check if the list is empty
3. If the list is empty, add the node and point the head
to this node
4. If the list is not empty, link the existing head as
the next node to the new node.
5. Make the new node as the new head.
6. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//display the listvoidprintList(){structnode*ptr = head;printf("\n[ ");//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}printf(" ]");}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Circular Linked List: ");//print listprintList();}
The Deletion operation in a Circular linked list removes a certain node from the list. The deletion operation in this type of lists can be done at the beginning, or a given position, or at the ending.
Algorithm
1. START
2. If the list is empty, then the program is returned.
3. If the list is not empty, we traverse the list using a
current pointer that is set to the head pointer and create
another pointer previous that points to the last node.
4. Suppose the list has only one node, the node is deleted
by setting the head pointer to NULL.
5. If the list has more than one node and the first node is to
be deleted, the head is set to the next node and the previous
is linked to the new head.
6. If the node to be deleted is the last node, link the preceding
node of the last node to head node.
7. If the node is neither first nor last, remove the node by
linking its preceding node to its succeeding node.
8. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;if(head->next == head){
head =NULL;return tempLink;}//mark next to first link as first
head = head->next;//return the deleted linkreturn tempLink;}//display the listvoidprintList(){structnode*ptr = head;//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Circular Linked List: ");//print listprintList();deleteFirst();printf("\nList after deleting the first item: ");printList();}
Output
Circular Linked List: (6,56) (5,40) (4,1) (3,30) (2,20)
List after deleting the first item: (5,40) (4,1) (3,30) (2,20)
Circular Linked List – Displaying the List
The Display List operation visits every node in the list and prints them all in the output.
Algorithm
1. START
2. Walk through all the nodes of the list and print them
3. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//display the listvoidprintList(){structnode*ptr = head;printf("\n[ ");//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}printf(" ]");}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Circular Linked List: ");//print listprintList();}
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}intlength(){int length =0;//if list is emptyif(head ==NULL){return0;}
current = head->next;while(current != head){
length++;
current = current->next;}return length;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;if(head->next == head){
head =NULL;return tempLink;}//mark next to first link as first
head = head->next;//return the deleted linkreturn tempLink;}//display the listvoidprintList(){structnode*ptr = head;printf("\n[ ");//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}printf(" ]");}intmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Original List: ");//print listprintList();while(!isEmpty()){structnode*temp =deleteFirst();printf("\nDeleted value:");printf("(%d,%d) ",temp->key,temp->data);}printf("\nList after deleting all items: ");printList();}
Output
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[ ]
Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, forward as well as backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
Prev − Each link of a linked list contains a link to the previous link called Prev.
Linked List − A Linked List contains the connection link to the first link called First and to the last link called Last.
Doubly Linked List Representation
As per the above illustration, following are the important points to be considered.
Doubly Linked List contains a link element called first and last.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Each link is linked with its previous link using its previous link.
The last link carries a link as null to mark the end of the list.
Basic Operations in Doubly Linked List
Following are the basic operations supported by a list.
Insertion − Adds an element at the beginning of the list.
Insert Last − Adds an element at the end of the list.
Insert After − Adds an element after an item of the list.
Deletion − Deletes an element at the beginning of the list.
Delete Last − Deletes an element from the end of the list.
Delete − Deletes an element from the list using the key.
Display forward − Displays the complete list in a forward manner.
Display backward − Displays the complete list in a backward manner.
Doubly Linked List – Insertion at the Beginning
In this operation, we create a new node with three compartments, one containing the data, the others containing the address of its previous and next nodes in the list. This new node is inserted at the beginning of the list.
Algorithm
1. START
2. Create a new node with three variables: prev, data, next.
3. Store the new data in the data variable
4. If the list is empty, make the new node as head.
5. Otherwise, link the address of the existing first node to the
next variable of the new node, and assign null to the prev variable.
6. Point the head to the new node.
7. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the doubly linked listvoidprintList(){structnode*ptr = head;while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("\nDoubly Linked List: ");printList();}
In this insertion operation, the new input node is added at the end of the doubly linked list; if the list is not empty. The head will be pointed to the new node, if the list is empty.
Algorithm
1. START
2. If the list is empty, add the node to the list and point
the head to it.
3. If the list is not empty, find the last node of the list.
4. Create a link between the last node in the list and the
new node.
5. The new node will point to NULL as it is the new last node.
6. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the doubly linked listvoidprintList(){structnode*ptr = head;while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}//insert link at the last locationvoidinsertLast(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//make link a new last link
last->next = link;//mark old last node as prev of new link
link->prev = last;}//point last to new last node
last = link;}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertLast(5,40);insertLast(6,56);printf("Doubly Linked List: ");printList();}
This deletion operation deletes the existing first nodes in the doubly linked list. The head is shifted to the next node and the link is removed.
Algorithm
1. START
2. Check the status of the doubly linked list
3. If the list is empty, deletion is not possible
4. If the list is not empty, the head pointer is
shifted to the next node.
5. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the doubly linked listvoidprintList(){structnode*ptr = head;while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;//if only one linkif(head->next ==NULL){
last =NULL;}else{
head->next->prev =NULL;}
head = head->next;//return the deleted linkreturn tempLink;}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Doubly Linked List: \n");printList();printf("\nList after deleting first record: \n");deleteFirst();printList();}
Output
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
List after deleting first record: (5,40) (4,1) (3,30) (2,20) (1,10)
Doubly Linked List – Complete Implementation
Following are the complete implementations of Doubly Linked List in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the list in from first to lastvoiddisplayForward(){//start from the beginningstructnode*ptr = head;//navigate till the end of the listprintf("\n[ ");while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}printf(" ]");}//display the list from last to firstvoiddisplayBackward(){//start from the laststructnode*ptr = last;//navigate till the start of the listprintf("\n[ ");while(ptr !=NULL){//print dataprintf("(%d,%d) ",ptr->key,ptr->data);//move to next item
ptr = ptr ->prev;printf(" ");}printf(" ]");}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}//insert link at the last locationvoidinsertLast(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//make link a new last link
last->next = link;//mark old last node as prev of new link
link->prev = last;}//point last to new last node
last = link;}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;//if only one linkif(head->next ==NULL){
last =NULL;}else{
head->next->prev =NULL;}
head = head->next;//return the deleted linkreturn tempLink;}//delete link at the last locationstructnode*deleteLast(){//save reference to last linkstructnode*tempLink = last;//if only one linkif(head->next ==NULL){
head =NULL;}else{
last->prev->next =NULL;}
last = last->prev;//return the deleted linkreturn tempLink;}//delete a link with given keystructnode*delete(int key){//start from the first linkstructnode* current = head;structnode* previous =NULL;//if list is emptyif(head ==NULL){returnNULL;}//navigate through listwhile(current->key != key){//if it is last nodeif(current->next ==NULL){returnNULL;}else{//store reference to current link
previous = current;//move to next link
current = current->next;}}//found a match, update the linkif(current == head){//change first to point to next link
head = head->next;}else{//bypass the current link
current->prev->next = current->next;}if(current == last){//change last to point to prev link
last = current->prev;}else{
current->next->prev = current->prev;}return current;}
bool insertAfter(int key,int newKey,int data){//start from the first linkstructnode*current = head;//if list is emptyif(head ==NULL){return false;}//navigate through listwhile(current->key != key){//if it is last nodeif(current->next ==NULL){return false;}else{//move to next link
current = current->next;}}//create a linkstructnode*newLink =(structnode*)malloc(sizeof(structnode));
newLink->key = key;
newLink->data = data;if(current == last){
newLink->next =NULL;
last = newLink;}else{
newLink->next = current->next;
current->next->prev = newLink;}
newLink->prev = current;
current->next = newLink;return true;}intmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("\nList (First to Last): ");displayForward();printf("\n");printf("\nList (Last to first): ");displayBackward();printf("\nList , after deleting first record: ");deleteFirst();displayForward();printf("\nList , after deleting last record: ");deleteLast();displayForward();printf("\nList , insert after key(4) : ");insertAfter(4,7,13);displayForward();printf("\nList , after delete key(4) : ");delete(4);displayForward();}
Output
List (First to Last):
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first):
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
List , after deleting first record:
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record:
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) :
[ (5,40) (4,1) (4,13) (3,30) (2,20) ]
List , after delete key(4) :
[ (5,40) (4,13) (3,30) (2,20) ]
A linked list is a linear data structure which can store a collection of “nodes” connected together via links i.e. pointers. Linked lists nodes are not stored at a contiguous location, rather they are linked using pointers to the different memory locations. A node consists of the data value and a pointer to the address of the next node within the linked list.
A linked list is a dynamic linear data structure whose memory size can be allocated or de-allocated at run time based on the operation insertion or deletion, this helps in using system memory efficiently. Linked lists can be used to implment various data structures like a stack, queue, graph, hash maps, etc.
A linked list starts with a head node which points to the first node. Every node consists of data which holds the actual data (value) associated with the node and a next pointer which holds the memory address of the next node in the linked list. The last node is called the tail node in the list which points to null indicating the end of the list.
Linked Lists vs Arrays
In case of arrays, the size is given at the time of creation and so arrays are of fixed lenghth where as Linked lists are dynamic in size and any number of nodes can be added in the linked lists dynamically. An array can accommodate similar types of data types where as linked lists can store various nodes of different data types.
Types of Linked List
Following are the various types of linked list.
Singly Linked Lists
Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.
Doubly Linked Lists
Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.
Circular Linked Lists
Circular linked lists can exist in both singly linked list and doubly linked list.
Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.
Basic Operations in Linked List
The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an element at a given key. These operations are performed on Singly Linked Lists as given below −
Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.
Linked List – Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.
Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −
NewNode.next -> RightNode;
It should look like this −
Now, the next node at the left should point to the new node.
LeftNode.next -> NewNode;
This will put the new node in the middle of the two. The new list should look like this −
Insertion in linked list can be done in three different ways. They are explained as follows −
Insertion at Beginning
In this operation, we are adding an element at the beginning of the list.Algorithm
1. START
2. Create a node to store the data
3. Check if the list is empty
4. If the list is empty, add the data to the node and
assign the head pointer to it.
5. If the list is not empty, add the data to a node and link to the
current head. Assign the head to the newly added node.
6. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(44);insertatbegin(50);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 50 44 30 22 12 ]
Insertion at Ending
In this operation, we are adding an element at the ending of the list.Algorithm
1. START
2. Create a new node and assign the data
3. Find the last node
4. Point the last node to new node
5. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidinsertatend(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;structnode*linkedlist = head;// point it to old first nodewhile(linkedlist->next !=NULL)
linkedlist = linkedlist->next;//point first to new first node
linkedlist->next = lk;}voidmain(){int k=0;insertatbegin(12);insertatend(22);insertatend(30);insertatend(44);insertatend(50);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 12 22 30 44 50 ]
Insertion at a Given Position
In this operation, we are adding an element at any position within the list.Algorithm
1. START
2. Create a new node and assign data to it
3. Iterate until the node at position is found
4. Point first to new first node
5. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidinsertafternode(structnode*list,int data){structnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;
lk->next = list->next;
list->next = lk;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertafternode(head->next,30);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 22 12 30 ]
Linked List – Deletion Operation
Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.
The left (previous) node of the target node now should point to the next node of the target node −
LeftNode.next -> TargetNode.next;
This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.
TargetNode.next -> NULL;
We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.
Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.
Deletion in linked lists is also performed in three different ways. They are as follows −
Deletion at Beginning
In this deletion operation of the linked, we are deleting an element from the beginning of the list. For this, we point the head to the second node.Algorithm
1. START
2. Assign the head pointer to the next node in the list
3. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voiddeleteatbegin(){
head = head->next;}intmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();deleteatbegin();printf("\nLinked List after deletion: ");// print listprintList();}
Output
Linked List:
[ 55 40 30 22 12 ]
Linked List after deletion:
[ 40 30 22 12 ]
Deletion at Ending
In this deletion operation of the linked, we are deleting an element from the ending of the list.Algorithm
1. START
2. Iterate until you find the second last element in the list.
3. Assign NULL to the second last element in the list.
4. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voiddeleteatend(){structnode*linkedlist = head;while(linkedlist->next->next !=NULL)
linkedlist = linkedlist->next;
linkedlist->next =NULL;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();deleteatend();printf("\nLinked List after deletion: ");// print listprintList();}
Output
Linked List:
[ 55 40 30 22 12 ]
Linked List after deletion:
[ 55 40 30 22 ]
Deletion at a Given Position
In this deletion operation of the linked, we are deleting an element at any position of the list.Algorithm
1. START
2. Iterate until find the current node at position in the list.
3. Assign the adjacent node of current node in the list
to its previous node.
4. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voiddeletenode(int key){structnode*temp = head,*prev;if(temp !=NULL&& temp->data == key){
head = temp->next;return;}// Find the key to be deletedwhile(temp !=NULL&& temp->data != key){
prev = temp;
temp = temp->next;}// If the key is not presentif(temp ==NULL)return;// Remove the node
prev->next = temp->next;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();deletenode(30);printf("\nLinked List after deletion: ");// print listprintList();}
Output
Linked List:
[ 55 40 30 22 12 ]
Linked List after deletion:
[ 55 40 22 12 ]
Linked List – Reversal Operation
This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −
We have to make sure that the last node is not the last node. So we’ll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.
Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.
We’ll make the head node point to the new first node by using the temp node.
Algorithm
Step by step process to reverse a linked list is as follows −
1. START
2. We use three pointers to perform the reversing:
prev, next, head.
3. Point the current node to head and assign its next value to
the prev node.
4. Iteratively repeat the step 3 for all the nodes in the list.
5. Assign head to the prev node.
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidreverseList(structnode** head){structnode*prev =NULL,*cur=*head,*tmp;while(cur!=NULL){
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;}*head = prev;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();reverseList(&head);printf("\nReversed Linked List: ");printList();}
Searching for an element in the list using a key element. This operation is done in the same way as array search; comparing every element in the list with the key element given.
Algorithm
1 START
2 If the list is not empty, iteratively check if the list
contains the key
3 If the key element is not present in the list, unsuccessful
search
4 END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}intsearchlist(int key){structnode*temp = head;while(temp !=NULL){if(temp->data == key){return1;}
temp=temp->next;}return0;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();int ele =30;printf("\nElement to be searched is: %d", ele);
k =searchlist(30);if(k ==1)printf("\nElement is found");elseprintf("\nElement is not found in the list");}
Output
Linked List:
[ 55 40 30 22 12 ]
Element to be searched is: 30
Element is found
Linked List – Traversal Operation
The traversal operation walks through all the elements of the list in an order and displays the elements in that order.
Algorithm
1. START
2. While the list is not empty and did not reach the end of the list,
print the data in each node
3. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 30 22 12 ]
Linked List – Complete implementation
Following are the complete implementations of Linked List in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidinsertatend(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;structnode*linkedlist = head;// point it to old first nodewhile(linkedlist->next !=NULL)
linkedlist = linkedlist->next;//point first to new first node
linkedlist->next = lk;}voidinsertafternode(structnode*list,int data){structnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;
lk->next = list->next;
list->next = lk;}voiddeleteatbegin(){
head = head->next;}voiddeleteatend(){structnode*linkedlist = head;while(linkedlist->next->next !=NULL)
linkedlist = linkedlist->next;
linkedlist->next =NULL;}voiddeletenode(int key){structnode*temp = head,*prev;if(temp !=NULL&& temp->data == key){
head = temp->next;return;}// Find the key to be deletedwhile(temp !=NULL&& temp->data != key){
prev = temp;
temp = temp->next;}// If the key is not presentif(temp ==NULL)return;// Remove the node
prev->next = temp->next;}intsearchlist(int key){structnode*temp = head;while(temp !=NULL){if(temp->data == key){return1;}
temp=temp->next;}return0;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatend(30);insertatend(44);insertatbegin(50);insertafternode(head->next->next,33);printf("Linked List: ");// print listprintList();deleteatbegin();deleteatend();deletenode(12);printf("\nLinked List after deletion: ");// print listprintList();insertatbegin(4);insertatbegin(16);printf("\nUpdated Linked List: ");printList();
k =searchlist(16);if(k ==1)printf("\nElement is found");elseprintf("\nElement is not present in the list");}
Output
Linked List:
[ 50 22 12 33 30 44 ]
Linked List after deletion:
[ 22 33 30 ]
Updated Linked List:
[ 16 4 22 33 30 ]
Element is found
Skip List is an advanced data structure that is used for storing a sorted list of elements.
Let’s suppose, you are working on a project called “Music Player”. You have a list of songs that you want to play in a specific order. You want to store these songs in a data structure that allows you to quickly search for a song, insert a new song, and delete a song. You also want to maintain the order of the songs. This is where the Skip List data structure comes in use.
What is a Skip List?
A Skip List is a data structure that help us to search, insert, and delete elements in a sorted list. It is similar to a linked list, but with additional pointers that allow us to skip over some elements. This makes searching for an element faster than a linked list.
A Skip List is a probabilistic data structure, which means that the structure of the list is determined by random choices. The Skip List is a versatile data structure that can be used in a variety of applications, such as databases, search engines, and network routing algorithms.
How does a Skip List work?
Skip list has multiple levels. The bottom level is a sorted linked list that contains all the elements. Then, each higher level contains a subset of the elements from the lower level. The higher levels have pointers that allow us to skip over some elements. This makes searching for an element faster than a linked list.
Representation of Skip List
A Skip List is represented as a series of linked lists, where each list is a level of the Skip List. Each node in the Skip List contains a key and a value. The key is used to sort the elements in the list, and the value is the data associated with the key.
Each node also contains pointers to the next node in the same level, and pointers to the next node in the level below. The top level of the Skip List contains only one node, which is the head of the list. The head node contains pointers to the first node in each level of the Skip List.
Types of Skip List
There are more than one type of Skip Lists:
Randomized Skip List: In a randomized skip list, the elements promoted to higher levels are chosen randomly. This makes the structure of the skip list unpredictable.
Deterministic Skip List:In the deterministic skip list, the elements promoted to higher levels are chosen based on a deterministic rule. This makes the structure of the skip list predictable. For example, in a deterministic skip list, every 2nd element is promoted to the next level.
Operations on Skip List
A Skip List supports the following operations:
Search: Search for an element in the Skip List.
Insert: Insert an element into the Skip List.
Delete: Delete an element from the Skip List.
Implementing a Skip List
A Skip List can be implemented using a linked list data structure. Each node in the Skip List contains a key, a value, and an array of pointers to the next node in each level. The Skip List also contains a head node that points to the first node in each level. Here is an example of a Skip List implemented in C, C++, Java and Python:
Algorithm to implement Skip List
In order to implement a Skip List, we need to follow these steps:
Create a Node structure, with key, value, and an array of pointers.Create a SkipList structure, with a head node and the level of the Skip List.Create a function to create a new node.Create a function to create a new Skip List.Create a function to generate a random level for a node.Create a function to insert a node into the Skip List.Create a function to display the Skip List.At last, create a main function to test the Skip List.
Example of Skip List
Following is an example of a Skip List implemented in C, C++, Java, and Python that demonstrates the insertion of elements into the Skip List and displays the Skip List:
Note: output may vary as the level of the Skip List is generated randomly.
Search Operation in Skip List
The search operation in a Skip List is similar to a linked list. We start from the top level and move to the next level if the key is greater than the current node. We continue this process until we find the key or reach the bottom level. If the key is found, we return the node; otherwise, we return NULL.
Algorithm
Following are steps to search for a key in a Skip List:
Start from the top level of the Skip List.Move to the next level if the key is greater than the current node.Continue this process until we find the key or reach the bottom level.If the key is found, return the node; otherwise, return NULL.
Example of Search Operation in Skip List
Let’s search for the key 12 in the Skip List. The search operation is as follows:
//C Program to search for a key in Skip List#include <stdio.h>#include <stdlib.h>#include <limits.h>#include <time.h>#define MAX_LEVEL 6// Node structurestructNode{int key;structNode*forward[MAX_LEVEL];};// SkipList structurestructSkipList{structNode*header;int level;};// Create a nodestructNode*createNode(int key,int level){structNode*newNode =(structNode*)malloc(sizeof(structNode));
newNode->key = key;for(int i =0; i < level; i++)
newNode->forward[i]=NULL;return newNode;}// Create a SkipListstructSkipList*createSkipList(){structSkipList*list =(structSkipList*)malloc(sizeof(structSkipList));
list->header =createNode(INT_MIN, MAX_LEVEL);
list->level =0;return list;}// Generate random level for nodeintrandomLevel(){int level =0;while(rand()< RAND_MAX /2&& level < MAX_LEVEL)
level++;return level;}// Search for a keystructNode*searchNode(structSkipList*list,int key){structNode*current = list->header;for(int i = list->level; i >=0; i--){while(current->forward[i]!=NULL&& current->forward[i]->key < key)
current = current->forward[i];}
current = current->forward[0];if(current !=NULL&& current->key == key)return current;returnNULL;}// create nodevoidinsertNode(structSkipList*list,int key){structNode*current = list->header;structNode*update[MAX_LEVEL];for(int i = list->level; i >=0; i--){while(current->forward[i]!=NULL&& current->forward[i]->key < key)
current = current->forward[i];
update[i]= current;}
current = current->forward[0];if(current ==NULL|| current->key != key){int rlevel =randomLevel();if(rlevel > list->level){for(int i = list->level +1; i <= rlevel; i++)
update[i]= list->header;
list->level = rlevel;}structNode*newNode =createNode(key, rlevel);for(int i =0; i <= rlevel; i++){
newNode->forward[i]= update[i]->forward[i];
update[i]->forward[i]= newNode;}}}intmain(){srand((unsigned)time(0));structSkipList*list =createSkipList();insertNode(list,3);insertNode(list,6);insertNode(list,7);insertNode(list,9);insertNode(list,12);insertNode(list,19);insertNode(list,17);insertNode(list,26);insertNode(list,21);insertNode(list,25);structNode*node =searchNode(list,12);if(node !=NULL)printf("Key found: %d\n", node->key);elseprintf("Key not found\n");return0;}
Output
The output obtained is as follows −
Key found: 12
Delete Operation in Skip List
The delete operation in a Skip List is similar to a linked list. We search for the key to be deleted and update the pointers to remove the node from the list. The delete operation is as follows:
Algorithm
Following are the steps to delete a key in a Skip List:
Search for the key to be deleted in the Skip List.Update the pointers to remove the node from the list.Repeat this process for all levels of the Skip List.
Example of Delete Operation in Skip List
Let’s delete the key 12 from the Skip List. The delete operation is as follows:
The time complexity of search, insert, and delete operations in a Skip List is O(log n) on average.
The time complexity of these operations is the same as that of a balanced binary search tree.
The space complexity of a Skip List is O(n).
Applications of Skip List
The Skip List data structure is used in the following applications:
Database Indexing: Skip Lists are used in databases to index data efficiently.
Search Engines: Skip Lists are also used in search engines to store and retrieve web pages.
Network Routing Algorithms: This data structure also used in network routing algorithms to find the shortest path between two nodes.
Advantages of Skip List
Following are the advantages of Skip List −
Efficient Operations: Skip Lists provide efficient search, insert, and delete operations.
Simple Implementation: Skip Lists are easy to implement compared to other data structures like AVL trees and Red-Black trees.
Space Efficiency: Skip Lists are space-efficient and require less memory compared to other data structures.
Disadvantages of Skip List
Following are the disadvantages of Skip List −
Complexity: Skip Lists are complex data structures compared to linked lists.
Randomness: The performance of Skip Lists depends on the randomness of the levels.
Conclusion
In this tutorial, we learned about the Skip List data structure, its operations, and its implementation in C, C++, Java, and Python. Skip Lists are efficient data structures that provide fast search, insert, and delete operations. Skip Lists are used in various applications like database indexing, search engines, and network routing algorithms.
An array is a type of linear data structure that is defined as a collection of elements with same or different data types. They exist in both single dimension and multiple dimensions. These data structures come into picture when there is a necessity to store multiple elements of similar nature together at one place.
The difference between an array index and a memory address is that the array index acts like a key value to label the elements in the array. However, a memory address is the starting address of free memory available.
Following are the important terms to understand the concept of Array.
Element − Each item stored in an array is called an element.
Index − Each location of an element in an array has a numerical index, which is used to identify the element.
Syntax
Creating an array in C and C++ programming languages −
data_type array_name[array_size]={elements separated by commas}
or,
data_type array_name[array_size];
Arrays are used as solutions to many problems from the small sorting problems to more complex problems like travelling salesperson problem. There are many data structures other than arrays that provide efficient time and space complexity for these problems, so what makes using arrays better? The answer lies in the random access lookup time.
Arrays provide O(1) random access lookup time. That means, accessing the 1st index of the array and the 1000th index of the array will both take the same time. This is due to the fact that array comes with a pointer and an offset value. The pointer points to the right location of the memory and the offset value shows how far to look in the said memory.
array_name[index]
| |
Pointer Offset
Therefore, in an array with 6 elements, to access the 1st element, array is pointed towards the 0th index. Similarly, to access the 6th element, array is pointed towards the 5th index.
Array Representation
Arrays are represented as a collection of buckets where each bucket stores one element. These buckets are indexed from ‘0’ to ‘n-1’, where n is the size of that particular array. For example, an array with size 10 will have buckets indexed from 0 to 9.
This indexing will be similar for the multidimensional arrays as well. If it is a 2-dimensional array, it will have sub-buckets in each bucket. Then it will be indexed as array_name[m][n], where m and n are the sizes of each level in the array.
As per the above illustration, following are the important points to be considered.
Index starts with 0.
Array length is 9 which means it can store 9 elements.
Each element can be accessed via its index. For example, we can fetch an element at index 6 as 23.
Basic Operations in Arrays
The basic operations in the Arrays are insertion, deletion, searching, display, traverse, and update. These operations are usually performed to either modify the data in the array or to report the status of the array.
Following are the basic operations supported by an array.
Traverse − print all the array elements one by one.
Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
Display − Displays the contents of the array.
In C, when an array is initialized with size, then it assigns defaults values to its elements in following order.
Data Type
Default Value
bool
false
char
0
int
0
float
0.0
double
0.0f
void
wchar_t
0
Array – Insertion Operation
In the insertion operation, we are adding one or more elements to the array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array. This is done using input statements of the programming languages.
Algorithm
Following is an algorithm to insert elements into a Linear Array until we reach the end of the array −
1. Start
2. Create an Array of a desired datatype and size.
3. Initialize a variable 'i' as 0.
4. Enter the element at ith index of the array.
5. Increment i by 1.
6. Repeat Steps 4 & 5 until the end of the array.
7. Stop
Example
Here, we see a practical implementation of insertion operation, where we add data at the end of the array −
#include <stdio.h>intmain(){int LA[3]={}, i;printf("Array Before Insertion:\n");for(i =0; i <3; i++)printf("LA[%d] = %d \n", i, LA[i]);printf("Inserting Elements.. \n");printf("The array elements after insertion :\n");// prints array valuesfor(i =0; i <3; i++){
LA[i]= i +2;printf("LA[%d] = %d \n", i, LA[i]);}return0;}
For other variations of array insertion operation, click here.
Array – Deletion Operation
In this array operation, we delete an element from the particular index of an array. This deletion operation takes place as we assign the value in the consequent index to the current index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to delete an element available at the Kth position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>voidmain(){int LA[]={1,3,5};int n =3;int i;printf("The original array elements are :\n");for(i =0; i<n; i++)printf("LA[%d] = %d \n", i, LA[i]);for(i =1; i<n; i++){
LA[i]= LA[i+1];
n = n -1;}printf("The array elements after deletion :\n");for(i =0; i<n; i++)printf("LA[%d] = %d \n", i, LA[i]);}
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
The array elements after deletion :
LA[0] = 1
LA[1] = 5
Array – Search Operation
Searching an element in the array using a key; The key element sequentially compares every value in the array to check if the key is present in the array or not.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to find an element with a value of ITEM using sequential search.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>voidmain(){int LA[]={1,3,5,7,8};int item =5, n =5;int i =0, j =0;printf("The original array elements are :\n");for(i =0; i<n; i++){printf("LA[%d] = %d \n", i, LA[i]);}for(i =0; i<n; i++){if( LA[i]== item ){printf("Found element %d at position %d\n", item, i+1);}}}
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
Array – Traversal Operation
This operation traverses through all the elements of an array. We use loop statements to carry this out.
Algorithm
Following is the algorithm to traverse through all the elements present in a Linear Array −
1 Start
2. Initialize an Array of certain size and datatype.
3. Initialize another variable i with 0.
4. Print the ith value in the array and increment i.
5. Repeat Step 4 until the end of the array is reached.
6. End
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>intmain(){int LA[]={1,3,5,7,8};int item =10, k =3, n =5;int i =0, j = n;printf("The original array elements are :\n");for(i =0; i<n; i++){printf("LA[%d] = %d \n", i, LA[i]);}}
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Array – Update Operation
Update operation refers to updating an existing element from the array at a given index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to update an element available at the Kth position of LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>voidmain(){int LA[]={1,3,5,7,8};int k =3, n =5, item =10;int i, j;printf("The original array elements are :\n");for(i =0; i<n; i++){printf("LA[%d] = %d \n", i, LA[i]);}
LA[k-1]= item;printf("The array elements after updation :\n");for(i =0; i<n; i++){printf("LA[%d] = %d \n", i, LA[i]);}}
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
Array – Display Operation
This operation displays all the elements in the entire array using a print statement.
Algorithm
Consider LA is a linear array with N elements. Following is the algorithm to display an array elements.
1. Start
2. Print all the elements in the Array
3. Stop
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>intmain(){int LA[]={1,3,5,7,8};int n =5;int i;printf("The original array elements are :\n");for(i =0; i<n; i++){printf("LA[%d] = %d \n", i, LA[i]);}}
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
