Introduction to data structures - Explore the basics

1.C Hello World Program 2.C Program to Print an Integer Entered By the User 3.C Program to Add Two Numbers 4.C Program to Multiply two Floating-Point Numbers 5.C Program to Print the ASCII Value of a Character 6.C Program to Swap Two Numbers 7.C Program to Find the Size of int, float, double, and char 8.C Program to Make a Simple Calculator 9.C Program to Print Hollow Star Pyramid in a Diamond Shape 10.C Program to Print Full Diamond Shape Pyramid 11.C Program to Display Prime Numbers Between Two Intervals Using Functions 12.C Program to Print a 2D Array 13.C Program to Find the Largest Element in an Array 14.C Program to Find the Maximum and Minimum in an Array

Data Structure can be defined as the group of data elements which provides an efficient way of storing and organizing data in the computer so that it can be used efficiently. examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in almost every aspect of Computer Science i.e. Operating System, Compiler Design, Artificial intelligence, Graphics and many more. Data Structures are the main part of many computer science algorithms as they enable the programmers to handle the data in an efficient way. It plays a vital role in enhancing the performance of a software or a program as the main function of the software is to store and retrieve the user’s data as fast as possible  Data Structure= Organized Data + Allowed Operations What is Data Structure

Data Structure  A data structure is a particular way of organizing data in a computer so that it can be used effectively.  For example, we can store a list of items having the same data-type using the array data structure.

The representation of particular data structure in the main memory of a computer is called as storage structure. The storage structure representation in auxiliary memory is called as file structure. It is define as the way of storing and manipulating data in organized form so that it can be used efficiently Data Structure mainly specifies the following four things: 1)organization of data 2)accessing method 3)degree of associativity 4) processing alternative for information Algorithm + Data Structure = Program Data Structure study Covers the following points 1) Amount of memory require to store 2) Amount of time require to process 3) Representation of data in memory

Types Of DS The DS are divided into two types: 1) Primitive (built in) 2) Non primitive(user defined) Non primitive divided into two type 3) Linear DS 4) Non linear DS

Applications of Arrays  Arrays Arrangement of leader-board of a game can be done simply through arrays to store the score and arrange them in descending order to clearly make out the rank of each player in the game. 2D arrays, commonly known as, matrix, are used in image processing. It is also used in speech processing, in which each speech signal is an array.

Applications of the linked list 1.Images in a location are linked with each other. So, an image viewer software uses a linked list to view the previous and the next images using the previous and next buttons. 2.Web pages can be accessed using the previous and the next URL links which are linked using linked list. 3.The music players also use the same technique to switch between music. 4.To keep the track of turns in a multi player game, a circular linked list is used.

Applications of a stack Some Applications of a stack are: 1.Undo operation is also carried out through stacks. 2.Forward – backward surfing in browser 3.History of visited websites 4.Message logs and all messages you get are arranged in stack 5.Call logs, E-mails, Google photos’ any gallery , YouTube downloads, Notifications ( latest appears first ) 6.Syntaxes in languages are parsed using stacks. 7.Converting infix to postfix expressions.

Applications of Queue 1. Operating System uses queue for job scheduling. 2. To handle congestion in networking queue can be used. 3. Data packets in communication are arranged in queue format. 4. Sending an E-mail, it will be queued 5. server while responding request 6. Uploading and downloading photo’s, first kept for uploading/downloading will completed first (Not if there is threading) 7. Most of internet requests and processes uses queue 8. While switching multiple applications, windows uses circular queue.

