Algorithm to delete a Node from Linked List

Delete_Node_LL(List, Start, value)

Here, List is a Linked list Containing n Nodes.Start is a pointer pointing to the starting node of the List We have to delete a node which contains value as its data. Ptr is an intermediate pointer, which will be used to traverse the List. Prev is a intermediate pointer which will be contains the address of Node which is previous to the node pointing by Ptr

Step 1: [Initializing the pointers Ptr will be pointing the starting node and Prev will be null]

             Ptr = Start, Prev = null

Step 2: [If Node to be deleted is 1st node]

            if Ptr->Data = value then

                  i) Start = Ptr->Next

                  ii) Free(Ptr) [Releasing memory consumed by node to be deleted]

                  iii) Return; 

Step 3:[Since node to be deleted is not starting node so moving Ptr to 2nd node and Prev will be pointing starting node] 

           i)Prev = Ptr

          ii)Ptr = Ptr->Next

Step 4: Repeat Step 4(i) to 4(iv) till Ptr is not null. 

           i) if Ptr->Data = value then

                         a) Prev->Next = Ptr->Next; 

                         b) Free(Ptr); 

                         c) Return;

          ii) Prev = Ptr;

         iii) Ptr = Ptr ->Next

Step 5: [Node was not found raise error or return the control]

            Return;

Algorithm to search element in the Linked list

Search_LL(List, element, Start)

Here, List is a Linked list containing n elements, in which we have to search element. Start is a pointer which is containing the address of starting Node. SUCCESS=1 is a constant which will be returned on successful search and FAILURE=0 is a constant which will be returned on unsuccessful search. Ptr is a intermediate pointer which is used to traverse the list.

Step 1: [check, if list is empty]

            If Start = null then 

                   return FAILURE;

Step 2: Ptr = Start

Step 3: While Ptr < > null repeat step 4

Step 4: i) If Ptr -> Data = Element then 

                    return SUCCESS;

           ii) Ptr = Ptr->Next

Step 5: return FAILURE;

Step 6: End

Algorithm to insert node in Simple Linked List

Insert_LinkedList ( List, Node, Start, Value,Data)

In this algorithm List is a linked list having n nodes. Start is a pointer which contains the address of starting node of the list.Node  is the pointer pointing to the new node. Value is the data of a node from list after which the new node is to be inserted.Data is the value which is to be assigned to the data part of new node.

Node->data contains data and Node->Next points next node. In this algorithm following criteria are followed.

• If List is empty Node will be inserted at starting of list
• If Value found in the list than node will be inserted after the value
• else node will be inserted at the end of list

Ptr is an intermediate pointer which points the current node and used to traverse the list

Step 1: i) Node ->data = Data

Step 2: [Check if list is empty then we will insert new node at the starting point.]

            If Start = null then go to step 3 else go to step 4

Step 3: i) Node->Next=null.

            ii) Start=Node

            iii) Return

Step 4: [assigning the 1st node address to Ptr]

                  Ptr = Start

Step 5: While Ptr->Next is Not null repeat

            i) if Ptr->data = Data then go to step i.a else go to step ii)

                     a) Node->Next = Ptr->Next

                     b) Ptr->Next = Node

                     c) Return

           ii) Ptr = Ptr->Next

Step 6: [If Value that was searched not found, in that case inserting Node at the end of List]

            i)Node->Next = null

           ii)Ptr->Next = Node

Step 7: End

Algorithm: Binary Search in Array

Binary search algorithm is enhancement in searching of element in array, It reduces worst case complexity of of linear search from O(n) to O(log₂n). In this algorithm all the elements in the array must be sorted.

BinarySearch(ArrayValues[], n, searchValue, LB, UB)

Here ArrayValues is an array of size n, Which is already sorted. In which we have to search an element searchValue. LB is lower bound and UB is an upper bound of the array. Mid is an intermediate variable which will contains middle element of array.

Algorithm: Linear Search For Array

In Linear Search algorithm whole array is traversed to search the element untill the element found.

Linear_Search(valArr[], n, searchValue)

Here valArr[] is of length n, and SearchValue  is a value which is to be found in the array. Consider lower bound of the array is 1. this algorithm will return index of first occurrence of the searchValue, and returns -1 on failure.

Step1: [Iterate the array]

           For index=1 to n repeat step 2 and 3

Step2:  if valArr[index]=searchValue then goto step 2(i) else goto step 3

                  i) return index

Step3: if index=n then goto step 3(i) else goto step 3(ii)

            i) return -1;

            ii) index=index-1;

Step4: End.

Algorithm: To remove element from Array

Algorithm: RemoveElementFromArray(rIndex,valArray[],n,removedData)

In this algorithm rIndex is index from which element is to be removed and n is the size of array valArray. removedData will contain the value which is removed from array from index rIndex.

*consider lower bound of array is 1.

Step 1: [Check for size of array]

           if rIndex > n then

                 a) raise_error "Array Index out of bound"
                 b) Exit
Step 2: removedData = valArray[rIndex]

Step 3: [Shifting elements of array]
           Declare index as integer
           i) for index=rIndex to n-1 repeat step a to b

               a) valArray[index] = valArray[index+1]
               b) index= index+ 1

           ii) valArray[index] = null

Step 4: End

Explanation

DSA Tutorials: Algorithm: To insert element in array

Array Introduction

Algorithm: To insert element in array

Algorithm: InsertElementInArray(dataVal, valArray[], n, k,m)

In this algorithm dataVal is an element which is to be inserted in an array named valArray, whose size is n. we have to insert the element dataVal at index k. m is the total present elements in the array where m<n
*considering lower bound of array is 1.

Step 1: [Check for the size of array]
         if n < k then

                   a) RaiseError "Array Index out of bound"

                   b) goto step 5

Step 2: [Shifting the elements from k indexed elements by 1]

           i) for index = m  to k repeat step a to b

                 a) valArray[index+1] = valArray[index]
             
                 b) [Decrements counter]   index = index - 1

           ii) goto to step 3

Step 3: [Now Insert the element]

            valArray[k] = dataVal;

Step 4: Exit

Explanation

Linked List

Definition

A Linked List is a linear collection of data element(where linearity is achieved by pointers in node) with following properties:.

1. Each element of Linked list is called Node
2. There is a pointer called start. Which contains address of first Node
3. Each Node has atleast two part. 1st is data part another is pointer part. Data part contains actual data. and pointer part contains address of next Node.
4. Pointer of Last Node of Linked List contains null.

Types of Linked List

1. Simple Linked List
2. Header Linked List
3. Circular Linked List
4. Two way Linked List
5. Hybrid Linked List

Arrays

Defination:

Array is a collection of homogeneous data elements with following properties

1. All the data elements are stored contiguous memory location
2. Data elements are accessed with index number.

There are 3 types of Array

• 1-D Array (Linear Array)
• 2-D Array (Matrix)
• N-D Array (Multidimensional Array)

DSA: Introduction

Definitions: 

1. Data Structure: A mathematical or logical representation of data in memory is called data structure.

2. Algorithm: A step by step solution to any problem is called algorithm.

Introduction to Data Structure:

As we have gone through the definition of data structure "It is mathematical or logical representation of data in memory". 

Classification:

There are two type of Data Structures according to memory representation