⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 6list.html

📁 Visual C++ has been one of most effective tool for the large industrial applications. This book is t
💻 HTML
字号:
🔍 
<html>
<head>
	<title>Linked Lists</title>
    <meta  name="description" content="Linked list in C++">
    <meta name="keywords" content="link, list, dynamic, new, delete">
	<link rel="stylesheet" href="rs.css" tppabs="http://www.relisoft.com/book/rs.css">
</head>

<body background="margin.gif" tppabs="http://www.relisoft.com/book/images/margin.gif" bgcolor="#FFFFDC">

<!-- Main Table -->
<table cellpadding="6">
    <tr>
    <td width="78">
	&nbsp;
    <td>
<h4>Linked List</h4>
<p>A linked list is a dynamic data structure with fast prepending and appending and linear searching. A list consists of links. Suppose that we want to store integer id抯 in a linked list. A <var>Link</var> will contain a field for an id and a pointer to the next link. To see how it works in practice, let抯 look at the picture.

<p><img src="Image5-2.gif" tppabs="http://www.relisoft.com/book/lang/pointer/images/Image5.gif" width=300 height=90 alt=" ">

<p class=caption>Figure 5. A linked list storing numbers 6, 2 and 1.</p>

<p>The last link in the list has a null (zero) pointer <var>_pNext</var>. That抯 the list terminator. A null pointer is never a valid pointer, that is, it cannot be dereferenced. It can however be checked against zero.

<tr>
<td class=margin valign=top>

<br>
<a href="javascript:if(confirm('http://www.relisoft.com/book/lang/pointer/source/list.zip  \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval.  \n\nDo you want to open it from the server?'))window.location='http://www.relisoft.com/book/lang/pointer/source/list.zip'" tppabs="http://www.relisoft.com/book/lang/pointer/source/list.zip">
<img src="brace.gif" tppabs="http://www.relisoft.com/book/images/brace.gif" width=16 height=16 border=1 alt="Download!"><br>source</a>
<td>

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>class Link
{
public:
    Link (Link* pNext, int id) 
        : _pNext (pNext), _id (id) {}
    Link *  Next () const { return _pNext; }
    int     Id () const { return _id; }
private:
    int     _id;
    Link *  _pNext;
};</pre>
</table><!-- End Code -->

<p>Notice how the definition of <var>Link</var> is self-referencing--a <var>Link</var> contains a pointer to a <var>Link</var>. It's okay to use <i>pointers</i> and <i>references</i> to types whose definitions haven抰 been seen by the compiler, yet. The only thing needed by the compiler in such a case is the <i>declaration</i> of the type. In our case the line

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>class Link</pre>
</table><!-- End Code -->

serves as such a declaration.
<p>A linked <b><i>List</i></b> stores a pointer to the first link. Conceptually, a list is a different object than the link. To begin with, it has a different interface. One can add new items to the list, one can remove them. One can iterate the list, etc. These operations make no sense as methods of <var>Link</var>. Yet, in some sense, every link is a beginning of a list. This recursive way of looking at things is very popular in languages like Lisp. We usually try to avoid such recursive concepts in object oriented programming. So for us a <var>List</var> is a different creature than a <var>Link</var>.
<p>Starting from the first link pointed to by <var>_pHead</var>, we can traverse the whole list following the pointers <var>_pNext</var>.

<p>In the beginning, the list is empty and the pointer <var>_pHead</var> is initialized to zero.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>class List
{
public:
    List (): _pHead (0) {}
    ~List ();
    void Add ( int id );
    Link const * GetHead () const { return _pHead; }
private:
    Link* _pHead;
};</pre>
</table><!-- End Code -->

<p>The list has a destructor in which it deallocates all the links. The list <b><i>owns</i></b> the links.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>List::~List ()
{
    // free the list
    while ( _pHead != 0 )
    {
        Link* pLink = _pHead;
        _pHead = _pHead-&gt;Next(); // unlink pLink
        delete pLink;
    }
}</pre>
</table><!-- End Code -->



<p>The algorithm for deallocating a list works as follows: As long as there is something in the list, we point a temporary pointer, <var>pLink</var>, at the first link; point the <var>_pHead</var> at the next link (could be null), which is equivalent to unlinking the first link; and delete this link. The statement

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>_pHead = _pHead-&gt;Next ();
</pre></table><!-- End Code -->

is a pointer assignment. <var>_pHead</var> will now point at the same link that is pointed at by 
<var>_pHead-&gt;_pNext</var>

<p> Again, this is something we wouldn抰 be able to do with references.

<p><img src="Image6-2.gif" tppabs="http://www.relisoft.com/book/lang/pointer/images/Image6.gif" width=354 height=270 alt=" ">

<p class=caption>Figure 6. The unlinking and deleting of the first element of the list.</p>

<p>There is a simpler, recursive, implementation of the linked list destructor:

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>List::~List ()
{
    delete _pHead;
}
    
Link::~Link ()
{
    delete _pNext;
}</pre>
</table><!-- End Code -->

<p>The recursion stops automatically as soon as it reaches the terminating null pointer.