Applications of a Graph 1.Facebook’s Graph API uses the structure of Graphs. (The Graph API is the primary way to get data into and out of the Facebook platform. It's an HTTP-based API that apps can use to programmatically query data, post new stories, manage ads, upload photos, and perform a wide variety of other tasks.) 2.Google’s Knowledge Graph also has to do something with Graph. ( knowledge base that represents semantic relations between concepts in a network.) 3.GPS navigation system also uses shortest path APIs. 4.Networking components has huge application of graph 5.Facebook, Instagram and all social media networking sites every user is Node 6.Data organization

Applications of the trees 1.XML Parser uses tree algorithms. 2.Decision-based algorithm is used in machine learning which works upon the algorithm of tree. 3.Databases also uses tree data structures for indexing. 4.Domain Name Server(DNS) also uses tree structures. 5.File explorer/my computer of mobile/any computer 6.BST used in computer Graphics 7.Posting questions on websites like Quora, the comments are child of questions

DATA TYPES A particular kind of data item, as defined by the values it can take, the Programming language used, or the operations that can be performed on it. Primitive Data Structure  Primitive Data Structure are basic structure and directly operated upon by machine instructions.  Primitive data structures have different representations on different computers.  Integers, floats, character and pointers are example of primitive data structures.  These data types are available in most programming languages as built in type. Integer: It is a data type which allows all values without fraction part. We can used it for whole numbers. Float: It is a data type which is use for storing fraction numbers. Character: It is a data type which is used for character values. Pointer: A variable that hold memory address of

Non Primitive Data Type  These are more sophisticated data structures.  These are derived from primitive data structure.  The non – primitive data structures emphasize structuring of a group of homogeneous or heterogeneous data items.  Example of non – primitive data types are Array, List, and File etc.  A non – primitive data type is further divided into Linear and non – Linear data structure. Array: An array is a fixed size sequenced collection of elements of the same data type. List: An ordered set containing variable number of elements is called as List. File: A file is a collection of logically related information. It can be viewed as a large list of records consisting of various fields.

Linear Data Structures A linear data structure simply means that it is a storage format of the data in the memory in which the data are arranged in contiguous blocks of memory. Example is the array of characters it represented by one character after another. In the linear data structure, member elements form a sequence in the storage. There are two ways to represent a linear data structure in memory.  static memory allocation  dynamic memory allocation

Operations on Data structures 1. Traversing 2. Searching 3. Insertion 4. Deletion 5. Selection 6. Update 7. Sort 8. Merge 9. Split

Program 1 – Menu driven program to implement linear search and binary search and find the location of an element on its first occurrence Main Function Step 1 : List the choices Step 2: Enter the choice Step 3: Validate the choice Step 4: if option is 1 then call linear() function; 2 calls binary() function; 3 exits

Quicksort  Quick sort is a fast sorting algorithm used to sort a list of elements. The quick sort algorithm attempts to separate the list of elements into two parts and then sort each part recursively. That means it use divide and conquer strategy.  In quick sort, the partition of the list is performed based on the element called pivot. Here pivot element is one of the elements in the list.  The list is divided into two partitions such that "all elements to the left of pivot are smaller than the pivot and all elements to the right of pivot are greater than or equal to the pivot".

Steps of quick sort Step by Step Process In Quick sort algorithm, partitioning of the list is performed using following steps... Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the list). Step 2 - Define two variables i and j. Set i and j to first and last elements of the list respectively. Step 3 - Increment i until list[i] > pivot then stop. Step 4 - Decrement j until list[j] < pivot then stop. Step 5 - If i < j then exchange list[i] and list[j]. Step 6 - Repeat steps 3,4 & 5 until i >= j. Step 7 - Exchange the pivot element with list[j] element.

 Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the input array into smaller subarrays and sorting those subarrays then merging them back together to obtain the sorted array.  Here’s a step-by-step explanation of how merge sort works: 1.Divide: Divide the list or array recursively into two halves until it can no more be divided. 2.Conquer: Each subarray is sorted individually using the merge sort algorithm. 3.Merge: The sorted subarrays are merged back together in sorted order. The process continues until all elements from both subarrays have been merged.

def mergeSort(arr):  if len(arr) <= 1:  return arr  mid = len(arr) / 2  leftHalf = arr[0:mid]  rightHalf = arr[mid:len(arr)]  sortedLeft = mergeSort(leftHalf)  sortedRight = mergeSort(rightHalf)  return merge(sortedLeft, sortedRight)

