Deleting Node From 2 way linked List

Delete_Node_2WayList(List,Value, Start, End)

Here in this algorithm List is a 2 way linked list containing n nodes. Start and End are the pointers pointing the starting and ending nodes. We have to delete a node from the list which contains Value as its data. Ptr is an intermediate pointer that will be used to traverse the list.

[Checking if List is Empty]

Step 1: if Start=null then

                  return;

[Initializing the Ptr]

Step 2: Ptr = Start

[Searching for the Node which is to be deleted]

Step 3: While Ptr <> null and Ptr->Data <> Value repeat the step

                      i) Ptr = Ptr -> Next

[Checking if search was successful or not]

Step 4: if Ptr = null then

                return;

[Search was successful and Ptr is pointing to the node which is to be deleted]

Step 5:   i) Ptr->Prev->Next = Ptr->Next [Next of Previous node of current node will point the next of  current node] 

              ii) Ptr->Next->Prev = Ptr->Prev [Prev of Next node of current node will point the previous of current node]

[Now Current Node pointing by Ptr is not referenced from list anymore it can be freed now]

             iii) FREE (Ptr)

Step 6: End;

Inserting Node in Two Way Linked List

As we all know, in Two-Way linked list there are two Pointer's fields, with a data Field. One Pointer Field is known as Previous Pointer, which points Previous Node. Previous Pointer will be null, if it is First Node. Another Pointer Field is known as Next Pointer, which points to the next node. Next Pointer will be null if it is last node. There are Two External pointer called Start & End. Start pointer points Starting node of the list, End pointer points the last pointer of the List.

                   

Insert_Node_2wayList(List,DataAfter,Start,End,NewNode)

Here List is a 2 way linked list containing n Nodes. Start, End are the starting and Ending pointers pointing to the First and Last Node of the List. DataAfter is a value in a Node after which the NewNode will have to be inserted. 

Ptr is an intermediate pointer which will be used to traverse the list

Conventions: <> = Not Equals to

Step 1: [checking, if List is empty]

            if Start=null then

                   NewNode->Prev = null

                   NewNode->Next = null

                   Start = NewNode

                   End = NewNode

                   return Success;

Step 2:[Initializing the pointer]

           Ptr = Start

Step 3: [List is Not Empty Now Searching for the Node after which new Node is to be inserted. After this loop Ptr pointer of the node after which new node is to be inserted or null if the node not found]

            While Ptr <> null and Ptr->Data <> DataAfter repeat the step

                          i) Ptr=Ptr->Next

Step 4: [Check, if the Node found or not]

            if Ptr = null then

                 return Failure;

Step 5: [Inserting node]

             NewNode->Prev = Ptr              [New Node's Previous pointer will point current Node]

             NewNode->Next = Ptr->Next  [New Node's Next pointer will point Next Node current Node]

             Ptr->Next->Prev = NewNode  [Next Node of current node will point new node]

             Ptr->Next = NewNode              [Next of Current Node will point new node]

Step 6: return Success;

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