tag:blogger.com,1999:blog-73265124684831682132024-02-07T10:56:32.700-08:00DSA TutorialsAdminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-7326512468483168213.post-72224419882877612682012-12-04T04:57:00.001-08:002012-12-04T04:57:42.372-08:00Deleting Node From 2 way linked List<div dir="ltr" style="text-align: left;" trbidi="on">
<h4 style="text-align: left;">
Delete_Node_2WayList(List,Value, Start, End)</h4>
<div>
<br /></div>
<div>
Here in this algorithm <i><b>List</b></i> is a 2 way linked list containing n nodes. <b><i>Start</i></b> and <b><i>End</i></b> are the pointers pointing the starting and ending nodes. We have to delete a node from the list which contains Value as its data. <i style="font-weight: bold;">Ptr </i>is an intermediate pointer that will be used to traverse the list.</div>
<div>
<br /></div>
<div>
[Checking if List is Empty]</div>
<div>
<b>Step 1: </b>if <i style="font-weight: bold;">Start=null </i>then</div>
<div>
<i> return;</i></div>
<div>
[Initializing the Ptr]</div>
<div>
<b>Step 2: <i>Ptr = Start</i></b></div>
<div>
[Searching for the Node which is to be deleted]</div>
<div>
<b>Step 3: </b>While <b style="font-style: italic;">Ptr <> null </b><i>and </i><b style="font-style: italic;">Ptr->Data <> Value </b>repeat the step</div>
<div>
i) <b><i>Ptr = Ptr -> Next</i></b></div>
<div>
[Checking if search was successful or not]</div>
<div>
<b>Step 4: </b>if <b style="font-style: italic;">Ptr = null </b>then</div>
<div>
return;</div>
<div>
[Search was successful and <b>Ptr </b>is pointing to the node which is to be deleted]</div>
<div>
<b>Step 5: </b>i) <i style="font-weight: bold;">Ptr->Prev->Next = Ptr->Next </i>[Next of Previous node of current node will point the next of current node]<i style="font-weight: bold;"> </i></div>
<div>
ii)<i style="font-weight: bold;"> Ptr->Next->Prev = Ptr->Prev </i>[Prev of Next node of current node will point the previous of current node]</div>
<div>
<br /></div>
<div>
[Now Current Node pointing by Ptr is not referenced from list anymore it can be freed now]</div>
<div>
iii) <b><i>FREE (Ptr)</i></b></div>
<div>
<b><i><br /></i></b></div>
<div>
<b>Step 6: </b>End;</div>
<div>
<b><i><br /></i></b></div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-48599903620635658552012-12-04T04:43:00.000-08:002012-12-04T04:57:37.679-08:00Inserting Node in Two Way Linked List<div dir="ltr" style="text-align: left;" trbidi="on">
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 <i>null, </i>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 <i>Start & End. Start </i>pointer points Starting node of the list, <i>End </i>pointer points the last pointer of the List.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEituxNY-b2ThBxnzXU1HEBgL2VIDw6TWUPoyASYvawG-SpYBgTt904rHt0E7u-DOAXLqNKYrNWn26HrN2PomcS22SpcXhiShebLEvvrk5iF7pa3KPnL7ceKdqj-cLFRCi6BtA-_N4cY61jg/s1600/2wayLL.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEituxNY-b2ThBxnzXU1HEBgL2VIDw6TWUPoyASYvawG-SpYBgTt904rHt0E7u-DOAXLqNKYrNWn26HrN2PomcS22SpcXhiShebLEvvrk5iF7pa3KPnL7ceKdqj-cLFRCi6BtA-_N4cY61jg/s1600/2wayLL.png" /></a></div>
<br />
<h4 style="text-align: left;">
Insert_Node_2wayList(List,DataAfter,Start,End,NewNode)</h4>
<div>
<br />
Here <i>List </i>is a 2 way linked list containing n Nodes. <i>Start, End</i> are the starting and Ending pointers pointing to the First and Last Node of the List. <i>DataAfter</i> is a value in a Node after which the NewNode will have to be inserted. </div>
<div>
Ptr is an intermediate pointer which will be used to traverse the list</div>
<div>
Conventions: <> = Not Equals to</div>
<div>
<b>Step 1:</b> [checking, if List is empty]</div>
<div>
if <b style="font-style: italic;">Start=null </b>then</div>
<div>
<i>NewNode->Prev = null</i></div>
<div>
<i>New</i><i>Node->Next = null</i></div>
<div>
<i>Start = </i><i>New</i><i>Node</i></div>
<div>
<i> End = </i><i>New</i><i>Node</i></div>
<div>
<i> return <b>Success</b>;</i></div>
<div>
<b>Step 2:</b>[Initializing the pointer]</div>
<div>
<b><i> Ptr = Start</i></b></div>
<div>
<b>Step 3:</b> [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 <i style="font-weight: bold;">null </i>if the node not found]</div>
<div>
While <b style="font-style: italic;">Ptr <> null </b>and<b style="font-style: italic;"> </b><i><b>Ptr->Data <> DataAfter</b></i><b style="font-style: italic;"> </b>repeat the step</div>
<div>
i) <b><i>Ptr=Ptr->Next</i></b></div>
<div>
<b><i><br /></i></b></div>
<div>
<b>Step 4: </b>[Check, if the Node found or not]</div>
<div>
if <i style="font-weight: bold;">Ptr = null </i>then</div>
<div>
<i>return <b>Failure;</b></i></div>
<div>
<i><b><br /></b></i></div>
<div>
<b>Step 5: </b>[Inserting node]</div>
<div>
<i>NewNode->Prev = Ptr [</i>New Node's Previous pointer will point current Node<i>]</i></div>
<div>
<i>NewNode->Next = Ptr->Next [</i>New Node's Next pointer will point Next Node current Node<i>]</i></div>
<div>
<i>Ptr->Next->Prev = NewNode [</i>Next Node of current node will point new node<i>]</i></div>
<div>
<i> Ptr->Next = NewNode [</i>Next of Current Node will point new node<i>]</i></div>
<div>
<i><br /></i></div>
<div>
<b>Step 6: </b><i>return <b>Success</b>;</i></div>
<div>
<i><br /></i></div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-73002232138478999222012-11-28T23:37:00.002-08:002012-11-30T03:39:24.618-08:00Algorithm to delete a Node from Linked List<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Delete_Node_LL(List, Start, value)</h3>
<div>
Here, <i>List</i> is a Linked list Containing <i>n</i> Nodes.<i>Start</i> is a pointer pointing to the starting node of the <i>List</i> We have to delete a node which contains value as its data. <i>Ptr </i>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 <i>Ptr</i></div>
<div>
<br /></div>
<div style="border-color: blue; border-style: solid; color: grey;">
<br />
<div>
Step 1: [Initializing the pointers <i>Ptr </i>will be pointing the starting node and <i>Prev</i> will be null]</div>
<div>
<i> Ptr = Start, Prev = null</i></div>
<div>
<i><br /></i></div>
<div>
Step 2: [If Node to be deleted is 1st node]</div>
<div>
if <i>Ptr->Data = value</i> then</div>
<div>
i) <i>Start = Ptr->Next</i></div>
<div>
ii) Free(<i>Ptr</i>) <i>[Releasing memory consumed by node to be deleted]</i></div>
<div>
iii) Return; </div>
<div>
<i><br /></i></div>
<div>
Step 3:[Since node to be deleted is not starting node so moving Ptr to 2nd node and Prev will be pointing starting node] </div>
<div>
i)<i>Prev = Ptr</i></div>
<div>
<i> </i>ii)<i>Ptr = Ptr->Next</i></div>
<div>
<i><br /></i></div>
<div>
Step 4: Repeat Step 4(i) to 4(iv) till <i>Ptr </i>is not <i>null.</i> </div>
<div>
i) if <i>Ptr->Data = value </i>then</div>
<div>
a) <i>Prev->Next = Ptr->Next; </i></div>
<div>
b)<i> Free(Ptr); </i></div>
<div>
<i> </i>c)<i> Return;</i></div>
<div>
ii) <i>Prev = Ptr;</i></div>
<div>
iii) <i>Ptr = Ptr ->Next</i></div>
<div>
<br /></div>
<div>
Step 5: [Node was not found raise error or return the control]</div>
<div>
Return;</div>
</div>
<div class="BSExplainFlip">
<br />
<br />
<a name='more'></a><br />
<h4 style="text-align: left;">
Click Here for Explanation</h4>
</div>
<div class="BSExplainDiv" style="display: none;">
Consider a List displayed below
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgcyvH9bfORp-9k0cNtVQk3DBX3_rhHQuMhYdYkatSPcw5LuPz0nHVXe-SpDAtB3xdZrmiMWeNXxRtTXPU8x5AB_pNUAxbK7MZ5CLQ74cXXo03BuER6FdIcJ5GeZYOCf_J09RVsQpo5zJtb/s1600/List.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="114" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgcyvH9bfORp-9k0cNtVQk3DBX3_rhHQuMhYdYkatSPcw5LuPz0nHVXe-SpDAtB3xdZrmiMWeNXxRtTXPU8x5AB_pNUAxbK7MZ5CLQ74cXXo03BuER6FdIcJ5GeZYOCf_J09RVsQpo5zJtb/s640/List.png" width="640" /></a></div>
<br />
Here <i>Start</i>=2002<br />
Consider <i>value=54</i><br />
<i><br /></i>
At starting:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZZZHWo1wiqs0qjmWr3eHjSN3-cllxLOCRFx7sYU5kZC794_qqRbfdCFa98AjpuLzAC6esI0pnUAm-P49H3Gtf8y6ld4a6jr_8tJfWknwYVqhusPnBXcIUpLM1i20XmUI-f57mvX5ejoVg/s1600/List.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="138" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZZZHWo1wiqs0qjmWr3eHjSN3-cllxLOCRFx7sYU5kZC794_qqRbfdCFa98AjpuLzAC6esI0pnUAm-P49H3Gtf8y6ld4a6jr_8tJfWknwYVqhusPnBXcIUpLM1i20XmUI-f57mvX5ejoVg/s640/List.png" width="640" /></a></div>
<br />
<i> </i><br />
<i>Here Ptr = Start=2002.</i><br />
<i> </i><br />
<i>and Ptr->Data = value </i><br />
<b>so that according to the step 2 of algorithm</b><br />
<b><br /></b>
<i>Start = Ptr->Next</i><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEifqn0aYZJdSiU1zCLTGDQlnv-8QH-zQxfUAKW3UpHY5xrnCECIdZzMOUkF01IjdWm6q8ReazVnsAVNXy6dpPo1cNKe4C1_Qs4jddwjaqn2L3F6QXaK_F0acXh4xhRTDSsoEuoVRGB7CrN9/s1600/List.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="190" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEifqn0aYZJdSiU1zCLTGDQlnv-8QH-zQxfUAKW3UpHY5xrnCECIdZzMOUkF01IjdWm6q8ReazVnsAVNXy6dpPo1cNKe4C1_Qs4jddwjaqn2L3F6QXaK_F0acXh4xhRTDSsoEuoVRGB7CrN9/s640/List.png" width="640" /></a></div>
<i><br /></i>
<i>Free(Ptr)</i><br />
<i><br /></i>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgV2iXTvkW_-UZzVyeBEoUrg-fMLDNrQU2f7USX7uvz7o0LVPCF2uty8_zl9NeFoN5CscQuT3YhBan25MdyFeNHDgQfdFb4bxA7J1uOeYMfBf7niVQZZg-FK_r5Qqqu5fiUMegwxhtT4dyK/s1600/List+-+Copy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="123" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgV2iXTvkW_-UZzVyeBEoUrg-fMLDNrQU2f7USX7uvz7o0LVPCF2uty8_zl9NeFoN5CscQuT3YhBan25MdyFeNHDgQfdFb4bxA7J1uOeYMfBf7niVQZZg-FK_r5Qqqu5fiUMegwxhtT4dyK/s400/List+-+Copy.png" width="400" /></a></div>
<i> </i><br />
Similarly, if<i> value=10 </i>then<br />
<i>Ptr->Data = 54 </i>which is not equal to <i>value.</i><br />
<i>so Prev = Ptr = 2002</i><br />
<i> Ptr = Ptr->Next = 2044</i><br />
<i><br /></i>
<u>Iteration 1:</u><br />
<i>Ptr->Data</i> = 45 <i>which is not equals to value</i><br />
<i> </i>So <i>Prev = Ptr = 2044</i><br />
<i> Ptr = Ptr->Next = 5260</i><br />
<i><br /></i>
<u>Iteration 2:</u><br />
<i>Ptr->Data</i> = 10 = Value<br />
=> <i>Prev->Next = Ptr->Next</i><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVI9O8C0YP8eFq84n-95mCmcfaCy14SR0CNB2_IDCwY9FN2FeXmjEkjgjKd-0qYVRZ84UkQ25Wqf0rrdJE9YQcbclX5TOxF6LAUjse6oAFHJ07wOF8F9WOIaoL1gxG69ieqK4C7zOE1XzU/s1600/List_Main+-+Copy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="118" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVI9O8C0YP8eFq84n-95mCmcfaCy14SR0CNB2_IDCwY9FN2FeXmjEkjgjKd-0qYVRZ84UkQ25Wqf0rrdJE9YQcbclX5TOxF6LAUjse6oAFHJ07wOF8F9WOIaoL1gxG69ieqK4C7zOE1XzU/s400/List_Main+-+Copy.png" width="400" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<i>Free(Ptr)</i><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD6_1k0povqBZJDVYn1hq2Czyx43uKep5HBy8nRYL-DCCV8gF-WUsb4R5xRjXhWi7Z0bL299UZCMSAqGKId4tAGcUd-85WVDLo_ztdcJjfK8RjS3547CSiyDYOStb7En6zD_zr_qpghe8a/s1600/List_Main+-+Copy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="93" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD6_1k0povqBZJDVYn1hq2Czyx43uKep5HBy8nRYL-DCCV8gF-WUsb4R5xRjXhWi7Z0bL299UZCMSAqGKId4tAGcUd-85WVDLo_ztdcJjfK8RjS3547CSiyDYOStb7En6zD_zr_qpghe8a/s320/List_Main+-+Copy.png" width="320" /></a></div>
<br /></div>
</div>
<!-- Begin: adBrite, Generated: 2012-11-29 13:15:47 -->
<script type="text/javascript">
var AdBrite_Title_Color = '0000FF';
var AdBrite_Text_Color = '000000';
var AdBrite_Background_Color = 'fff7df';
var AdBrite_Border_Color = 'CCCCCC';
var AdBrite_URL_Color = '008000';
var AdBrite_Page_Url = '';
try{var AdBrite_Iframe=window.top!=window.self?2:1;var AdBrite_Referrer=document.referrer==''?document.location:document.referrer;AdBrite_Referrer=encodeURIComponent(AdBrite_Referrer);}catch(e){var AdBrite_Iframe='';var AdBrite_Referrer='';}
</script>
<script type="text/javascript">document.write(String.fromCharCode(60,83,67,82,73,80,84));document.write(' src="http://ads.adbrite.com/mb/text_group.php?sid=2251965&zs=3330305f323530&ifr='+AdBrite_Iframe+'&ref='+AdBrite_Referrer+'&purl='+encodeURIComponent(AdBrite_Page_Url)+'" type="text/javascript">');document.write(String.fromCharCode(60,47,83,67,82,73,80,84,62));</script>
<div><a target="_top" href="http://www.adbrite.com/mb/commerce/purchase_form.php?opid=2251965&afsid=1" style="font-weight:bold;font-family:Arial;font-size:13px;">Your Ad Here</a></div>
<!-- End: adBrite -->Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-62643478796664471412012-11-28T00:17:00.002-08:002012-11-28T23:41:26.388-08:00Algorithm to search element in the Linked list<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Search_LL(List, element, Start)</h3>
<div>
Here, <i>List</i> is a Linked list containing n elements, in which we have to search <i>element. Start </i>is a pointer which is containing the address of starting Node. <i>SUCCESS</i>=1 is a constant which will be returned on successful search and <i>FAILURE</i>=0 is a constant which will be returned on unsuccessful search. <i>Ptr </i>is a intermediate pointer which is used to traverse the list.</div>
<div>
<br /></div>
<div>
Step 1: [check, if list is empty]</div>
<div>
If <i>Start = null </i>then </div>
<div>
<i> return FAILURE;</i></div>
<div>
Step 2: <i>Ptr = Start</i></div>
<div>
Step 3: While <i>Ptr < > null </i>repeat step 4</div>
<div>
Step 4: i) If <i>Ptr -> Data = Element </i>then </div>
<div>
<i> return SUCCESS;</i></div>
<div>
ii) <i>Ptr = Ptr->Next</i></div>
<div>
Step 5: <i>return FAILURE;</i></div>
<div>
Step 6: End</div>
<br />
<a name='more'></a><br />
<br />
<div class="BSExplainFlip">
<h4 style="text-align: left;">
<b>Click here for Explanation</b></h4>
</div>
<div class="BSExplainDiv" style="display: none;">
Consider a List displaying below, In this there are 4 nodes. Starting node <i>Start</i> Containing the address of starting node i.e. 2002, and last node containing the null value. Suppose we have search an <i>element=45 </i>in the list<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVDRCPMvpHo_4acNuCsKt3kmaBTPof6f4RGvnXs_V3NrMgoMKCTAWuxVgPCQ1DAq6tTYOsuDD743a9AdbOE3MK7htL_vXiNy1rxDEttAqZGMO2AEzmRbdKqISOKqMRIsZ-dQwEnA2wjaHZ/s1600/List.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="115" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVDRCPMvpHo_4acNuCsKt3kmaBTPof6f4RGvnXs_V3NrMgoMKCTAWuxVgPCQ1DAq6tTYOsuDD743a9AdbOE3MK7htL_vXiNy1rxDEttAqZGMO2AEzmRbdKqISOKqMRIsZ-dQwEnA2wjaHZ/s640/List.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">List</td></tr>
</tbody></table>
Since <i>Start is not null </i>so step 2 will be executed next<br />
<br />
Step 2: <i>Ptr=Start=2002 </i><b>i.e <i>Ptr</i> is now also pointing to the starting node.</b><br />
Step 3: [Iteration will be started]<br />
<br />
Iteration 1: <i>Ptr->Data = 54 is not Equal to Element(=45).</i><br />
<i> <b>so </b>Ptr = Ptr->Next = 2044 [Now <b>Ptr</b> is pointing to next node]</i><br />
<i><br /></i>
Iteration 2:<i>Ptr->Data = 45 is Equal to Element(=45)</i><br />
<i> s<b>o Return Success;</b></i><br />
<br />
<u>Now Suppose we have to search an <i>element=60:</i></u><br />
<u><i><br /></i></u>
<br />
Iteration 1: <i>Ptr->Data = 54 is not Equal to Element(=60).</i><br />
<i> <b>so </b>Ptr = Ptr->Next = 2044 [Now <b>Ptr</b> is pointing to next node]</i><br />
<div>
<i><br /></i></div>
<br />
<br />
Iteration 2: <i>Ptr->Data = 45 is not Equal to Element(=60).</i><br />
<i> <b>so </b>Ptr = Ptr->Next = 5260 [Now <b>Ptr</b> is pointing to next node]</i><br />
<div>
<i><br /></i></div>
<br />
<br />
Iteration 3: <i>Ptr->Data = 10 is not Equal to Element(=60).</i><br />
<i> <b>so </b>Ptr = Ptr->Next = 3254 [Now <b>Ptr</b> is pointing to next node]</i><br />
<div>
<i><br /></i></div>
<br />
<br />
Iteration 4: <i>Ptr->Data = 87 is not Equal to Element(=60).</i><br />
<i> <b>so </b>Ptr = Ptr->Next = null [Now <b>Ptr</b> is now <b>null</b>]</i><br />
<i><br /></i>
<b>Since <i>Ptr </i>=null now so that Iteration will be finished and Search was failed so</b><br />
<b> <i>return FAILURE;</i></b></div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-17678685553962149092012-11-26T23:09:00.002-08:002012-11-26T23:09:46.463-08:00Algorithm to insert node in Simple Linked List<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Insert_LinkedList ( List, Node, Start, Value,Data)</h3>
<div>
In this algorithm List is a <i>linked list</i> having <i>n</i> nodes. Start is a pointer which contains the address of starting node of the list<i>.Node </i> is the pointer pointing to the new node. <i>Value </i>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.</div>
<div>
Node->data contains data and Node->Next points next node. In this algorithm following criteria are followed.</div>
<div>
<ul style="text-align: left;">
<li>If List is empty Node will be inserted at starting of list</li>
<li>If Value found in the list than node will be inserted after the value</li>
<li>else node will be inserted at the end of list</li>
</ul>
</div>
<div>
<br /></div>
<div>
Ptr is an intermediate pointer which points the current node and used to traverse the list</div>
<div>
<br /></div>
<div>
Step 1: i) Node ->data = Data</div>
<div>
Step 2: [Check if list is empty then we will insert new node at the starting point.]</div>
<div>
If <i>Start = null </i>then go to step 3 else go to step 4</div>
<div>
<br /></div>
<div>
Step 3: i) Node->Next=<i>null.</i></div>
<div>
ii) Start=Node</div>
<div>
iii) Return</div>
<div>
<br /></div>
<div>
Step 4: [assigning the 1st node address to Ptr]</div>
<div>
Ptr = Start</div>
<div>
<br /></div>
<div>
Step 5: While Ptr->Next <i>is Not <b>null </b>repeat</i></div>
<div>
<i> </i>i) if Ptr->data = Data then go to step i.a else go to step ii)</div>
<div>
a) Node->Next = Ptr->Next</div>
<div>
b) Ptr->Next = Node</div>
<div>
c) Return</div>
<div>
ii) Ptr = Ptr->Next</div>
<div>
Step 6: [If Value that was searched not found, in that case inserting Node at the end of List]</div>
<div>
i)Node->Next = <i>null</i></div>
<div>
ii)Ptr->Next = Node</div>
<div>
<br /></div>
<div>
Step 7: End</div>
<div>
<br /></div>
<div>
<br />
<a name='more'></a><br /></div>
<div class="BSExplainFlip">
<h4 style="text-align: left;">
<b>Click here for Explanation</b></h4>
<div>
<b><br /></b></div>
</div>
<div class="BSExplainDiv" style="display: none;">
According to the Algorithm Consider <b><i>List </i></b>is a Linked list and <i><b>Start</b></i> is a pointer which is pointing to the starting node of the list. <i style="font-weight: bold;">Data </i>is the data which is to be assigned to the data path of the New Node called <i style="font-weight: bold;">Node. Value=10 </i>is the data of a node from list after which we have to insert the new node.<br />
Step 1: <b><i>Node->data = Data</i></b><br />
<br />
Scene 1: List is Empty<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9JQSJ_rTHtSmOBtFpzU-Y9mRAXA31kLO4EFurw26X1AoJvomC2Lboe5fIzu5IMd7rTC6gbt4-CS7vVchYIaFTEV77J5ncqXuS5XF_XC68Ag4ES4ydBdEuILD4EQA-u4VYu3RJIMCys3gT/s1600/LL_Scene1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="43" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9JQSJ_rTHtSmOBtFpzU-Y9mRAXA31kLO4EFurw26X1AoJvomC2Lboe5fIzu5IMd7rTC6gbt4-CS7vVchYIaFTEV77J5ncqXuS5XF_XC68Ag4ES4ydBdEuILD4EQA-u4VYu3RJIMCys3gT/s400/LL_Scene1.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">When List is empty</td></tr>
</tbody></table>
Since List is empty adding <i style="font-weight: bold;">Node </i>to starting of the <b><i>List</i></b><br />
<b><i> Start = Node</i></b><br />
<i><b> </b>Now List will be as shown in below fig.</i><br />
<i><br /></i>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgp0vOau9qiyweYjRIIluwjZoE87m579EjsJPrGwIupcUFrKLHko3Jr70k8UBKIVv0rc8mlYzElZPnZEcdzQFKVo09sxuH_88PRR_3g-xMKjLC7iYG6lPDSqCdcfwvWY8nSdujBFu4F0qmw/s1600/LL_Scene_AddNodeAtFirst.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="100" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgp0vOau9qiyweYjRIIluwjZoE87m579EjsJPrGwIupcUFrKLHko3Jr70k8UBKIVv0rc8mlYzElZPnZEcdzQFKVo09sxuH_88PRR_3g-xMKjLC7iYG6lPDSqCdcfwvWY8nSdujBFu4F0qmw/s200/LL_Scene_AddNodeAtFirst.png" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">After inserting node in Empty List</td></tr>
</tbody></table>
<br />
Scene 2: When List contains node having <b><i>V</i></b><i style="font-weight: bold;">alue=10 </i>in its data field, in the list (As Shown in Image Below.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAPASxDnxeBfinI6GQ2eZIayFo8kerWwFmxxKuEdVCNTvFm23UBkmh3cODc59ebiHVOsoAkG8lrwXbWJJP0YpovH2bLMSl1j_0tuWdAmmpD_a7mhhnUb1xFEE87yxCAwhK3y2ztKT-CNvR/s1600/List.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="113" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAPASxDnxeBfinI6GQ2eZIayFo8kerWwFmxxKuEdVCNTvFm23UBkmh3cODc59ebiHVOsoAkG8lrwXbWJJP0YpovH2bLMSl1j_0tuWdAmmpD_a7mhhnUb1xFEE87yxCAwhK3y2ztKT-CNvR/s640/List.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">List </td></tr>
</tbody></table>
<br />
In this case The node with <i style="font-weight: bold;">Value=10 </i>in its data field will be searched as the logic is written in the <i>step 5</i><br />
<i><br /></i>
<i><b>Ptr = Start</b></i><br />
<i><b><br /></b></i>
<i><u>1st Iteration</u> <b>Ptr->Next < > null</b></i><br />
<i> <b>Ptr -> Data = 54</b></i><br />
<b style="font-style: italic;"> </b><span style="font-style: italic;">since</span><b style="font-style: italic;"> </b><i><b>Ptr ->Data < > Value </b>so <b>Ptr = Ptr->Next = 2044</b></i><br />
<i><b><br /></b></i>
<i><u>2nd Iteration</u><b> Ptr->next < > null</b></i><br />
<br />
<i> <b>Ptr -> Data = 45</b></i><br />
<b style="font-style: italic;"> </b><span style="font-style: italic;">since</span><b style="font-style: italic;"> </b><i><b>Ptr ->Data < > Value </b>so <b>Ptr = Ptr->Next = 5260</b></i><br />
<i><u>3rd Iteration</u><b> Ptr->next < > null</b></i><br />
<i><b> Ptr->Data = 10</b></i><br />
<i><b> </b>since <b>Ptr->Data = Value </b>so</i><br />
<i> [Now we have found our position]</i><br />
<i><br /></i>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOgEYG6qfKOKz4sU_uOfgANKfwTzwiPKEnJC7fZGOIITvhRO1JIAXO2H2WSsP_iakfmy0xK9h4tgZ6BbTjLRUgkSKPPnDlZi5iVH_CW50fES6Q38IGYJ6Uu8-GHf3IJLdYYOSJCqSOyUOT/s1600/NodeInserting.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="172" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOgEYG6qfKOKz4sU_uOfgANKfwTzwiPKEnJC7fZGOIITvhRO1JIAXO2H2WSsP_iakfmy0xK9h4tgZ6BbTjLRUgkSKPPnDlZi5iVH_CW50fES6Q38IGYJ6Uu8-GHf3IJLdYYOSJCqSOyUOT/s640/NodeInserting.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Inserting Node</td></tr>
</tbody></table>
<i><br /></i>
<i> <b>Node->next = Ptr->next</b></i><br />
<i><b> Ptr->next = Node</b></i><br />
<i><b><br /></b></i>
So Final List is:<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9ewuYhSGJ1OVGSgfQjjapzvDhwRVfNSeq8EK0BqQluS53g-3ZMRA18_h33Lw4hXvTN7ygr-kkAz4n7oo4UKgeHc_ag-03k3DpDAvGurshqu-4PqipNWF4P-anf7xM3rV_gkarIZTAOzTn/s1600/NodeInserted.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="160" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9ewuYhSGJ1OVGSgfQjjapzvDhwRVfNSeq8EK0BqQluS53g-3ZMRA18_h33Lw4hXvTN7ygr-kkAz4n7oo4UKgeHc_ag-03k3DpDAvGurshqu-4PqipNWF4P-anf7xM3rV_gkarIZTAOzTn/s640/NodeInserted.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Node Inserted</td></tr>
</tbody></table>
<br />
Similarly if node with <i style="font-weight: bold;">value </i>doesn't exist or exists at the end of list then new node will be added at the end of list.<br />
<div>
<i><b><br /></b></i></div>
</div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-87125785698280149712012-11-26T00:22:00.004-08:002014-04-10T05:51:00.218-07:00Algorithm: Binary Search in Array<div dir="ltr" style="text-align: left;" trbidi="on">
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<sub>2</sub>n). In this algorithm all the elements in the array must be sorted.<br />
<br />
<h3 style="text-align: left;">
BinarySearch(ArrayValues[], n, searchValue, LB, UB)</h3>
<div>
Here <i>ArrayValues</i> is an array of size <i>n, </i>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.</div>
<div>
<a name='more'></a><br /></div>
<div>
Step 1: till <i><b>LB<=UB</b></i> repeat <b>step 2 and 3 </b></div>
<div>
Step 2: Mid = (LB + UB)/2</div>
<div>
Step 3: i) if ArrayValues[Mid] = searchValue then <b><i>return Mid.</i></b></div>
<div>
ii) if ArrayValues[Mid] > searchValue then </div>
<div>
a) <b>UB = Mid-1</b></div>
<div>
else</div>
<div>
a) <b>LB = Mid+1</b></div>
<div>
Step 4: return -1</div>
<div>
<br /></div>
<div>
<br /></div>
<div class="BSExplainFlip">
<h4 style="text-align: left;">
<b>Click here for Explanation</b></h4>
</div>
<div class="BSExplainDiv" style="display: none;">
<div>
<b><u>Scene 1</u></b></div>
<div>
<i>searchValue = 18; LB=0; UB=6</i></div>
<div>
<i>ArrayValues => 15 18 19 21 25 28 31 </i></div>
<div>
<i>Indexes 0 1 2 3 4 5 6</i></div>
<div>
<i><br /></i></div>
<div>
1st Iteration:</div>
<div>
<i>Mid = (6+0) = 3; ArrayValues[Mid] = 21 => ArrayValues[Mid] > SearchValue</i></div>
<div>
<i><b>so </b>LB = 0; UB = Mid - 1 = 2</i></div>
<div>
<i><br /></i></div>
<div>
2nd Iteration</div>
<div>
<i>Mid = (2+0) / 2 = 1; ArrayValues[Mid] = 18 = searchValue</i></div>
<div>
<i><br /></i></div>
<div>
<i>Return 18</i></div>
<div>
<i><br /></i></div>
<div>
<b><u>Scene 2</u></b></div>
<div>
<div>
<i>searchValue = 17; LB=0; UB=6</i></div>
<div>
<i>ArrayValues => 15 18 19 21 25 28 31 </i></div>
<div>
<i>Indexes 0 1 2 3 4 5 6</i></div>
<div>
<i><br /></i></div>
<div>
1st Iteration:</div>
<div>
<i>Mid = (6+0) = 3; ArrayValues[Mid] = 21 => ArrayValues[Mid] > searchValue</i></div>
<div>
<i><b>so </b>LB = 0; UB = Mid - 1 = 2</i></div>
<div>
<i><br /></i></div>
<div>
2nd Iteration</div>
<div>
<i>Mid = (2+0) / 2 = 1; ArrayValues[Mid] = 18 => </i><i>ArrayValues[Mid] > searchValue</i></div>
</div>
<div>
<i><b>So </b>LB = 0; UB = Mid-1 = 0</i></div>
<div>
<i><br /></i></div>
<div>
3rd Iteration</div>
<div>
<i>Mid = (0+0)/2) = 0; ArrayValues[Mid] = 15 => ArrayValues[Mid] < searchValue</i></div>
<div>
<i><b>So </b>LB = Mid +1 = 1; UB = 0</i></div>
<div>
<i><br /></i></div>
<div>
4th Iteration</div>
<div>
LB>UB [search failed]</div>
<div>
return -1;</div>
</div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-28185674721396543032012-11-24T00:03:00.000-08:002012-11-28T23:41:53.016-08:00Algorithm: Linear Search For Array<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
In Linear Search algorithm whole array is traversed to search the element untill the element found.<br />
<h3 style="text-align: left;">
Linear_Search(valArr[], n, searchValue)</h3>
<div>
Here <i>valArr[]</i> is of length <i>n</i>, and <i>SearchValue </i> 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.</div>
<div>
<br /></div>
<div>
<i>Step1</i>: [Iterate the array]</div>
<div>
For index=1 to n repeat step 2 and 3</div>
<div>
<br /></div>
<div>
<i>Step2</i>: if valArr[index]=searchValue then goto step 2(i) else goto step 3</div>
<div>
i) return index</div>
<div>
<br /></div>
<div>
<i>Step3</i>: if index=n then goto step 3(i) else goto step 3(ii)</div>
<div>
i) return -1;</div>
<div>
ii) index=index-1;</div>
<div>
<br /></div>
<div>
<i>Step4</i>: End.</div>
<div>
<br /></div>
<br />
<a name='more'></a><br />
<br />
<b>Explanation:</b><br />
Suppose valArr is an array with the elements [10,23,12,14,18,19]. (Its size is n=6). Suppose we have to search element <i>searchValue=14. </i><br />
<i><br /></i>
<i>when Index =1 </i><br />
<br />
valArr: 10 23 12 14 18 19<br />
<br />
Search Value 14<br />
<br />
Search Status: <b><span style="color: red;">X</span></b><br />
<br />
<i><br /></i>
<i>When Index=2</i><br />
<i><br /></i>
<br />
valArr: 10 23 12 14 18 19<br />
<br />
Search Value 14<br />
<br />
Search Status: <span style="color: red;"><b>X</b></span><br />
<br />
<br />
<i><br /></i>
<i>When Index=3</i><br />
<i><br /></i>
<br />
valArr: 10 23 12 14 18 19<br />
<br />
Search Value 14<br />
<br />
Search Status: <span style="color: red;"><b>X</b></span><br />
<br />
<br />
<br />
<br />
<br />
<i>When Index=4</i><br />
<i><br /></i>
<br />
valArr: 10 23 12 14 18 19<br />
<br />
Search Value 14<br />
<br />
Search Status: <span style="background-color: white; font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;"><span style="color: lime;"><b>√</b></span></span><br />
<span style="background-color: white; font-family: verdana, geneva, lucida, 'lucida grande', arial, helvetica, sans-serif; font-size: 13px;"><span style="color: lime;"><b><br /></b></span></span>
<span style="font-family: verdana, geneva, lucida, lucida grande, arial, helvetica, sans-serif; font-size: x-small;"><b><i>return 4;</i></b></span><br />
<br />
<div>
<br /></div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-36930121797114115742012-11-21T22:36:00.003-08:002012-11-21T22:36:52.672-08:00Algorithm: To remove element from Array<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Algorithm: RemoveElementFromArray(rIndex,<i>valArray[],n,removedData</i>)</h3>
<div>
In this algorithm rIndex is index from which element is to be removed and n is the size of array <i>valArray. removedData will contain the value which is removed from array from index rIndex.</i></div>
<div>
<i>*</i><b>consider lower bound of array is 1.</b></div>
<div>
<b><br /></b></div>
<pre style="background-color: #f1eee5; border: thin dashed green; color: blue; font-family: Tahoma; height: 370px; overflow: scroll; text-align: left; width: 90%;">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 <b>step a to b</b>
a) valArray[index] = valArray[index+1]
b) index= index+ 1
ii) valArray[index] = <i>null</i>
Step 4: End
</pre>
<br />
<br />
<b>Explanation</b><br />
<b></b><br />
<a name='more'></a>Consider size of <i>valArray </i>is 5 ( i.e. n=5), and it contains total 5 elements which are [15,18,12,3,4], and we have to remove element from index 3(i.e. rIndex = 3).<br />
<br />
<br />
current <i>valArray is</i><br />
<i><br /></i> Data<i> 15 18 12 3 4</i><br />
<b>Array Index 1 2 3 4 5</b><br />
<div>
<b><br /></b></div>
<div>
<b><i>since rIndex = 3 which is less than n=5, so it will move to step 2</i></b></div>
<div>
<i>at step 2:</i></div>
<div>
<i>removedData = valArray[3] => removedData = 12;</i></div>
<div>
<i><br /></i></div>
<div>
<i><b>now it will move to step 3:</b></i></div>
<div>
<i><b><br /></b></i></div>
<div>
<i><b>when index = 3</b></i></div>
<div>
Data<i> 15 18 3 3 4</i><br />
<b>Array Index 1 2 3 4 5</b></div>
<div>
<b><br /></b></div>
<div>
<b><i>when index = 4</i></b></div>
<div>
<div>
<br />
Data<i> 15 18 3 </i><i>4</i><i> 4</i><br />
<b>Array Index 1 2 3 4 5</b></div>
</div>
<div>
<b><br /></b>
<b><i>when index =5 </i></b><br />
<b><i>Control will be exited from loop & will move to step 3(ii)</i></b><br />
<b><i><br /></i></b>
<b><i>after the step </i></b><br />
<b><i><br /></i></b>
<br />
<div>
Data<i> 15 18 3 </i><i>4</i><i> x</i><br />
<b>Array Index 1 2 3 4 5</b></div>
<div>
<b><br /></b></div>
<div>
</div>
</div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-53756830917174831972012-11-21T22:03:00.001-08:002012-11-21T22:03:34.003-08:00DSA Tutorials: Algorithm: To insert element in array<a href="http://www.dsatutorial.blogspot.in/2012/11/arrays.html">Array Introduction</a>Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-38720159851222091332012-11-21T21:49:00.002-08:002012-11-21T22:27:05.635-08:00Algorithm: To insert element in array<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Algorithm: InsertElementInArray(dataVal, valArray[], n, k,m)</h3>
In this algorithm <i>dataVal</i> is an element which is to be inserted in an array named <i>valArray</i>, whose size is <i>n. </i>we have to insert the element <i>dataVal </i>at<i> </i>index<i> k. m </i>is the total present elements in the array where m<n<br />
<i><b>*considering lower bound of array is 1.</b></i></div>
</div>
<br />
<pre linecount="on" style="background-color: #f1eee5; border-color: Green; border-style: dashed; border-width: thin; color: blue; font-family: Tahoma; height: 400; list-style-type: circle; overflow: scroll; width: 90%;">Step 1: [Check for the size of array]
<i>if n < k then</i>
<i> a) RaiseError "Array Index out of bound"</i>
<i> b) goto step 5</i>
Step 2: [Shifting the elements from k indexed elements by 1]
i) for <i>index = m to k repeat <b>step a to b</b></i>
a) <i>valArray[index+1] = valArray[index]</i>
b) [Decrements counter] index = index - 1
ii) goto to step 3
Step 3: [Now Insert the element]
<i>valArray[k] = dataVal;</i>
Step 4: Exit
</pre>
<b><br /></b>
<b>Explanation</b><br />
<br />
<a name='more'></a>Consider size of <i>valArray </i>is 8 ( i.e. n=8), and it contains total 5 elements which are [15,18,12,3,4] at present (i.e. m=5), <i>dataVal =10 </i>which is to be inserted at index 3 (i.e. k=3).<br />
<br />
current <i>valArray is</i><br />
<i><br /></i>
Data<i> 15 18 12 3 4 x x x </i><br />
<b>Array Index 1 2 3 4 5 6 7 8</b><br />
<b><br /></b>
<b>since k=3 which is less than n=8 so it will move to step 2</b><br />
<b><br /></b>
<b><i>when index = m = 5</i></b><br />
<b><br /></b>
<br />
Data<i> 15 18 12 3 4 4 x x </i><br />
<b>Array Index 1 2 3 4 5 6 7 8</b><br />
<b><br /></b>
<b><i>when index m = 4</i></b><br />
<b><i><br /></i></b>
<br />
Data<i> 15 18 12 3 3 4 x x </i><br />
<b>Array Index 1 2 3 4 5 6 7 8</b><br />
<b><br /></b>
<b><i>when index = 3 = k</i></b><br />
<b><i><br /></i></b>
<br />
Data<i> 15 18 12 12 3 4 x x </i><br />
<b>Array Index 1 2 3 4 5 6 7 8</b><br />
<br />
<div>
<b><br /></b></div>
<div>
<b><i>now decrement of index will make index < k so it will now </i></b><br />
<b><i><br /></i></b>
<b><i>after execution of step 3:</i></b><br />
<b><i><br /></i></b>
<br />
Data<i> 15 18 <b>10</b> 12 3 4 x x </i><br />
<b>Array Index 1 2 3 4 5 6 7 8</b><br />
<b><br /></b>
<b>End</b></div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-80880333420303023022012-11-21T05:19:00.002-08:002012-11-21T21:03:05.500-08:00Linked List<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Definition</h3>
<div>
A Linked List is a linear collection of data element(where linearity is achieved by pointers in node) with following properties:.</div>
<div>
<ol style="text-align: left;">
<li>Each element of Linked list is called <i>Node</i></li>
<li>There is a pointer called <i>start. </i>Which contains address of first <i>Node</i></li>
<li>Each <i>Node</i> has atleast two part. 1st is data part another is pointer part. Data part contains actual data. and pointer part contains address of next <i>Node</i>.</li>
<li>Pointer of Last Node of Linked List contains <i>null.</i></li>
</ol>
<h3 style="text-align: left;">
Types of Linked List</h3>
</div>
<div>
<ol style="text-align: left;">
<li>Simple Linked List</li>
<li>Header Linked List</li>
<li>Circular Linked List</li>
<li>Two way Linked List</li>
<li>Hybrid Linked List</li>
</ol>
<h3 style="text-align: left;">
<a name='more'></a>Simple Linked List</h3>
</div>
<div>
A simple Linked List is a collection of data elements called Nodes with following properties:</div>
<div>
<ol style="text-align: left;">
<li>Start Pointer will contain address of 1st node.</li>
<li>Pointer of node contains address of next node.</li>
<li>Pointer field of last node contains null value.</li>
</ol>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinidQ0PlIOut-h1xkhFLbNn7hYu1RfqMVGkNzIPkDj7PH1RaDwJi18bCo9rbDmKjz9-XyKxB61rZyx8l8zz31zYnFjn5o0mcRsx3kMK9inAwRaXrpdpaK8sS_RmA2rWWnz4e__M_J-gUpl/s1600/simple+Linked+List.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="" border="0" height="83" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinidQ0PlIOut-h1xkhFLbNn7hYu1RfqMVGkNzIPkDj7PH1RaDwJi18bCo9rbDmKjz9-XyKxB61rZyx8l8zz31zYnFjn5o0mcRsx3kMK9inAwRaXrpdpaK8sS_RmA2rWWnz4e__M_J-gUpl/s640/simple+Linked+List.png" title="" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Simple Linked List</td></tr>
</tbody></table>
<h3 style="text-align: left;">
Header Linked List</h3>
<div>
A Header Linked List is a collection of data elements called Nodes with following properties:</div>
<div>
<ol style="text-align: left;">
<li>1st node will be header node.(Header node is a special type of node which contains information about the list. (like: No of nodes, size of nodes etc)</li>
<li>Start pointer will contains address of header node.</li>
<li>[remaining properties are same as Simple linked list]</li>
</ol>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaG2EWrLtvFv2hn5Xvjng4hOl06Wyt2iVQrurjH_yftWpXmcX_2m7WjP5B2K0W57BUXHjTzMcJFq_HKArSpDqN2ghYniTk5Q1n94v4Y8btr30UnLw_sos0jC6E_P75n0dNQYIB9LpG_ynB/s1600/Header.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="84" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaG2EWrLtvFv2hn5Xvjng4hOl06Wyt2iVQrurjH_yftWpXmcX_2m7WjP5B2K0W57BUXHjTzMcJFq_HKArSpDqN2ghYniTk5Q1n94v4Y8btr30UnLw_sos0jC6E_P75n0dNQYIB9LpG_ynB/s640/Header.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Header Linked List</td></tr>
</tbody></table>
<div>
<br /></div>
</div>
<h3 style="text-align: left;">
Circular Linked List</h3>
</div>
<div>
A circular Linked List is a collection of data elements called Nodes with following properties:</div>
<div>
<ol style="text-align: left;">
<li>Start Pointer contains address of 1st Node.</li>
<li>Pointer of node contains address of next node.</li>
<li>Pointer field of last node contains address of First node.</li>
</ol>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyZV6Iju-DSE4-eStJTDsCtCqAq47yK1y8VIUg9OQlzhOCvNTOeVuy9Xb-GqB-vj66L6rLOZPS50w1KnF0tv-rtT_E7mw2lzuPS8TorEuLTQO17BVXFpCTK7OvPJjWeo3PC01rANaBahea/s1600/CLinkedList.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="126" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyZV6Iju-DSE4-eStJTDsCtCqAq47yK1y8VIUg9OQlzhOCvNTOeVuy9Xb-GqB-vj66L6rLOZPS50w1KnF0tv-rtT_E7mw2lzuPS8TorEuLTQO17BVXFpCTK7OvPJjWeo3PC01rANaBahea/s640/CLinkedList.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Circular Linked List</td></tr>
</tbody></table>
<h3 style="text-align: left;">
Two Way Linked List</h3>
</div>
<div>
A Two way Linked List is a collection of data elements called nodes with following properties:</div>
<div>
<ol style="text-align: left;">
<li>There are two pointers <i>Start </i>and <i>End. Start </i>contains address of First Node, <i>End </i>contains address of Last Node.</li>
<li>Each Node has two pointer fields and 1 data field. 1 pointer field contains address of previous node is called <i>Prev. </i>Another pointer field contains address of next node is called <i>Next.</i></li>
<li><i>Prev </i>of 1st node and <i>Next </i>of Last node contains <i>Null.</i></li>
</ol>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvqU2XndHZtkSZgN_T2Q7e-oEe-3vKvObqYsq7GDbLljyPMlbzXk7c1BLUcHHbmciUwwayrdAHFZI4XE-zU2h4pVrvXP08rl3LFSpbHDiCPirDR0yY0HmIcExuxgUG8WrsHinZ6Lo9xHNW/s1600/2wayLL.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="70" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvqU2XndHZtkSZgN_T2Q7e-oEe-3vKvObqYsq7GDbLljyPMlbzXk7c1BLUcHHbmciUwwayrdAHFZI4XE-zU2h4pVrvXP08rl3LFSpbHDiCPirDR0yY0HmIcExuxgUG8WrsHinZ6Lo9xHNW/s640/2wayLL.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Two Way Linked List</td></tr>
</tbody></table>
<div>
<i><br /></i>
<h3 style="text-align: left;">
Hybrid Linked List</h3>
</div>
</div>
<div>
A hybrid linked list is a special type of linked list, it is actually combination of two or more type of linked lists.</div>
<div>
For Example</div>
<div>
It can be <i>Header Circular Linked list or Header Two way linked list or it can Circular Two way linked list</i></div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-89121766909225053072012-11-20T01:48:00.001-08:002012-11-21T21:08:00.806-08:00Arrays<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Defination: </h3>
Array is a collection of homogeneous data elements with following properties<br />
<ol>
<li>All the data elements are stored contiguous memory location</li>
<li>Data elements are accessed with index number.</li>
</ol>
There are 3 types of Array<br />
<ul>
<li>1-D Array (Linear Array)</li>
<li>2-D Array (Matrix)</li>
<li>N-D Array (Multidimensional Array)</li>
</ul>
<h4 style="text-align: left;">
<u><a name='more'></a>Linear Array</u></h4>
<div style="text-align: left;">
<strong> </strong>In this type of array there will be single index all the element of array will be stored in contiguous memory location. NAME of array is actually a pointer which points the 1st element of Array.</div>
<h4 style="text-align: left;">
Declaration</h4>
<div style="text-align: left;">
<u>In C:</u> <em>data_type</em> arrName[array_size]</div>
<div style="text-align: left;">
<em> in c starting index of array is always 0</em></div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
<u>General Way:</u> declare <em>arrName</em><strong>[LB, UB]</strong> as <em>DataType</em></div>
<div style="text-align: left;">
<em> *LB - Lower Bound</em></div>
<div style="text-align: left;">
<em> *UB - Upper Bound</em></div>
<div style="text-align: left;">
<strong>Access Element</strong></div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
<u>In C:</u> arrName[ELEMENT_INDEX]</div>
<div style="text-align: left;">
where ELEMENT_INDEX must be from <em>0</em> to <em>array_size -1 </em></div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
<strong>Total Size of Array</strong></div>
<div style="text-align: left;">
<strong> </strong>Size of array can be found by following formulas</div>
<div style="text-align: left;">
Array_Size = UB - LB + 1</div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
<strong>Memory allocation of Linear Array</strong></div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
Suppose we have n elements in an array which are allocated memory from starting location <em>100</em>, and each element of the array is having size of <em>2</em> bytes. so that 1st element of the array will be stored at index memory location <em>100</em> and next element will be stored at memory location <em>102, </em>this will be continued for nth element<em>.</em></div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1Mv9-ktWi5jUYzvHYKLAe1nUI7_9X1uh_1BBjcRuwwQR6Rq5PcxbPlmeOFNsDZU3QmU7gkGsBVMLresLkLLxEzvSHan0nkGbaxfKvX5Ne7NC1Vjs4Y9cO2cmqEiIRKep7vLi4sZbnRD5l/s1600/img3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1Mv9-ktWi5jUYzvHYKLAe1nUI7_9X1uh_1BBjcRuwwQR6Rq5PcxbPlmeOFNsDZU3QmU7gkGsBVMLresLkLLxEzvSHan0nkGbaxfKvX5Ne7NC1Vjs4Y9cO2cmqEiIRKep7vLi4sZbnRD5l/s1600/img3.png" /></a></div>
</div>
<div style="text-align: left;">
<em></em> <b>Calculation of memory location for mth element of array</b><br />
<b><br /></b>
To fetch the element of index m from the array we use following formula<br />
<br />
Add_Of_Element_m = Base_Address+size * (m - LB)<br />
where Base_Address: <i>Address of starting element</i><br />
<i> </i>size: <i>Size of element</i><br />
m: <i>Index of the element whose address is to be found.</i><br />
LB: <i>Lower Bound of array</i><br />
<b><br /></b>
<i> <u> Example</u></i><br />
<i>Suppose we have an array having 10 elements, Lower Bound of array is 0, Starting address of Array is 1200, element size is 4 bytes, than what will be the address of element of index 5.</i><br />
<br />
<i><b> Soln:</b></i><br />
<i><b> </b>we are given: </i><br />
<i> Base_Address = 1200, size=4, LB=0, m = 5</i><br />
<i> Add_of_Element_m = 1200+4*(5-0)</i><br />
<i> Add_of_Element_m = <b>1220 --> Ans.</b></i><br />
<i><br /></i>
<br />
<h4 style="text-align: left;">
<b><u>2-D Array</u></b></h4>
<div>
These are also known as <b><i>Matrix</i></b>. These are collection of homogeneous data elements in rows and columns format. The name of 2 D array is actually a pointer which points the element at 1st Row and 1st Index.</div>
<div>
<br /></div>
<div>
<b>Declaration</b></div>
<div>
<u>General Way</u>: <i>declare arr[LBR,UBR][LBC,UBC] as DataType</i></div>
<div>
<u>In C</u>: <i>data_type arr_Name[NO_OF_ROWS][NO_COLS];</i></div>
<div>
<i> *LBR: Lower Bound for Rows; UBR: Upper Bound for Rows</i></div>
<div>
<i> *LBC: Lower Bound for Columns; UBC: Upper Bound for Columns</i></div>
<div>
<i> *NO_OF_ROWS: No of Rows</i></div>
<div>
<i> *NO_OF_COLS: No of Columns</i></div>
<div>
<b>Accessing Element</b></div>
<div>
<u>In C:</u><i> </i>arr_Name[Row_Index][Col_Index]</div>
<div>
where <b>Row_Index</b> is index of row 0<= <b>Row_Index</b>< NO_OF_ROWS</div>
<div>
<b>Col_Index </b>is index of columns 0<=<b>Col_Index</b>< NO_OF_COLS</div>
<div>
<b><br /></b></div>
<div>
<b>Total size of Matrix</b></div>
<div>
<b><br /></b></div>
<div>
Total Size of Matrix is given by below formula:<br />
NO_OF_ROWS = UBR - LBR +1<br />
NO_OF_COLS = UBC-LBC+1</div>
<div>
SIZE_OF_MATRIX = NO_OF_ROWS * NO_OF_COLS<br />
<br /></div>
<div>
<b>Memory Allocation For Matrix</b><br />
There are two ways in which <i>matrix </i>can be allocated memory these are:<br />
<i>1. Row Major</i><br />
<i>2. Column Major</i><br />
<b><br /></b>
<br />
<ul style="text-align: left;">
<li><b>Row Major: </b>In this scenario matrix is stored in memory Row by Row. For Eg: Suppose there is a matrix of called <i>Mat[3][4]. </i>Starting location(Base address) of matrix is 2000, in this case LBR=0,UBR=2; LBC=0,LBR=3. For <i>Row Major </i>memory allocation (Row 1)<i>Mat[0][0],Mat[0][1],Mat[0][2],Mat[0][3],</i>(Row 2) <i>Mat[1][0],Mat[1][1]... </i>will be the sequence.</li>
<ul>
<li><b>Memory Location for i,j element of Matrix in Row Major Allocation</b></li>
</ul>
</ul>
<b> i: </b><i>row index of element</i></div>
<div>
<i> </i><b>j: </b><i>column index of element</i></div>
<div>
<i> </i><i style="font-weight: bold;">size: </i>size of datatype </div>
<div>
<b>m: </b>no. of rows</div>
<div>
<b> n: </b>no. of cols</div>
<div>
<b>LBC: </b>Lower bound of columns</div>
<div>
<b> LBR: </b>Lower bound of Row</div>
<div>
<b>BA: </b>Base Address</div>
<div>
LOC_OF_IJ_ELEMENT = <b>BA + size * [(i-LBR)*n + (j-LBC)]</b><br />
<ul style="text-align: left;">
<li><b>Column Major: </b>In this scenario matrix is stored in memory column by column. For Eg: Suppose there is a matrix of called <i>Mat[3][4]. </i>Starting location(Base address) of matrix is 2000, in this case LBR=0,UBR=2; LBC=0,LBR=3. For <i>Column Major</i> memory allocation (Column1)<i>Mat[0][0],Mat[1][0],Mat[2][0],</i>(Column2)<i> Mat[0][1],Mat[1][1]... </i>will be the sequence.</li>
<ul>
<li><b>Memory Location for i,j indexed element of Matrix in Column allocation</b></li>
</ul>
</ul>
<div>
<b> i: </b><i>row index of element</i></div>
<div>
<i> </i><b>j: </b><i>column index of element</i></div>
<div>
<i> </i><i style="font-weight: bold;">size: </i>size of datatype </div>
<div>
<b>m: </b>no. of rows</div>
<div>
<b> n: </b>no. of cols</div>
<div>
<b>LBC: </b>Lower bound of columns</div>
<div>
<b> LBR: </b>Lower bound of Row</div>
<div>
<b>BA: </b>Base Address</div>
<div>
LOC_OF_IJ_ELEMENT = <b>BA + size * [(i-LBR) + (j-LBC)*m]</b><br />
<ul></ul>
</div>
<div>
<b><br /></b></div>
</div>
</div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
</div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0tag:blogger.com,1999:blog-7326512468483168213.post-54452962338355613152012-11-16T00:35:00.001-08:002012-11-21T20:52:49.766-08:00DSA: Introduction<div dir="ltr" style="text-align: left;" trbidi="on">
<h2 style="text-align: left;">
Definitions<b>: </b></h2>
<div style="text-align: left;">
1. <b><u>Data Structure</u></b>: <span style="font-weight: normal;">A mathematical or logical representation of data in memory is called <i>data structure</i>.</span></div>
2. <b><u>Algorithm</u></b>: A step by step solution to any problem is called <i>algorithm.</i><br />
<i><br /></i>
<br />
<h2 style="text-align: left;">
Introduction to Data Structure:</h2>
<div>
As we have gone through the definition of data structure "It is mathematical or logical representation of data in memory". </div>
<div>
<br /></div>
<h3 style="text-align: left;">
Classification:</h3>
<div>
There are two type of Data Structures according to memory representation<br />
<a name='more'></a></div>
<h4 style="text-align: left;">
</h4>
<h4 style="text-align: left;">
1. Contiguous Data Structures:</h4>
<div>
Those data structures for which contiguous memory is allocated for its data. </div>
<div>
<i>For Eg: Array, String, Stack(Array Implementation), Queue(Array Implementation), Tree( Array Implementation)</i></div>
<h4 style="text-align: left;">
</h4>
<h4 style="text-align: left;">
2. Non Contiguous Data Structures</h4>
<div>
Those data structures for which memory allocation is non contiguous for its data.</div>
<div>
<i>For Eg: Linked List, Queue, Stack, Tree, Graph(Linked List Implementation of all these), Hash Table etc.</i></div>
<div>
<i><br /></i></div>
<h3 style="text-align: left;">
Operations That can be performed on Data structures</h3>
<div>
Following operations can be performed on the data structures:</div>
<h4 style="text-align: left;">
</h4>
<h4 style="text-align: left;">
1. Insertion</h4>
<div>
A new element can be inserted in the data structure at specific position depending on data structure. For Example:</div>
<div>
a) In array we can insert element at starting index, last index, mid of array etc.</div>
<div>
b) In stack we can insert element at the top of stack.</div>
<div>
c) In normal Queue we can insert element at the rear of queue.</div>
<div>
d) In Linked List we can insert element at start, at end or at mid of List.<br />
<br /></div>
<h4 style="text-align: left;">
2. Deletion</h4>
<div>
An existing element can be removed/deleted from the data structures from specific position depending on data structure. For Example</div>
<div>
a) From <i>array</i> we can delete element from starting index, last index, mid of array etc.</div>
<div>
b) From <i>stack </i>we can delete element from the top of stack.</div>
<div>
c) From <i>Queue</i> we can delete element from the rear of queue.</div>
<div>
d) From Linked list we can delete element from start, from end or from mid of List.</div>
<h4 style="text-align: left;">
</h4>
<h4 style="text-align: left;">
3. Traversing</h4>
<div>
Processing of each element of data structure is called traversing of data structure. All the elements of the data structure can be traversed in specific manner.</div>
<h4 style="text-align: left;">
</h4>
<h4 style="text-align: left;">
4. Mergeing</h4>
<div>
Two same data structures can be merged and resulted into a single data structure.</div>
<h4 style="text-align: left;">
</h4>
<h4 style="text-align: left;">
5. Sorting</h4>
<div>
Elements of the data structures can be sorted in specific manner. This is not applicable for all the data structures.</div>
<div>
<i><br /></i></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
</div>
Adminhttp://www.blogger.com/profile/05747737716676578216noreply@blogger.com0