1. def merge(left, right): 2. result = [] 3. i = j = 0 4. while i < len(left) and j < len(right): 5. if left[i] < right[j]: 6. result.append(left[i]) 7. i += 1 8. else: 9. result.append(right[j]) 10. j += 1 11.result.extend(left[i:]) 12. result.extend(right[j:]) 13. return result 14.unsortedArr = [3, 7, 6, - 10, 15, 23.5, 55, -13] 15.sortedArr = mergeSort(unsortedArr) 16.print("Sorted array:", sortedArr)

 List Operations:   Traversal: Traversal of a data structure means processing all the data elements of it, sequentlly.   Insertion: Insertion means addition of a new data element in a data structure.   Deletion: Deletion means removal of a data element from a data structure. The data element is searched for before its removal.   Searching: Searching involves searching for the specified data element in a data structure.   Sorting: Arranging data elements of a data structure in a specified order is called sorting.   Merging: Combining elements of two similar data structures to form a new data structure of same type, is called merging.

Insert an element Algorithm InsertLA (DATA, N, ITEM, LOC) Desc: This algorithm inserts new element ITEM in linear array DATA with N elements If LOC=1 it means the element has to insert in beginning If LOC =N+1 it means the element have to be inserted at the end If LOC = J it means the elements have to be inserted at Jth Location Begin Step 1: [Initialize counter I with index of last element] I=N Step 2: While I >=LOC repeat steps 3 and 4 Step 3: [Move the current element one position backwards] DATA[I+1]=DATA[I] Step 4: [Decrement counter I] I=I-1 Step 5:[Insert new element at the Location] DATA[LOC]=ITEM Step 6:[ Update total under of array elements] N=N+1 Exit

 It is a process of deleting a particular element from an array. If an element to be deleted ith location then all elements from the (i+1)th location we have to be shifted one step towards left. So (i+1)th element is copied to ith location and (i+2)th to (i+1)th location and so on. Algorithm: In this algorithm a value is being deleted from ith location of an array Reg[N]. Let us assume that last element in the array is at Mth position. Steps 1. Back=i 2. While (Back<M) repeat 3 and 4 3. Reg[Back]= Reg[Back+1] 4. Back= Back+1 5. M=M-1 6. End

There are 4 library functions provided by C defined under <stdlib.h> header file to facilitate dynamic memory allocation in C programming. They are: 1.malloc() 2.calloc() 3.free() 4.realloc()

malloc() method The “malloc” or “memory allocation” method in C is used to dynamically allocate a single large block of memory with the specified size. It returns a pointer of type void which can be cast into a pointer of any form. It doesn’t Iniatialize memory at execution time so that it has initializes each block with the default garbage value initially. ptr = (cast-type*) malloc(byte-size) For Example: ptr = (int*) malloc(100 * sizeof(int));

C calloc() method “calloc” or “contiguous allocation” method in C is used to dynamically allocate the specified number of blocks of memory of the specified type. it is very much similar to malloc() but has two different points and these are: 1.It initializes each block with a default value ‘0’. 2.It has two parameters or arguments as compare to malloc(). ptr = (cast-type*)calloc(n, element- size); n= no. of elements and element-size is the size of each element. ptr = (float*) calloc(25, sizeof(float));

free() method free() method in C is used to dynamically de-allocate the memory. The memory allocated using functions malloc() and calloc() is not de-allocated on their own. Hence the free() method is used, whenever the dynamic memory allocation takes place. It helps to reduce wastage of memory by freeing it. Syntax: free(ptr);

realloc() method “realloc” or “re-allocation” method in C is used to dynamically change the memory allocation of a previously allocated memory. In other words, if the memory previously allocated with the help of malloc or calloc is insufficient, realloc can be used to dynamically re-allocate memory. re-allocation of memory maintains the already present value and new blocks will be initialized with the default garbage value. ptr = realloc(ptr, newSize); where ptr is reallocated with new size 'newSize'.

