📄 page197.html
字号:
<HTML><HEAD><TITLE>Inserting Items in a Sorted List</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html3476" HREF="page198.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3474" HREF="page196.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3468" HREF="page196.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3478" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION007221000000000000000">Inserting Items in a Sorted List</A></H3><P>Program <A HREF="page197.html#progsortedListAsLinkedListb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>gives the implementation of the <tt>insert</tt>method of the <tt>SortedListAsLinkedList</tt> class.In addition to <tt>self</tt>,this method takes a single argument:the object to be inserted into the sorted list.The algorithm used for the insertion is as follows:First, the existing sorted, linked list is traversedin order to find the linked list element which is greater than or equalto the object to be inserted into the list.The traversal is done using two variables--<tt>prevPtr</tt> and <tt>ptr</tt>.During the traversal,the latter keeps track of the current elementand the former keeps track of the previous element.<P>By keeping track of the previous element,it is possible to efficiently insert the new item into the sorted listby calling the <tt>insertAfter</tt> method of the<tt>LinkedList</tt> class.In Chapter <A HREF="page81.html#chapfds"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the <tt>InsertAfter</tt> method was shown to be <I>O</I>(1).<P>In the event that the item to be inserted is smaller than the first itemin the sorted list,then rather than using the <tt>insertAfter</tt> method,the <tt>prepend</tt> method is used.The <tt>Prepend</tt> method was also shown to be <I>O</I>(1).<P>In the worst case, the object to be inserted into the linked listis larger than all of the objects already present in the list.In this case, the entire list needs to be traversedbefore doing the insertion.Consequently, the total running time for the <tt>insert</tt>operation of the <tt>SortedListAsLinkedList</tt> class is <I>O</I>(<I>n</I>),where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline60691" SRC="img663.gif" >.<P><P><A NAME="10464"> </A><A NAME="progsortedListAsLinkedListb"> </A> <IMG WIDTH=575 HEIGHT=352 ALIGN=BOTTOM ALT="program10251" SRC="img814.gif" ><BR><STRONG>Program:</STRONG> <tt>SortedListAsLinkedList</tt> class <tt>insert</tt> method.<BR><P><HR><A NAME="tex2html3476" HREF="page198.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3474" HREF="page196.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3468" HREF="page196.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3478" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -