page97.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 122 行
HTML
122 行
<HTML><HEAD><TITLE>Singly-Linked Lists</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="tex2html2324" HREF="page98.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2322" HREF="page81.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2316" HREF="page96.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2326" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION004300000000000000000">Singly-Linked Lists</A></H1><A NAME="secfdslinklist"> </A><P>The singly-linked list is the most basic ofall the linked data structures.A singly-linked list is simply a sequence of objects,each of which refers to its successor in the list.Despite this obvious simplicity,there are myriad implementation variations.Figure <A HREF="page97.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows several of the most commonsingly-linked list variants.<P><P><A NAME="3441"> </A><A NAME="figlinklist1"> </A> <IMG WIDTH=575 HEIGHT=293 ALIGN=BOTTOM ALT="figure3265" SRC="img624.gif" ><BR><STRONG>Figure:</STRONG> Singly-linked list variations.<BR><P><P>The basic singly-linked list is shown in Figure <A HREF="page97.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).Each element of the list refers to its successor andthe last element refers to <tt>None</tt>.One variable,labeled <tt>head</tt><A NAME=3447> </A> in Figure <A HREF="page97.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a),is used to keep track of the list.<P>The basic singly-linked list is inefficient in those cases whenwe wish to add elements to both ends of the list.While it is easy to add elements at the head of the list,to add elements at the other end (the <em>tail</em><A NAME=3450> </A>)we need to locate the last element.If the basic basic singly-linked list is used,the entire list needs to be traversed in order to find its tail.<P>Figure <A HREF="page97.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b) showsa way in which to make adding elements to the tail of a list more efficient.The solution uses a second variable, <tt>tail</tt><A NAME=3453> </A>,which refers to the last element of the list.Of course, this time efficiency comes at the cost of the additional spaceused to store the variable <tt>tail</tt>.<P>The singly-linked list labeled (c)in Figure <A HREF="page97.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates two common programming tricks.There is an extra element at the head of the listcalled a <em>sentinel</em><A NAME=3457> </A>.This element is never used to hold dataand it is always present.The principal advantage of using a sentinel is thatit simplifies the programming of certain operations.For example, since there is always a sentinel standing guard,we never need to modify the <tt>head</tt> variable.Of course, the disadvantage of a sentinel such as that shown in (c)is that extra space is required,and the sentinel needs to be created when the list is initialized.<P>The list (c) is also a <em>circular list</em><A NAME=3460> </A>.Instead of using a reference <tt>None</tt> to demarcate the end of the list,the last element of the list refers to the sentinel.The advantage of this programming trick is thatinsertion at the head of the list,insertion at the tail of the list,and insertion at an arbitrary position of the listare all identical operations.<P>Of course, it is also possible to make a circular, singly-linked listthat does not use a sentinel.Figure <A HREF="page97.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (d) shows a variation in whicha single variable is used to keep track of the list,but this time the variable, <tt>tail</tt>,refers to the last element of the list.Since the list is circular in this case,the first element follows the last element of the list.Therefore, it is relatively simple to insert bothat the head and at the tail of this list.This variation minimizes the storage required,at the expense of a little extra time for certain operations.<P>Figure <A HREF="page97.html#figlinklist2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates how the empty list(i.e., the list containing no list elements)is represented for each of the variations given in Figure <A HREF="page97.html#figlinklist2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Notice that the sentinel is always presentin list variant (c).On the other hand,in the list variants which do not use a sentinel,a reference to <tt>None</tt> is used to indicate the empty list.<P><P><A NAME="3583"> </A><A NAME="figlinklist2"> </A> <IMG WIDTH=575 HEIGHT=276 ALIGN=BOTTOM ALT="figure3467" SRC="img625.gif" ><BR><STRONG>Figure:</STRONG> Empty singly-linked lists.<BR><P><P>In the following sections,we will present the implementation details of a generic singly-linked list.We have chosen to present variation (b)--the one which uses a head and a tail--since is supports append and prepend operations efficiently.<P><BR> <HR><UL> <LI> <A NAME="tex2html2327" HREF="page98.html#SECTION004310000000000000000">An Implementation</A><LI> <A NAME="tex2html2328" HREF="page99.html#SECTION004320000000000000000">List Elements</A><LI> <A NAME="tex2html2329" HREF="page100.html#SECTION004330000000000000000"><tt>LinkedList</tt> Class <tt>__init__</tt> Method</A><LI> <A NAME="tex2html2330" HREF="page101.html#SECTION004340000000000000000"><tt>purge</tt> Method</A><LI> <A NAME="tex2html2331" HREF="page102.html#SECTION004350000000000000000"><tt>LinkedList</tt> Properties</A><LI> <A NAME="tex2html2332" HREF="page103.html#SECTION004360000000000000000"><tt>first</tt> and <tt>last</tt> Properties</A><LI> <A NAME="tex2html2333" HREF="page104.html#SECTION004370000000000000000"><tt>prepend</tt> Method</A><LI> <A NAME="tex2html2334" HREF="page105.html#SECTION004380000000000000000"><tt>append</tt> Method</A><LI> <A NAME="tex2html2335" HREF="page106.html#SECTION004390000000000000000"><tt>__copy__</tt> Method</A><LI> <A NAME="tex2html2336" HREF="page107.html#SECTION0043100000000000000000"><tt>extract</tt> Method</A><LI> <A NAME="tex2html2337" HREF="page108.html#SECTION0043110000000000000000"><tt>insertAfter</tt> and <tt>insertBefore</tt> Methods</A></UL><HR><A NAME="tex2html2324" HREF="page98.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2322" HREF="page81.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2316" HREF="page96.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2326" 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 + -
显示快捷键?