Linked List A linked list is a non-sequential collection of data items. It is a dynamic data structure. For every data item in a linked list, there is an associated pointer that would give the memory location of the next data item in the linked list.  The data items in the linked list are not in consecutive memory locations. They may be anywhere, but the accessing of these data items is easier as each data item contains the address of the next data item.

Advantages of linked lists 1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program. 2. Linked lists have efficient memory utilization. Here, memory is not pre-allocated. Memory is allocated whenever it is required and it is de- allocated (removed) when it is no longer needed. 3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position. 4. Many complex applications can be easily carried out with linked lists.

 Uses of Linked List • The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space. • list size is limited to the memory size and doesn't need to be declared in advance. • Empty node can not be present in the linked list. • We can store values of primitive types or objects in the singly linked list.

Why use linked list over array?  Array has the following limitations: 1.The size of array must be known in advance before using it in the program. 2.Increasing size of the array is a time taking process. It is almost impossible to expand the size of the array at run time. 3.All the elements in the array need to be contiguously stored in the memory. Inserting any element in the array needs shifting of all its predecessors.

Disadvantag es of linked lists 1. It consumes more space because every node requires a additional pointer to store address of the next node. 2. Searching a particular element in list is difficult and also time consuming.

Comparison between array and linked list

Types of Linked Lists 1. Single Linked List. 2. Double Linked List. 3. Circular Linked List. 4. Circular Double Linked List.

 A single linked list is one in which all nodes are linked together in some sequential manner. Hence, it is also called as linear linked list.  A double linked list is one in which all nodes are linked together by multiple links which helps in accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary node within the list. Therefore each node in a double linked list has two link fields (pointers) to point to the left node (previous) and the right node (next). This helps to traverse in forward direction and backward direction.  A circular linked list is one, which has no beginning and no end. A single linked list can be made a circular linked list by simply storing address of the very first node in the link field of the last node.  A circular double linked list is one, which has both the successor pointer and predecessor pointer in the circular manner.

Implementat ion of Single Linked List Before writing the code to build the above list, we need to create a start node, used to create and access other nodes in the linked list.  Creating a structure with one data item and a next pointer, which will be pointing to next node of the list. This is called as self-referential structure.  Initialize the start pointer to be NULL.

Creating a node for Single Linked List

void createlist(int n) { int i; node * newnode; node *temp; for(i = 0; i < n ; i+ +) { newnode = getnode(); if(start = = NULL) { start = new node; } else { temp = start; while(temp - > next != NULL) temp = temp - > next; temp - > next = new node; } } }

Insertion of a Node  Inserting a node at the beginning.  Inserting a node at the end.  Inserting a node at intermediate position. Inserting a node at the beginning: The following steps are to be followed to insert a new node at the beginning of the list: Get the new node using getnode(). newnode = getnode(); If the list is empty then start = newnode. If the list is not empty, follow the steps given below: newnode -> next = start; start = newnode;

void insert_at_beg() { node *newnode; newnode = getnode(); if(start == NULL) { start = newnode; } else { newnode -> next = start; start = newnode; } }

Inserting a node at the end The following steps are followed to insert a new node at the end of the list: • Get the new node using getnode() • newnode = getnode(); • If the list is empty then start = newnode. • If the list is not empty follow the steps given below: • temp = start; • while(temp -> next != NULL) • temp = temp -> next; void insert_at_end() { node *newnode, *temp; newnode = getnode(); if(start == NULL) { start = newnode; } else { temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } }

Inserting a node at intermediat e position Get the new node using getnode(). newnode = getnode(); Ensure that the specified position is in between first node and last node. If not, specified position is invalid. This is done by countnode() function. Store the starting address (which is in start pointer) in temp and prev pointers. Then traverse the temp pointer upto the specified position followed by prev pointer. After reaching the specified position, follow the steps given below: prev -> next = newnode; newnode -> next = temp;