<p>Simplicity is the obvious advantage of the recursive solution. The price you pay for this simplicity is speed and memory usage. Recursive function calls are more expensive than looping. They also consume the program's stack space. If stack is at premium (e.g., when you抮e writing the kernel of an operating system), recursion is out of the question. But even if you have plenty of stack, you might still be better off using the iterative solution for really large linked lists. On the other hand, because of memory thrashing, really large linked lists are a bad idea in itself (we抣l talk about it later). In any case, whichever way you go, it's good to know your tradeoffs.

<p>Adding a new id to the list is done by allocating a new link and initializing it with the id and the pointer to the next item. The next item is the link that was previously at the beginning of the list. (It was pointed to by <var>_pHead</var>.) The new link becomes the head of the list and <var>_pHead</var> is pointed to it (pointer assignment). This process is called prepending.

<p><img src="Image7-1.gif" tppabs="http://www.relisoft.com/book/lang/pointer/images/Image7.gif" width=366 height=264 alt=" ">
<p class=caption>Figure 7. Prepending a new element in front of the list.</p>
<p>
<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>void List::Add ( int id )
{
    // add in front of the list
    Link * pLink = new Link (_pHead, id);
    _pHead = pLink;
}</pre>
</table><!-- End Code -->

<p>Since the list grows dynamically, every new <var>Link</var> has to be allocated using operator new. When a <b><i>new object</i></b> is allocated, its constructor is automatically called. This is why we are passing the constructor arguments in <var>new</var> <var>Link (_pHead, id)</var>.
<p>List iteration is simple enough. For instance, here抯 how we may do a search for a link containing a given id

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>for (Link const * pLink = list.GetHead();
     pLink != 0; 
     pLink = pLink-&gt;Next ())
{
    if (pLink-&gt;Id() == id)
        break;
}</pre>
</table><!-- End Code -->

<p>Notice the use of pointers to <var>const</var>. The method <var>GetHead</var> is declared to return a pointer to a <var>const Link</var>. 

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Link const * GetHead () const;</pre>
</table><!-- End Code -->

<p>The variable we assign it to must therefore be a pointer to a <var>const</var> <var>Link</var>, too.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Link const * pLink = list.GetHead ();</pre>
</table><!-- End Code -->

<p>The meaning of a pointer to <var>const</var> is the same as the meaning of a reference to <var>const</var>--the object pointed to, or referred to, cannot be changed through such a pointer or reference. In the case of a pointer, however, we have to distinguish between a pointer to <var>const</var> and a <var>const</var> pointer. The latter is a pointer that, once initialized, cannot be pointed to anything else (just like a reference). The syntax for these two cases is

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Link const * pLink; // pointer to const
Link * const pLink = pInitPtr;  // const pointer</pre>
</table><!-- End Code -->

<p>Finally, the two can be combined to form a <var>const</var> pointer to <var>const</var>

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Link const * const pLink = pInitPtr; // const pointer to const</pre>
</table><!-- End Code -->

<p>This last pointer can only be used for read access to a single location to which it was initialized.
<p>There is some confusion in the naming of pointers and references when combined with <var>const</var>. Since there is only one possibility of <var>const</var>-ness for a reference, one often uses the terms reference to <var>const</var> and <var>const</var> reference interchangeably. Unfortunately, the two cases are often confused when applied to pointers. In this book <var>const</var> pointer will always mean a pointer that cannot be moved, and pointer to <var>const</var>, a pointer through which one cannot write.
<p>But wait, there抯 even more to confuse you! There is an equivalent syntax for a pointer to <var>const</var>


<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre><b>const</b><!-- Code --> Link * pLink; // pointer to const</pre>
</table><!-- End Code -->

and, of course,

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre><b>const</b><!-- Code --> Link * const pLink = pInitPtr; // const pointer to const</pre>
</table><!-- End Code -->

<p>The source of all this confusion is our insistence on reading text from left to right (people in the Middle East will laugh at us). Since C was written for computers and not humans, the direction of reading didn抰 really matter. So, to this day, declaration are best read right to left.

<p>Let抯 play with reversing some of the declarations. Just remember that asterisk means &quot;pointer to a.&quot;

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Link const * pLink;</pre>
</table><!-- End Code -->

<p>becomes Figure 8.

<p><img src="Image8-1.gif" tppabs="http://www.relisoft.com/book/lang/pointer/images/Image8.gif" width=306 height=138 alt=" ">

<p class=caption>Figure 8. Reading type declarations: <var>pLink</var> is a pointer to a constant <var>Link</var>.</p>

<p>Similarly

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Link * const pLink;</pre>
</table><!-- End Code -->

<p><img src="Image9-1.gif" tppabs="http://www.relisoft.com/book/lang/pointer/images/Image9.gif" width=306 height=138 alt=" ">

<p class=caption>Figure 9. Reading type declarations: <var>pLink</var> is a constant pointer to a <var>Link</var>.</p>

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Link const * const pLink = pInitPtr;</pre>
</table><!-- End Code -->

<p><img src="Image10.gif" tppabs="http://www.relisoft.com/book/lang/pointer/images/Image10.gif" width=360 height=138 alt=" ">

<p class=caption>Figure 10. Reading type declarations: <var>pLink</var> is a constant pointer to a constant <var>Link</var>.</p>


</table>
<!-- End Main Table -->
</body>
</html>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -