page88.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 157 行 · 第 1/2 页
HTML
157 行
<HTML>
<HEAD>
<TITLE>Singly-Linked Lists</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html2987" HREF="page89.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page89.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2985" HREF="page79.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page79.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2979" HREF="page87.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page87.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2989" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2990" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION005200000000000000000">Singly-Linked Lists</A></H1>
<A NAME="secfdslinklist"> </A>
<P>
The singly-linked list is the most basic of
all the pointer-based data structures.
A singly-linked list is simply a sequence of dynamically allocated
storage elements,
each containing a pointer to its successor.
Despite this obvious simplicity,
there are myriad implementation variations.
Figure <A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows several of the most common
singly-linked list variants.
<P>
<P><A NAME="3065"> </A><A NAME="figlinklist1"> </A> <IMG WIDTH=575 HEIGHT=362 ALIGN=BOTTOM ALT="figure2829" SRC="img611.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img611.gif" ><BR>
<STRONG>Figure:</STRONG> Singly-Linked List Variations<BR>
<P>
<P>
The basic singly-linked list is shown in Figure <A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (a).
Each element of the list contains a pointer to its successor;
the last element contains a null pointer.
A pointer to the first element of the list,
labeled <tt>head</tt><A NAME=3070> </A> in Figure <A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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 when
we 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=3073> </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="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (b) shows
a way in which to make adding elements to the tail of a list more efficient.
The solution is to keep a second pointer, <tt>tail</tt><A NAME=3076> </A>,
which points to the last element of the list.
Of course, this time efficiency comes at the cost of the additional space
used to store the <tt>tail</tt> pointer.
<P>
The singly-linked lists labeled (c) and (d)
in Figure <A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrate two common programming tricks.
The list (c) has an extra element at the head of the list
called a <em>sentinel</em><A NAME=3080> </A>.
This element is never used to hold data
and it is always present.
The principal advantage of using a sentinel is that
it simplifies the programming of certain operations.
E.g., since there is always a sentinel standing guard,
we never need to modify the <tt>head</tt> pointer.
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=3083> </A>.
Instead of using a null pointer to demarcate the end of the list,
the pointer in the last element points to the sentinel.
The advantage of this programming trick is that
insertion at the head of the list,
insertion at the tail of the list,
and insertion at an arbitrary position of the list
are all identical operations.
<P>
Figure <A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (d) shows a variation of a singly-linked
list using a sentinel in which
instead of keeping a pointer to the sentinel,
the sentinel itself serves as the handle for the list.
This variant eliminates the need to allocate storage
for the sentinel separately.
<P>
Of course, it is also possible to make a circular, singly-linked list
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?