Counting the Number of Nodes: The following code will count the number of nodes exist in the list using recursion. int countnode(node *st) { if(st = = NULL) return 0; else return(1 + countnode(st - > next)); }

void insert_at_mid() { node *newnode, *temp, *prev; int pos, nodectr, ctr = 1; newnode = getnode(); printf("n Enter the position: "); scanf("%d", &pos); nodectr = countnode(start); if(pos > 1 && pos < nodectr) { temp = prev = start; while(ctr < pos) { prev = temp; temp = temp -> next; ctr++; } prev -> next = newnode; newnode -> next = temp; } else { printf("position %d is not a midd position", pos); } }

Deletion of a node Another primitive operation that can be done in a singly linked list is the deletion of a node. Memory is to be released for the node to be deleted. A node can be deleted from the list from three different places namely. Deleting a node at the beginning. Deleting a node at the end. Deleting a node at intermediate position

Deleting a node at the beginning The following steps are followed, to delete a node at the beginning of the list: If the list is not empty, follow the steps given below: temp = start; start = start -> next; free(temp); void delete_at_beg() { node *temp; if(start == NULL) { printf("n No nodes are exist.."); return ; } else { temp = start; start = temp -> next; free(temp); printf("n Node deleted "); } }

Deleting a node at the end The following steps are followed to delete a node at the end of the list: If the list is empty, display error message If the list is not empty, follow the steps given below: temp = prev = start; while(temp -> next != NULL) { prev = temp; temp = temp -> next; } prev -> next = NULL; free(temp); void delete_at_last() { node *temp, *prev; if(start == NULL) { printf("n Empty List.." return ; } else { temp = start; prev = start; while(temp -> next != NULL) { prev = temp; temp = temp -> next; } prev -> next = NULL; free(temp); printf("n Node delete "); } }

Deleting a node at Intermediate position If the list is empty, then display ‘empty list message’ If the list is not empty, follow the steps given below. if(pos > 1 && pos < nodectr) { temp = prev = start; ctr = 1; while(ctr < pos) { prev = temp; temp = temp -> next; ctr++; } prev -> next = temp -> next; free(temp); printf("n node deleted..");

void delete_at_mid() { int ctr = 1, pos, nodectr; node *temp, *prev; if(start == NULL) { printf("n Empty List.."); return ; } else { printf("n Enter position of node to delete: "); scanf("%d", &pos); nodectr = countnode(start); if(pos > nodectr) { printf("nThis node doesnot exist"); } if(pos > 1 && pos < nodectr) { temp = prev = start; while(ctr < pos) { prev = temp; temp = temp -> next; ctr ++; } prev -> next = temp -> next; free(temp); printf("n Node deleted.."); } else { printf("n Invalid position.."); getch(); } } }

Traversal and displaying a list (Left to Right) void traverse() { node *temp; temp = start; printf("n The contents of List (Left to Right): n"); if(start == NULL ) printf("n Empty List"); else { while (temp != NULL) { printf("%d ->", temp -> data); temp = temp -> next; } } printf("X"); }

Infix to Postfix  Algorithm 1. Scan the infix expression from left to right. 2. If the scanned character is an operand, output it. 3. Else, 1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it. 2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.) 4. If the scanned character is an ‘(‘, push it to the stack. 5. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis. 6. Repeat steps 2-6 until infix expression is scanned. 7. Print the output 8. Pop and output from the stack until it is not empty.

A * ( B + C )  ABC + * D / (A + ( B * C))  ABC*+ ((A + B) * (C + E))  AB + CE+* ((A + (B * C))/(D - E))  ABC * + DE - /

Algorithm to evaluate the postfix expression 1. Create a stack to store operands. 2. Scan the given expression from left to right. 3. a) If the scanned character is an operand, push it into the stack. b) If the scanned character is an operator, POP two operands from stack and perform operation and PUSH the result back to the stack. 4. Repeat step 3 till all the characters are scanned. 5. When the expression is ended, the number in the stack is the final result.

