page165.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 84 行
HTML
84 行
<HTML><HEAD><TITLE>Doubly-Linked and Circular 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="tex2html3100" HREF="page166.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3098" HREF="page158.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3094" HREF="page164.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3102" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION006330000000000000000">Doubly-Linked and Circular Lists</A></H2><P>In the preceding section we saw that the running time of<tt>dequeueHead</tt> is <I>O</I>(1),but that the running time of <tt>dequeueTail</tt> is <I>O</I>(<I>n</I>),for the linked-list implementation of a deque.This is because the linked list data structure used,<tt>LinkedList</tt>, is a <em>singly-linked list</em><A NAME=7876> </A>.Each element in a singly-linked list contains a single reference--a reference to the successor (next) element of the list.As a result, deleting the head of the linked list is easy:The new head is the successor of the old head.<P>However, deleting the tail of a linked list is not so easy:The new tail is the predecessor of the original tail.Since there is no reference from the original tail to its predecessor,the predecessor must be found by traversing the linked list from the head.This traversal gives rise to the <I>O</I>(<I>n</I>) running time.<P>In a <em>doubly-linked list</em><A NAME=7878> </A>,each list element contains two references--one to its successor and one to its predecessor.There are many different variations of doubly-linked lists:Figure <A HREF="page165.html#figdeque2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates three of them.<P><P><A NAME="8176"> </A><A NAME="figdeque2"> </A> <IMG WIDTH=575 HEIGHT=403 ALIGN=BOTTOM ALT="figure7880" SRC="img707.gif" ><BR><STRONG>Figure:</STRONG> Doubly-linked and circular list variations.<BR><P><P>Figure <A HREF="page165.html#figdeque2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a) shows the simplest case:Two variables, say <em>_head</em> and <em>_tail</em>,are used to keep track of the list elements.One of them refers to the first element of the list,the other refers to the last.The first element of the list has no predecessor,therefore that reference is null.Similarly, the last element has no successorand the corresponding reference is also null.In effect, we have two overlapping singly-linked listswhich go in opposite directions.Figure <A HREF="page165.html#figdeque2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> also shows the representation of an empty list.In this case the head and tail variables are both null.<P>A <em>circular, doubly-linked list</em><A NAME=8184> </A> is shown inFigure <A HREF="page165.html#figdeque2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b).A circular list is formed by makinguse of variables which would otherwise be null:The last element of the list is made the predecessor of the first element;the first element, the successor of the last.The upshot is that we no longer need both a head and tail variable tokeep track of the list.Even if only a single variable is used,both the first and the last list elements can be found in constant time.<P>Finally, Figure <A HREF="page165.html#figdeque2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c) shows a circular,doubly-linked list which has a single sentinel.This variation is similar to the preceding one in thatboth the first and the last list elements can be found in constant time.This variation has the advantage that no special cases arerequired when dealing with an empty list.Figure <A HREF="page165.html#figdeque2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows that the empty list is represented by a listwith exactly one element--the sentinel.In the case of the empty list,the sentinel is both is own successor and predecessor.Since the sentinel is always present,and since it always has both a successor and a predecessor,the code for adding elements to the empty listis identical to that for adding elements to a non-empty list.<P><HR><A NAME="tex2html3100" HREF="page166.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3098" HREF="page158.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3094" HREF="page164.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3102" 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 + -
显示快捷键?