page181.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 71 行
HTML
71 行
<HTML><HEAD><TITLE>Inserting and Accessing Items in a 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="tex2html3296" HREF="page182.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3294" HREF="page179.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3288" HREF="page180.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3298" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION007122000000000000000">Inserting and Accessing Items in a List</A></H3><P>Program <A HREF="page179.html#progorderedListAsLinkedLista"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> givesthe code for the <tt>__init__</tt> methodof the <tt>OrderedListAsLinkedList</tt> class.The <tt>__init__</tt> method simply creates an empty linked list.Clearly, the running time of the <tt>__init__</tt> method is <I>O</I>(1).<P>Program <A HREF="page181.html#progorderedListAsLinkedListb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> givesthe code for the <tt>insert</tt> and <tt>__getitem__</tt> methodsof the <tt>OrderedListAsLinkedList</tt> class.The <tt>insert</tt> method takes an objectand adds it to the ordered list.As in the case of the <tt>ArrayAsLinkedList</tt> class,the object is added at the end of the ordered list.This is done simply by calling the <tt>append</tt>method from the <tt>LinkedList</tt> class.<P><P><A NAME="9881"> </A><A NAME="progorderedListAsLinkedListb"> </A> <IMG WIDTH=575 HEIGHT=332 ALIGN=BOTTOM ALT="program9387" SRC="img752.gif" ><BR><STRONG>Program:</STRONG> <tt>OrderedListAsLinkedList</tt> class <tt>insert</tt> and <tt>__getitem__</tt> methods.<BR><P><P>The running time of the <tt>insert</tt> method is determinedby that of <tt>append</tt>.In Chapter <A HREF="page81.html#chapfds"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> this was shown to be <I>O</I>(1).The only other work done by the <tt>insert</tt> method is toadd one to the <tt>_count</tt> variable.Consequently, the total running time for <tt>insert</tt> is <I>O</I>(1).<P>Program <A HREF="page181.html#progorderedListAsLinkedListb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> also defines the <tt>__getitem__</tt> method.In addition to <tt>self</tt>,the <tt>__getitem__</tt> method takes an argument of type <tt>int</tt>.This method is used to access elements of the ordered listby their position in the list.In this case, the position is specified by a non-negative,integer-valued index.Since there is no way to access directlythe <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > element of linked list,the implementation of this method comprises a loopwhich traverses the list to find the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > item.The method returns a reference to the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > item,provided <IMG WIDTH=103 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61069" SRC="img753.gif" >.Otherwise, <I>i</I> is not a valid subscript valueand the method raises an exception.<P>The running time of the accessor method dependson the number of items in the listand on the value of the subscript expression.In the worst case,the item sought is at the end of the ordered list.Therefore, the worst-case running time of this algorithm,assuming the subscript expression is valid,is <I>O</I>(<I>n</I>), where <IMG WIDTH=78 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61037" SRC="img743.gif" >.<P><HR><A NAME="tex2html3296" HREF="page182.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3294" HREF="page179.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3288" HREF="page180.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3298" 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 + =
减小字号Ctrl + -
显示快捷键?