Doubly Linke d List A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Advantages over singly linked list 1) A DLL can be traversed in both forward and backward direction. 2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given. 3) We can quickly insert a new node before a given node. In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Disadvantages over singly linked list 1) Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though 2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers.

Creating a Node in Doubly Linked List Each node in a doubly linked list has data as well pointers. Therefore, we use a structure to create the node. The structure template for the node looks as follows: struct Node { int data; //The data point struct Node *Prev; //Pointer to the previous node struct Node *Next; //Pointer to the next node };

Traversal in a Doubly Linked List List_traversal(struct Node *Head) { Prev = (struct Node *)malloc(sizeof(struct Node)); Next = (struct Node *)malloc(sizeof(struct Node)); if(Head == NULL) //If the list is empty return; while(Next->Data != NULL) { Print(Next->data); //The display operation } }

Insertion A node can be added in four ways 1) At the front of the DLL 2) After a given node. 3) At the end of the DLL 4) Before a given node.

Insert a node at front (5 Steps)

Insert a node at front (5 Steps) //Given a reference to the head of a list and an int, inserts a new node on the front of the list. void push(struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* 2. put in the data */ new_node->data = new_data; /* 3. Make next of new node point to earlier head and previous as NULL */ new_node->next = (*head_ref); new_node->prev = NULL; /* 4. change prev of earlier head node to new node */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* 5. move the head to point to the new node */ (*head_ref) = new_node; }

Add a node after a given node /* Given a node as prev_node, insert a new node after the given node */ void insertAfter(struct Node* prev_node, int new_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { printf("the given previous node cannot be NULL"); return; } /* 2. allocate new node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* 3. put in the data */ new_node->data = new_data; /* 4. Make next of new node as next of prev_node */ new_node->next = prev_node- >next; /* 5. Make the next of prev_node as new_node */ prev_node->next = new_node; /* 6. Make prev_node as previous of new_node */ new_node->prev = prev_node; /* 7. Change previous of new_node's next node */ if (new_node->next != NULL) new_node->next->prev = new_node; }

Add a node before a node Let the pointer to this given node be next_node and the data of the new node to be added as new_data. 1.Check if the next_node is NULL or not. If it’s NULL, return from the function because any new node can not be added before a NULL 2.Allocate memory for the new node, let it be called new_node 3.Set new_node->data = new_data 4.Check for empty list 5.Set the previous pointer of this new_node as the previous node of the next_node, new_node->prev = next_node->prev 6.Set the previous pointer of the next_node as the new_node, next_node->prev = new_node 7.Set the next pointer of this new_node as the next_node, new_node->next = next_node; 8.If the previous node of the new_node is not NULL, then set the next pointer of this previous node as new_node, new_node- >prev->next = new_node 9.Else, if the prev of new_node is NULL, it will be the new head node. So, make (*head_ref) = new_node.

void append(struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node* last = *head_ref; /* used in step 5*/ /* 2. put in the data */ new_node->data = new_data; /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = new_node; /* 7. Make last node as previous of new node */ new_node->prev = last; return; } /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node->next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { new_node->prev = NULL; *head_ref = new_node; return; }

Deletion from a Doubly Linked List 1. Deletion from beginning 2. Deletion at the end 3. Deleting a node other than the first and the last node

Deletion from the beginning Algorithm to delete node from beginning %% Input: head {Pointer to first node of the linked list} Begin: If (head == NULL) then write ('Can't delete from an empty list') End if Else then toDelete head; ← head head.next; ← head.prev NULL; ← unalloc (toDelete) write ('Successfully deleted first node from the list') End if End

Deletion at the end Algorithm to delete node from end %% Input: last {Pointer to last node of the linked list} Begin: If (last == NULL) then write ('Can't delete from an empty list') End if Else then toDelete last; ← last last.prev; ← last.next NULL; ← unalloc (toDelete) write ('Successfully deleted last node from the list') End if End

Algorithm to delete node from any position of a doubly linked list Algorithm to delete node from any position %% Input : head {Pointer to the first node of the list} last {Pointer to the last node of the list} N {Position to be deleted from list} Begin: current head; ← For i 1 to N and current != NULL do ← current current.next; ← End for If (N == 1) then deleteFromBeginning() End if Else if (current == last) then deleteFromEnd() End if Else if (current != NULL) then current.prev.next current.next ← If (current.next != NULL) then current.next.prev current.prev; ← End if unalloc (current) write ('Node deleted successfully from ', N, ' position') End if Else then write ('Invalid position') End if

Defining a node 1.typedef struct node// defining structure node 2.{ 3. int data; 4. struct node *link; 5.}node;

Creation of new node 1. //creates a new node 2. node *create() 3. { 4. node *temp=(node*)malloc(sizeof(node)); 5. printf("enter datan"); 6. scanf("%d",&temp->data); 7. temp->link=NULL; 8. size++; 9. return temp; 10.}

Traverse to a node in the list 1. node *traverse(node *start,int pos) 2. { 3. int i=1; 4. do 5. { 6. i++; 7. start=start->link; 8. }while(i<pos); 9. return start; 10.}

Insert after a node 1. //inserts node after curr node 2. void insert(node *curr) 3. { 4. node *temp=create(); 5. temp->link=curr->link; 6. curr->link=temp;  }

Insert at the beginning 1. node *insert_start(node *start, node *end) 2. { 3. //printf("%dn",start->data); 4. node *curr=create(); 5. curr->link=start; 6. start=curr; 7. end->link=start; 8. return start; 9. }

Insert at the end 1. node *insert_end(node *start, node *end) 2. { 3. node *curr=create(); 4. end->link=curr; 5. curr->link=start; 6. end=curr; 7. return end; 8. }

Traverse 1. void display(node *start, int size) 2. { 3. node *temp=start;int i=1; 4. printf("ncircular linkedlistn"); 5. if(size==0) 6. { 7. printf("List Emptyn"); 8. return; 9. } 10. do 11. { 12. i++; 13. printf("%dn",start->data); 14. start=start->link; 15. }while(start!=temp&&i<=size); 16. printf("n"); 17.}

Delete a node at given location 1. void delete(node *start,node *end,int pos) 2. { 3. node *temp,*temp2; 4. temp=traverse(start,pos);// traverses to prev node from current pos 5. temp2=temp->link;//set to next node from pos 6. temp->link=temp2->link;// connection of prev to next node 7. free(temp2); 8. size--; 9. display(start); 10.}

Delete from beginning 1. node *delete_from_beg(node *start,node *end) 2. { 3. node *temp; 4. if(size==1)// to delete remaining one element in list since both are linked to each other 5. { 6. // free(start); 7. /+/ free(end); 8. size--; 9. start=end=NULL; 10. display(start); 11. return NULL; 12. } 13. else 14. { 15. temp=start; 16. start=start->link; 17. end->link=start; 18. free(temp); 19. size--; 20. display(start); 21. return start; 22. } 23. } 24.

Delete from end 1. node *delete_from_end(node *start,node *end) 2. { 3. node *temp; 4. if(size==1) 5. { 6. start=delete_from_beg(start,end); 7. return start; 8. } 9. else 10. { 11. temp=traverse(start,size-1); 12. temp->link=start; 13. free(end); 14. end=temp; 15. size--; 16. display(start); 17. return end; 18. } 19.}

Introduction to data structures - Explore the basics

More Related Content

Similar to Introduction to data structures - Explore the basics

More from divyammo

Recently uploaded

Introduction to data structures - Explore the basics

Editor's Notes