HTML code for sharing source code

HTML Copy To Clipboarddone!

<div class="highlight" style="background: #f8f8f8"><pre style="line-height: 125%"><div id="lc1"><span style="color: #BC7A00">#include &lt;cstdio&gt;</span>
</div><div id="lc2"><span style="color: #BC7A00">#include &lt;cassert&gt;</span>
</div><div id="lc3">
</div><div id="lc4">
</div><div id="lc5"><span style="color: #008000; font-weight: bold">using</span> <span style="color: #008000; font-weight: bold">namespace</span> std;
</div><div id="lc6">
</div><div id="lc7"><span style="color: #008000; font-weight: bold">typedef</span> <span style="color: #B00040">int</span> T;
</div><div id="lc8"><span style="color: #008000; font-weight: bold">const</span> <span style="color: #B00040">int</span> MAX<span style="color: #666666">=1000</span>;
</div><div id="lc9"><span style="color: #008000; font-weight: bold">const</span> <span style="color: #B00040">int</span> NONE<span style="color: #666666">=-1</span>;
</div><div id="lc10">
</div><div id="lc11"><span style="color: #008000; font-weight: bold">class</span> <span style="color: #0000FF; font-weight: bold">List</span>{
</div><div id="lc12">    <span style="color: #008000; font-weight: bold">struct</span> Item{
</div><div id="lc13">      <span style="color: #B00040">int</span> prev;
</div><div id="lc14">      <span style="color: #B00040">int</span> next;
</div><div id="lc15">      T value;
</div><div id="lc16">      
</div><div id="lc17">      
</div><div id="lc18">      Item(<span style="color: #B00040">int</span> a_prev, <span style="color: #B00040">int</span> a_next, T a_value){
</div><div id="lc19">        prev<span style="color: #666666">=</span>a_prev;
</div><div id="lc20">        next<span style="color: #666666">=</span>a_next;
</div><div id="lc21">        value<span style="color: #666666">=</span>a_value;
</div><div id="lc22">      }
</div><div id="lc23">      
</div><div id="lc24">      Item(T a_value){
</div><div id="lc25">        prev<span style="color: #666666">=</span>NONE;
</div><div id="lc26">        next<span style="color: #666666">=</span>NONE;
</div><div id="lc27">        value<span style="color: #666666">=</span>a_value;
</div><div id="lc28">      }
</div><div id="lc29">      
</div><div id="lc30">      Item(){
</div><div id="lc31">        prev<span style="color: #666666">=</span>NONE;
</div><div id="lc32">        next<span style="color: #666666">=</span>NONE;
</div><div id="lc33">        value<span style="color: #666666">=0</span>;
</div><div id="lc34">      }
</div><div id="lc35">      
</div><div id="lc36">    };
</div><div id="lc37">  
</div><div id="lc38">    Item<span style="color: #666666">*</span> items[MAX];
</div><div id="lc39">    <span style="color: #B00040">int</span> first;       <span style="color: #408080; font-style: italic">//индекс начального элемента</span>
</div><div id="lc40">    <span style="color: #B00040">int</span> last;        <span style="color: #408080; font-style: italic">//индекс конечного элемента</span>
</div><div id="lc41">    <span style="color: #B00040">int</span> num;         <span style="color: #408080; font-style: italic">//общее число элементов</span>
</div><div id="lc42">     
</div><div id="lc43">     
</div><div id="lc44">    <span style="color: #408080; font-style: italic">//ищем следующее свободное место в массиве</span>
</div><div id="lc45">    <span style="color: #B00040">int</span> get_free_index(){
</div><div id="lc46">      <span style="color: #B00040">int</span> i<span style="color: #666666">=0</span>;
</div><div id="lc47">      <span style="color: #008000; font-weight: bold">for</span>(i<span style="color: #666666">=0</span>;i<span style="color: #666666">&lt;</span>MAX;i<span style="color: #666666">++</span>){
</div><div id="lc48">       <span style="color: #008000; font-weight: bold">if</span>( items[i]<span style="color: #666666">-&gt;</span>prev<span style="color: #666666">==</span>NONE <span style="color: #666666">&amp;&amp;</span> items[i]<span style="color: #666666">-&gt;</span>next<span style="color: #666666">==</span>NONE ){      
</div><div id="lc49">            <span style="color: #008000; font-weight: bold">return</span> i<span style="color: #666666">+</span>(num<span style="color: #666666">==1</span>);
</div><div id="lc50">       }
</div><div id="lc51">      }
</div><div id="lc52">      
</div><div id="lc53">      <span style="color: #008000; font-weight: bold">return</span> NONE;
</div><div id="lc54">
</div><div id="lc55">    }
</div><div id="lc56">
</div><div id="lc57">    <span style="color: #408080; font-style: italic">//вставляем значение перед выбранным элементом массива</span>
</div><div id="lc58">    <span style="color: #B00040">void</span> insert_before(<span style="color: #B00040">int</span> i, T a_value){
</div><div id="lc59">      <span style="color: #B00040">int</span> free_index<span style="color: #666666">=</span>get_free_index();
</div><div id="lc60">      
</div><div id="lc61">      items[free_index]       <span style="color: #666666">=</span> <span style="color: #008000; font-weight: bold">new</span> Item(a_value);
</div><div id="lc62">      items[free_index]<span style="color: #666666">-&gt;</span>next <span style="color: #666666">=</span> i;
</div><div id="lc63">      items[free_index]<span style="color: #666666">-&gt;</span>prev <span style="color: #666666">=</span> items[i]<span style="color: #666666">-&gt;</span>prev;
</div><div id="lc64">      items[i]<span style="color: #666666">-&gt;</span>prev          <span style="color: #666666">=</span> free_index;
</div><div id="lc65">      
</div><div id="lc66">      <span style="color: #008000; font-weight: bold">if</span>(i <span style="color: #666666">==</span> first)
</div><div id="lc67">        first<span style="color: #666666">=</span>free_index;
</div><div id="lc68">      
</div><div id="lc69">      num<span style="color: #666666">++</span>;
</div><div id="lc70">      
</div><div id="lc71">    }
</div><div id="lc72">
</div><div id="lc73">
</div><div id="lc74">    <span style="color: #B00040">void</span> insert_after(<span style="color: #B00040">int</span> i, T a_value){
</div><div id="lc75">      <span style="color: #B00040">int</span> free_index<span style="color: #666666">=</span>get_free_index();
</div><div id="lc76">      
</div><div id="lc77">      items[free_index]       <span style="color: #666666">=</span> <span style="color: #008000; font-weight: bold">new</span> Item(a_value);
</div><div id="lc78">      items[free_index]<span style="color: #666666">-&gt;</span>prev <span style="color: #666666">=</span> i;
</div><div id="lc79">      
</div><div id="lc80">      items[free_index]<span style="color: #666666">-&gt;</span>next <span style="color: #666666">=</span> items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc81">      
</div><div id="lc82">      <span style="color: #008000; font-weight: bold">if</span>(items[i]<span style="color: #666666">-&gt;</span>next<span style="color: #666666">!=</span>NONE)
</div><div id="lc83">        items[items[i]<span style="color: #666666">-&gt;</span>next]<span style="color: #666666">-&gt;</span>prev<span style="color: #666666">=</span>free_index;
</div><div id="lc84">      
</div><div id="lc85">      
</div><div id="lc86">      items[i]<span style="color: #666666">-&gt;</span>next          <span style="color: #666666">=</span> free_index;
</div><div id="lc87">      
</div><div id="lc88">      <span style="color: #008000; font-weight: bold">if</span>(i <span style="color: #666666">==</span> last)
</div><div id="lc89">        last<span style="color: #666666">=</span>free_index;
</div><div id="lc90">      
</div><div id="lc91">      num<span style="color: #666666">++</span>;
</div><div id="lc92">      
</div><div id="lc93">    }
</div><div id="lc94">    
</div><div id="lc95">    
</div><div id="lc96">    <span style="color: #408080; font-style: italic">//ищем и возвращаем индекс элемента в массиве, чье значение равно аргументу</span>
</div><div id="lc97">    <span style="color: #B00040">int</span> findItem(T value){
</div><div id="lc98">      <span style="color: #008000; font-weight: bold">if</span>(isEmpty()) <span style="color: #008000; font-weight: bold">return</span> NONE;
</div><div id="lc99">      <span style="color: #408080; font-style: italic">//будем возвращать первый найденный индекс</span>
</div><div id="lc100">      
</div><div id="lc101">      <span style="color: #B00040">int</span> i <span style="color: #666666">=</span> first;
</div><div id="lc102">      
</div><div id="lc103">      <span style="color: #008000; font-weight: bold">while</span>(items[i]<span style="color: #666666">-&gt;</span>next <span style="color: #666666">!=</span> NONE <span style="color: #666666">&amp;&amp;</span> items[i]<span style="color: #666666">-&gt;</span>value <span style="color: #666666">!=</span> value){
</div><div id="lc104">        i<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc105">      }
</div><div id="lc106">      
</div><div id="lc107">      <span style="color: #008000; font-weight: bold">if</span>(items[i]<span style="color: #666666">-&gt;</span>value <span style="color: #666666">==</span> value)
</div><div id="lc108">        <span style="color: #008000; font-weight: bold">return</span> i;
</div><div id="lc109">
</div><div id="lc110">      <span style="color: #008000; font-weight: bold">return</span> NONE;
</div><div id="lc111">    }
</div><div id="lc112">
</div><div id="lc113">    <span style="color: #408080; font-style: italic">//получить индекс на элемент по номеру его в списке</span>
</div><div id="lc114">    <span style="color: #B00040">int</span> getItem(<span style="color: #B00040">unsigned</span> <span style="color: #B00040">int</span> index){
</div><div id="lc115">      <span style="color: #008000; font-weight: bold">if</span>(isEmpty())      <span style="color: #008000; font-weight: bold">return</span> NONE;
</div><div id="lc116">      <span style="color: #008000; font-weight: bold">if</span>(index<span style="color: #666666">==0</span>)       <span style="color: #008000; font-weight: bold">return</span> first;
</div><div id="lc117">      <span style="color: #008000; font-weight: bold">if</span>(index<span style="color: #666666">==</span>(num<span style="color: #666666">-1</span>)) <span style="color: #008000; font-weight: bold">return</span> last;
</div><div id="lc118">      <span style="color: #008000; font-weight: bold">if</span>(index<span style="color: #666666">&gt;=</span>num)     <span style="color: #008000; font-weight: bold">return</span> NONE; 
</div><div id="lc119">      
</div><div id="lc120">      <span style="color: #B00040">int</span> i;
</div><div id="lc121">
</div><div id="lc122">      <span style="color: #408080; font-style: italic">//определяем с какого конца легче двигатся</span>
</div><div id="lc123">      <span style="color: #008000; font-weight: bold">if</span>(index<span style="color: #666666">&gt;=</span>num<span style="color: #666666">/2</span>){
</div><div id="lc124">        i<span style="color: #666666">=</span>last;
</div><div id="lc125">        index<span style="color: #666666">=</span>num<span style="color: #666666">-</span>index<span style="color: #666666">-1</span>;
</div><div id="lc126">        <span style="color: #008000; font-weight: bold">while</span>(index){
</div><div id="lc127">          i<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>prev;
</div><div id="lc128">          index<span style="color: #666666">--</span>;
</div><div id="lc129">        }
</div><div id="lc130">      }
</div><div id="lc131">      <span style="color: #008000; font-weight: bold">else</span>{
</div><div id="lc132">        i<span style="color: #666666">=</span>first;
</div><div id="lc133">        <span style="color: #008000; font-weight: bold">while</span>(index){
</div><div id="lc134">          i<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc135">          index<span style="color: #666666">--</span>;
</div><div id="lc136">        }
</div><div id="lc137">      }
</div><div id="lc138">      
</div><div id="lc139">      <span style="color: #008000; font-weight: bold">return</span> i;
</div><div id="lc140">    }
</div><div id="lc141">
</div><div id="lc142">    <span style="color: #408080; font-style: italic">//удаляем элемент по его номеру в массиве</span>
</div><div id="lc143">    <span style="color: #B00040">void</span> removeItem(<span style="color: #B00040">int</span> i){
</div><div id="lc144">      <span style="color: #008000; font-weight: bold">if</span>(isEmpty()) <span style="color: #008000; font-weight: bold">return</span>;
</div><div id="lc145">      
</div><div id="lc146">      <span style="color: #008000; font-weight: bold">if</span>(items[i]<span style="color: #666666">-&gt;</span>prev <span style="color: #666666">!=</span> NONE)
</div><div id="lc147">        items[items[i]<span style="color: #666666">-&gt;</span>prev]<span style="color: #666666">-&gt;</span>next<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc148">        
</div><div id="lc149">      <span style="color: #008000; font-weight: bold">if</span>(items[i]<span style="color: #666666">-&gt;</span>next <span style="color: #666666">!=</span> NONE)
</div><div id="lc150">        items[items[i]<span style="color: #666666">-&gt;</span>next]<span style="color: #666666">-&gt;</span>prev<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>prev;
</div><div id="lc151">
</div><div id="lc152">
</div><div id="lc153">      num<span style="color: #666666">--</span>;
</div><div id="lc154">      
</div><div id="lc155">      <span style="color: #008000; font-weight: bold">if</span>(i <span style="color: #666666">==</span> first){
</div><div id="lc156">          first<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc157">      }    
</div><div id="lc158">      
</div><div id="lc159">
</div><div id="lc160">      <span style="color: #008000; font-weight: bold">if</span>(i <span style="color: #666666">==</span> last){
</div><div id="lc161">          last<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>prev;        
</div><div id="lc162">      }
</div><div id="lc163">      
</div><div id="lc164">      items[i]<span style="color: #666666">-&gt;</span>prev<span style="color: #666666">=</span>NONE;
</div><div id="lc165">      items[i]<span style="color: #666666">-&gt;</span>next<span style="color: #666666">=</span>NONE;
</div><div id="lc166">      
</div><div id="lc167">      
</div><div id="lc168">      <span style="color: #008000; font-weight: bold">if</span>(<span style="color: #666666">!</span>num){
</div><div id="lc169">        first<span style="color: #666666">=0</span>;
</div><div id="lc170">        last<span style="color: #666666">=0</span>;
</div><div id="lc171">      }
</div><div id="lc172">      
</div><div id="lc173">
</div><div id="lc174">    }
</div><div id="lc175">
</div><div id="lc176">    <span style="color: #008000; font-weight: bold">public</span><span style="color: #666666">:</span>
</div><div id="lc177">    List (){
</div><div id="lc178">      num<span style="color: #666666">=0</span>;
</div><div id="lc179">      first<span style="color: #666666">=0</span>;
</div><div id="lc180">      last<span style="color: #666666">=0</span>;
</div><div id="lc181">      <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> i<span style="color: #666666">=0</span>;i<span style="color: #666666">&lt;</span>MAX;i<span style="color: #666666">++</span>){
</div><div id="lc182">        items[i]<span style="color: #666666">=</span><span style="color: #008000; font-weight: bold">new</span> Item;
</div><div id="lc183">      }
</div><div id="lc184">      
</div><div id="lc185">    }
</div><div id="lc186">    
</div><div id="lc187">    <span style="color: #666666">~</span>List (){
</div><div id="lc188">      
</div><div id="lc189">    }
</div><div id="lc190">    
</div><div id="lc191">    <span style="color: #408080; font-style: italic">// добавить в конец</span>
</div><div id="lc192">    <span style="color: #B00040">void</span> add(T value){
</div><div id="lc193">      <span style="color: #B00040">int</span> free_index<span style="color: #666666">=</span>get_free_index();
</div><div id="lc194">      items[free_index] <span style="color: #666666">=</span> <span style="color: #008000; font-weight: bold">new</span> Item(value);
</div><div id="lc195">      <span style="color: #008000; font-weight: bold">if</span>(<span style="color: #666666">!</span>num){
</div><div id="lc196">        first <span style="color: #666666">=</span> free_index;
</div><div id="lc197">        last  <span style="color: #666666">=</span> free_index;
</div><div id="lc198">      }
</div><div id="lc199">      <span style="color: #008000; font-weight: bold">else</span>{
</div><div id="lc200">        items[free_index]<span style="color: #666666">-&gt;</span>prev <span style="color: #666666">=</span> last;
</div><div id="lc201">        items[last]      <span style="color: #666666">-&gt;</span>next <span style="color: #666666">=</span> free_index;
</div><div id="lc202">        last                    <span style="color: #666666">=</span> free_index;
</div><div id="lc203">      }
</div><div id="lc204">      num<span style="color: #666666">++</span>;
</div><div id="lc205">    }
</div><div id="lc206">    
</div><div id="lc207">    <span style="color: #408080; font-style: italic">// добавить элемент в позицию с указанным индексом</span>
</div><div id="lc208">    <span style="color: #B00040">void</span> insert(<span style="color: #B00040">unsigned</span> <span style="color: #B00040">int</span> index, T a_value){
</div><div id="lc209">      <span style="color: #408080; font-style: italic">//будем добавлять перед этим эл-том</span>
</div><div id="lc210">      <span style="color: #408080; font-style: italic">//cначало досчитаем до этого элемента</span>
</div><div id="lc211">      
</div><div id="lc212">      <span style="color: #008000; font-weight: bold">if</span>(<span style="color: #666666">!</span>index)
</div><div id="lc213">        <span style="color: #008000; font-weight: bold">return</span> insert_before(first, a_value);
</div><div id="lc214">        
</div><div id="lc215">      <span style="color: #408080; font-style: italic">//если индекс превышает число эл-тов то добавляем в конец</span>
</div><div id="lc216">      <span style="color: #008000; font-weight: bold">if</span>(index<span style="color: #666666">&gt;</span>num)
</div><div id="lc217">        <span style="color: #008000; font-weight: bold">return</span> add(a_value);
</div><div id="lc218">      
</div><div id="lc219">      <span style="color: #B00040">int</span> i;
</div><div id="lc220">      
</div><div id="lc221">     
</div><div id="lc222">      <span style="color: #408080; font-style: italic">//определяем с какого конца легче двигатся</span>
</div><div id="lc223">      <span style="color: #008000; font-weight: bold">if</span>(index<span style="color: #666666">&gt;=</span>num<span style="color: #666666">/2</span>){
</div><div id="lc224">        i<span style="color: #666666">=</span>last;
</div><div id="lc225">        index<span style="color: #666666">=</span>num<span style="color: #666666">-</span>index;
</div><div id="lc226">        <span style="color: #008000; font-weight: bold">while</span>(index){
</div><div id="lc227">          i<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>prev;
</div><div id="lc228">          index<span style="color: #666666">--</span>;
</div><div id="lc229">        }
</div><div id="lc230">      }
</div><div id="lc231">      <span style="color: #008000; font-weight: bold">else</span>{
</div><div id="lc232">        i<span style="color: #666666">=</span>first;
</div><div id="lc233">        <span style="color: #008000; font-weight: bold">while</span>(index){
</div><div id="lc234">          i<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc235">          index<span style="color: #666666">--</span>;
</div><div id="lc236">        }
</div><div id="lc237">      }
</div><div id="lc238">      printf(<span style="color: #BA2121">&quot;found %i</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">&quot;</span>,i);
</div><div id="lc239">      <span style="color: #008000; font-weight: bold">return</span> insert_after(i,a_value);
</div><div id="lc240">    }
</div><div id="lc241">    
</div><div id="lc242">    <span style="color: #408080; font-style: italic">// установить значение по индексу </span>
</div><div id="lc243">    <span style="color: #B00040">void</span> set(<span style="color: #B00040">int</span> index, T value){
</div><div id="lc244">      <span style="color: #B00040">int</span> i <span style="color: #666666">=</span> getItem(index);
</div><div id="lc245">      items[i]<span style="color: #666666">-&gt;</span>value<span style="color: #666666">=</span>value;
</div><div id="lc246">    };
</div><div id="lc247">    
</div><div id="lc248">    
</div><div id="lc249">    
</div><div id="lc250">    <span style="color: #408080; font-style: italic">// получить значение по индексу</span>
</div><div id="lc251">    T get(<span style="color: #B00040">int</span> index){
</div><div id="lc252">      <span style="color: #B00040">int</span> i<span style="color: #666666">=</span>getItem(index);
</div><div id="lc253">      <span style="color: #008000; font-weight: bold">if</span>(i<span style="color: #666666">!=</span>NONE)
</div><div id="lc254">        <span style="color: #008000; font-weight: bold">return</span> items[i]<span style="color: #666666">-&gt;</span>value;
</div><div id="lc255">      <span style="color: #008000; font-weight: bold">return</span> NONE;
</div><div id="lc256">    }
</div><div id="lc257">    
</div><div id="lc258">    <span style="color: #408080; font-style: italic">// очистить список </span>
</div><div id="lc259">    <span style="color: #B00040">void</span> clear (){
</div><div id="lc260">      num<span style="color: #666666">=0</span>;
</div><div id="lc261">      first<span style="color: #666666">=0</span>;
</div><div id="lc262">      last<span style="color: #666666">=0</span>;
</div><div id="lc263">      <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> i<span style="color: #666666">=0</span>;i<span style="color: #666666">&lt;</span>MAX;i<span style="color: #666666">++</span>){
</div><div id="lc264">        items[i]<span style="color: #666666">=</span><span style="color: #008000; font-weight: bold">new</span> Item;
</div><div id="lc265">      }
</div><div id="lc266">    }
</div><div id="lc267">    
</div><div id="lc268">    <span style="color: #408080; font-style: italic">// получить количество </span>
</div><div id="lc269">    <span style="color: #B00040">int</span> count(){
</div><div id="lc270">      <span style="color: #008000; font-weight: bold">return</span> num;
</div><div id="lc271">    }
</div><div id="lc272">    
</div><div id="lc273">    <span style="color: #408080; font-style: italic">// пустой ли список </span>
</div><div id="lc274">    <span style="color: #B00040">bool</span> isEmpty(){
</div><div id="lc275">      <span style="color: #008000; font-weight: bold">return</span> <span style="color: #666666">!</span>num;
</div><div id="lc276">    }
</div><div id="lc277">    
</div><div id="lc278">    <span style="color: #408080; font-style: italic">// получить индекс указаного элемента. Если: элемента нет, вернуть -1</span>
</div><div id="lc279">    <span style="color: #B00040">int</span> indexOf(T value){
</div><div id="lc280">      <span style="color: #408080; font-style: italic">//будем возвращать первый найденный индекс</span>
</div><div id="lc281">      
</div><div id="lc282">      <span style="color: #B00040">int</span> i<span style="color: #666666">=</span>first;
</div><div id="lc283">      <span style="color: #B00040">int</span> j<span style="color: #666666">=0</span>;
</div><div id="lc284">      <span style="color: #008000; font-weight: bold">while</span>(items[i]<span style="color: #666666">-&gt;</span>next <span style="color: #666666">!=</span> NONE <span style="color: #666666">&amp;&amp;</span> items[i]<span style="color: #666666">-&gt;</span>value <span style="color: #666666">!=</span> value){
</div><div id="lc285">        i<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc286">        j<span style="color: #666666">++</span>;
</div><div id="lc287">      }
</div><div id="lc288">      
</div><div id="lc289">      <span style="color: #008000; font-weight: bold">if</span>(items[i]<span style="color: #666666">-&gt;</span>value <span style="color: #666666">==</span> value)
</div><div id="lc290">        <span style="color: #008000; font-weight: bold">return</span> j;
</div><div id="lc291">
</div><div id="lc292">      
</div><div id="lc293">      <span style="color: #008000; font-weight: bold">return</span> NONE;
</div><div id="lc294">      
</div><div id="lc295">    }
</div><div id="lc296">    
</div><div id="lc297">    <span style="color: #408080; font-style: italic">// проверить, принадлежит ли элемент списку</span>
</div><div id="lc298">    <span style="color: #B00040">bool</span> contains(T value){
</div><div id="lc299">      <span style="color: #008000; font-weight: bold">return</span> (<span style="color: #B00040">bool</span>)(indexOf(value)<span style="color: #666666">+1</span>);
</div><div id="lc300">    }
</div><div id="lc301">    
</div><div id="lc302">    <span style="color: #408080; font-style: italic">// удалить все вхождения элемента из списка</span>
</div><div id="lc303">    <span style="color: #B00040">void</span> remove(T value){
</div><div id="lc304">      
</div><div id="lc305">      <span style="color: #008000; font-weight: bold">while</span>(<span style="color: #008000; font-weight: bold">true</span>){
</div><div id="lc306">        <span style="color: #B00040">int</span> i<span style="color: #666666">=</span>findItem(value);
</div><div id="lc307">        
</div><div id="lc308">        <span style="color: #008000; font-weight: bold">if</span>(i<span style="color: #666666">==</span>NONE)
</div><div id="lc309">          <span style="color: #008000; font-weight: bold">break</span>;
</div><div id="lc310">          
</div><div id="lc311">        removeItem(i);
</div><div id="lc312">      }
</div><div id="lc313">        
</div><div id="lc314">      
</div><div id="lc315">      
</div><div id="lc316">    }
</div><div id="lc317">    
</div><div id="lc318">    <span style="color: #408080; font-style: italic">// удалить элемент с заданным индексом</span>
</div><div id="lc319">    <span style="color: #B00040">void</span> removeAt(<span style="color: #B00040">int</span> index){
</div><div id="lc320">      <span style="color: #B00040">int</span> i<span style="color: #666666">=</span>getItem(index);
</div><div id="lc321">      <span style="color: #008000; font-weight: bold">if</span>(i<span style="color: #666666">!=</span>NONE)
</div><div id="lc322">        removeItem(i);
</div><div id="lc323">      
</div><div id="lc324">    }
</div><div id="lc325">    
</div><div id="lc326">    
</div><div id="lc327">    
</div><div id="lc328">    <span style="color: #B00040">void</span> print_all(){
</div><div id="lc329">      <span style="color: #B00040">int</span> i<span style="color: #666666">=</span>first;
</div><div id="lc330">      printf(<span style="color: #BA2121">&quot;</span><span style="color: #BB6622; font-weight: bold">\n\n</span><span style="color: #BA2121">  Count elements: %i </span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">&quot;</span>, num);
</div><div id="lc331">      printf(<span style="color: #BA2121">&quot;  First index: %i </span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">&quot;</span>,first);
</div><div id="lc332">      printf(<span style="color: #BA2121">&quot;  Last index: %i </span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">&quot;</span>,last);
</div><div id="lc333">      printf(<span style="color: #BA2121">&quot;  index  |  prev  |  next  |  value  |  arr_key  </span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">&quot;</span>);
</div><div id="lc334">      <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> j<span style="color: #666666">=0</span>;j<span style="color: #666666">&lt;</span>num;j<span style="color: #666666">++</span>){
</div><div id="lc335">        <span style="color: #408080; font-style: italic">//if(i==NONE) break;</span>
</div><div id="lc336">        printf(<span style="color: #BA2121">&quot;  %4i   |  %3i   |  %3i   |  %3i  |   %3i </span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">&quot;</span>,i,items[i]<span style="color: #666666">-&gt;</span>prev,items[i]<span style="color: #666666">-&gt;</span>next, items[i]<span style="color: #666666">-&gt;</span>value, i);
</div><div id="lc337">        i<span style="color: #666666">=</span>items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc338">      }
</div><div id="lc339">      
</div><div id="lc340">    }
</div><div id="lc341">    
</div><div id="lc342">    
</div><div id="lc343">
</div><div id="lc344">
</div><div id="lc345">    <span style="color: #408080; font-style: italic">// скопировать список в массив (предполагается, что массив содержит достаточное количество элементов для выполнения операции) </span>
</div><div id="lc346">    <span style="color: #B00040">void</span> copyTo(T<span style="color: #666666">*</span> arr){
</div><div id="lc347">      <span style="color: #B00040">int</span> i<span style="color: #666666">=</span>first;
</div><div id="lc348">      <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> j<span style="color: #666666">=0</span>;j<span style="color: #666666">&lt;</span>num;j<span style="color: #666666">++</span>){
</div><div id="lc349">        arr[j] <span style="color: #666666">=</span> items[i]<span style="color: #666666">-&gt;</span>value;
</div><div id="lc350">        i      <span style="color: #666666">=</span> items[i]<span style="color: #666666">-&gt;</span>next;
</div><div id="lc351">      }
</div><div id="lc352">    }
</div><div id="lc353">    
</div><div id="lc354">    <span style="color: #408080; font-style: italic">// получить итератор для обхода спискa</span>
</div><div id="lc355">    <span style="color: #408080; font-style: italic">//Iterator* getIterator(){</span>
</div><div id="lc356">      
</div><div id="lc357">    <span style="color: #408080; font-style: italic">//}</span>
</div><div id="lc358">
</div><div id="lc359">
</div><div id="lc360">};
</div><div id="lc361">
</div><div id="lc362"><span style="color: #B00040">void</span> test(){
</div><div id="lc363">    List<span style="color: #666666">*</span> list <span style="color: #666666">=</span> <span style="color: #008000; font-weight: bold">new</span> List();
</div><div id="lc364">    
</div><div id="lc365">    <span style="color: #408080; font-style: italic">/*тестирование на пустоту*/</span>
</div><div id="lc366">    assert(list<span style="color: #666666">-&gt;</span>isEmpty() ) ;
</div><div id="lc367">    assert(list<span style="color: #666666">-&gt;</span>count() <span style="color: #666666">==</span> <span style="color: #666666">0</span>);
</div><div id="lc368">
</div><div id="lc369">    <span style="color: #408080; font-style: italic">/*тестирование на дополнение в конец, изменение числа элементов, наличие элементов */</span>
</div><div id="lc370">    <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> i<span style="color: #666666">=0</span>;i<span style="color: #666666">&lt;10</span>;i<span style="color: #666666">++</span>){
</div><div id="lc371">      list<span style="color: #666666">-&gt;</span>add(i);
</div><div id="lc372">      assert(<span style="color: #666666">!</span>list<span style="color: #666666">-&gt;</span>isEmpty());
</div><div id="lc373">      assert(list<span style="color: #666666">-&gt;</span>get(i)<span style="color: #666666">==</span>i);
</div><div id="lc374">      assert(list<span style="color: #666666">-&gt;</span>count() <span style="color: #666666">==</span> i<span style="color: #666666">+1</span>);
</div><div id="lc375">      
</div><div id="lc376">      assert(list<span style="color: #666666">-&gt;</span>contains(i));
</div><div id="lc377">      assert(list<span style="color: #666666">-&gt;</span>indexOf(i)<span style="color: #666666">==</span>i);
</div><div id="lc378">      
</div><div id="lc379">      assert(<span style="color: #666666">!</span>list<span style="color: #666666">-&gt;</span>contains(i<span style="color: #666666">+1</span>));
</div><div id="lc380">      assert(list<span style="color: #666666">-&gt;</span>indexOf(i<span style="color: #666666">+1</span>)<span style="color: #666666">==</span>NONE);
</div><div id="lc381">    }
</div><div id="lc382">    
</div><div id="lc383">    
</div><div id="lc384">    <span style="color: #408080; font-style: italic">/*Тестирование удаления по значению*/</span>
</div><div id="lc385">    <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> i<span style="color: #666666">=0</span>;i<span style="color: #666666">&lt;10</span>;i<span style="color: #666666">+=2</span>){
</div><div id="lc386">      list<span style="color: #666666">-&gt;</span>remove(i);
</div><div id="lc387">      assert(list<span style="color: #666666">-&gt;</span>count() <span style="color: #666666">==</span> <span style="color: #666666">10-</span>i<span style="color: #666666">/2-1</span>);
</div><div id="lc388">      assert(<span style="color: #666666">!</span>list<span style="color: #666666">-&gt;</span>contains(i));
</div><div id="lc389">    }
</div><div id="lc390">
</div><div id="lc391">    <span style="color: #408080; font-style: italic">/*Тестирование удаления по номеру элемента в списке*/</span>    
</div><div id="lc392">    list<span style="color: #666666">-&gt;</span>removeAt(<span style="color: #666666">4</span>);
</div><div id="lc393">    list<span style="color: #666666">-&gt;</span>removeAt(<span style="color: #666666">3</span>);
</div><div id="lc394">    list<span style="color: #666666">-&gt;</span>removeAt(<span style="color: #666666">2</span>);
</div><div id="lc395">    list<span style="color: #666666">-&gt;</span>removeAt(<span style="color: #666666">1</span>);
</div><div id="lc396">    list<span style="color: #666666">-&gt;</span>removeAt(<span style="color: #666666">0</span>);
</div><div id="lc397">
</div><div id="lc398">    assert(list<span style="color: #666666">-&gt;</span>isEmpty()) ;
</div><div id="lc399">    assert(list<span style="color: #666666">-&gt;</span>count() <span style="color: #666666">==</span> <span style="color: #666666">0</span>);
</div><div id="lc400">
</div><div id="lc401">    <span style="color: #408080; font-style: italic">/*Тестирование вставки в начало*/</span>
</div><div id="lc402">    <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> i<span style="color: #666666">=1</span>;i<span style="color: #666666">&lt;10</span>;i<span style="color: #666666">++</span>){
</div><div id="lc403">      list<span style="color: #666666">-&gt;</span>insert(<span style="color: #666666">0</span>,i);
</div><div id="lc404">    }
</div><div id="lc405">    
</div><div id="lc406">    <span style="color: #408080; font-style: italic">/*Тестирование очистки*/</span>
</div><div id="lc407">    list<span style="color: #666666">-&gt;</span>clear();
</div><div id="lc408">    assert(list<span style="color: #666666">-&gt;</span>isEmpty() ) ;
</div><div id="lc409">    assert(list<span style="color: #666666">-&gt;</span>count() <span style="color: #666666">==</span> <span style="color: #666666">0</span>);
</div><div id="lc410">    
</div><div id="lc411">    <span style="color: #408080; font-style: italic">/*Тестирование удаления одинаковых элементов*/</span>
</div><div id="lc412">    <span style="color: #008000; font-weight: bold">for</span>(<span style="color: #B00040">int</span> i<span style="color: #666666">=0</span>;i<span style="color: #666666">&lt;100</span>;i<span style="color: #666666">++</span>)
</div><div id="lc413">      list<span style="color: #666666">-&gt;</span>add(<span style="color: #666666">486</span>);
</div><div id="lc414">    list<span style="color: #666666">-&gt;</span>remove(<span style="color: #666666">486</span>);
</div><div id="lc415">    assert(list<span style="color: #666666">-&gt;</span>isEmpty() ) ;
</div><div id="lc416">    assert(list<span style="color: #666666">-&gt;</span>count() <span style="color: #666666">==</span> <span style="color: #666666">0</span>);
</div><div id="lc417">
</div><div id="lc418"><span style="color: #408080; font-style: italic">/*Тестирование изменения*/</span>
</div><div id="lc419">    list<span style="color: #666666">-&gt;</span>add(<span style="color: #666666">1</span>);
</div><div id="lc420">    assert(list<span style="color: #666666">-&gt;</span>get(<span style="color: #666666">0</span>)<span style="color: #666666">==1</span>);
</div><div id="lc421">    list<span style="color: #666666">-&gt;</span>set(<span style="color: #666666">0</span>,<span style="color: #666666">31337</span>);
</div><div id="lc422">    assert(list<span style="color: #666666">-&gt;</span>get(<span style="color: #666666">0</span>)<span style="color: #666666">==31337</span>);
</div><div id="lc423">    
</div><div id="lc424">    list<span style="color: #666666">-&gt;</span>insert(<span style="color: #666666">0</span>,<span style="color: #666666">1</span>);
</div><div id="lc425">  list<span style="color: #666666">-&gt;</span>print_all();
</div><div id="lc426">
</div><div id="lc427">    list<span style="color: #666666">-&gt;</span>insert(<span style="color: #666666">1</span>,<span style="color: #666666">2</span>);
</div><div id="lc428">    list<span style="color: #666666">-&gt;</span>insert(<span style="color: #666666">1</span>,<span style="color: #666666">3</span>);
</div><div id="lc429">    list<span style="color: #666666">-&gt;</span>insert(<span style="color: #666666">1</span>,<span style="color: #666666">4</span>);
</div><div id="lc430">    list<span style="color: #666666">-&gt;</span>insert(<span style="color: #666666">1</span>,<span style="color: #666666">5</span>);
</div><div id="lc431">
</div><div id="lc432">    
</div><div id="lc433">  list<span style="color: #666666">-&gt;</span>print_all();
</div><div id="lc434">
</div><div id="lc435">
</div><div id="lc436">
</div><div id="lc437">    <span style="color: #408080; font-style: italic">//assert(list-&gt;contains(1));</span>
</div><div id="lc438">    <span style="color: #408080; font-style: italic">//assert(!list-&gt;contains(568));</span>
</div><div id="lc439">
</div><div id="lc440">}
</div><div id="lc441">
</div><div id="lc442">
</div><div id="lc443"><span style="color: #B00040">int</span> main(){
</div><div id="lc444">  test();
</div><div id="lc445">  <span style="color: #B00040">int</span> i;
</div><div id="lc446">  scanf(<span style="color: #BA2121">&quot;%i&quot;</span>,<span style="color: #666666">&amp;</span>i);
</div><div id="lc447">  <span style="color: #008000; font-weight: bold">return</span> <span style="color: #666666">0</span>;
</div><div id="lc448">}
</div></pre></div>
<p style="padding: 0; margin: 2em 0 1em 0; font-size: 0.8em; color: #666;"><span style="padding: 0 1em; background-color: #f5f5f5;"> Colored with <a style="color: #333" href="http://dumpz.org">dumpz.org</a></span></p>

BBCODE Copy To Clipboarddone!

[color=#BC7A00]#include <cstdio>
#include <cassert>
[/color]

[color=#008000][b]using[/b][/color] [color=#008000][b]namespace[/b][/color] std;

[color=#008000][b]typedef[/b][/color] [color=#B00040]int[/color] T;
[color=#008000][b]const[/b][/color] [color=#B00040]int[/color] MAX[color=#666666]=[/color][color=#666666]1000[/color];
[color=#008000][b]const[/b][/color] [color=#B00040]int[/color] NONE[color=#666666]=-[/color][color=#666666]1[/color];

[color=#008000][b]class[/b][/color] [color=#0000FF][b]List[/b][/color]{
    [color=#008000][b]struct[/b][/color] Item{
      [color=#B00040]int[/color] prev;
      [color=#B00040]int[/color] next;
      T value;
      
      
      Item([color=#B00040]int[/color] a_prev, [color=#B00040]int[/color] a_next, T a_value){
        prev[color=#666666]=[/color]a_prev;
        next[color=#666666]=[/color]a_next;
        value[color=#666666]=[/color]a_value;
      }
      
      Item(T a_value){
        prev[color=#666666]=[/color]NONE;
        next[color=#666666]=[/color]NONE;
        value[color=#666666]=[/color]a_value;
      }
      
      Item(){
        prev[color=#666666]=[/color]NONE;
        next[color=#666666]=[/color]NONE;
        value[color=#666666]=[/color][color=#666666]0[/color];
      }
      
    };
  
    Item[color=#666666]*[/color] items[MAX];
    [color=#B00040]int[/color] first;       [color=#408080][i]//индекс начального элемента
[/i][/color]    [color=#B00040]int[/color] last;        [color=#408080][i]//индекс конечного элемента
[/i][/color]    [color=#B00040]int[/color] num;         [color=#408080][i]//общее число элементов
[/i][/color]     
     
    [color=#408080][i]//ищем следующее свободное место в массиве
[/i][/color]    [color=#B00040]int[/color] get_free_index(){
      [color=#B00040]int[/color] i[color=#666666]=[/color][color=#666666]0[/color];
      [color=#008000][b]for[/b][/color](i[color=#666666]=[/color][color=#666666]0[/color];i[color=#666666]<[/color]MAX;i[color=#666666]++[/color]){
       [color=#008000][b]if[/b][/color]( items[i][color=#666666]->[/color]prev[color=#666666]==[/color]NONE [color=#666666]&&[/color] items[i][color=#666666]->[/color]next[color=#666666]==[/color]NONE ){      
            [color=#008000][b]return[/b][/color] i[color=#666666]+[/color](num[color=#666666]==[/color][color=#666666]1[/color]);
       }
      }
      
      [color=#008000][b]return[/b][/color] NONE;

}

[color=#408080][i]//вставляем значение перед выбранным элементом массива
[/i][/color]    [color=#B00040]void[/color] insert_before([color=#B00040]int[/color] i, T a_value){
      [color=#B00040]int[/color] free_index[color=#666666]=[/color]get_free_index();
      
      items[free_index]       [color=#666666]=[/color] [color=#008000][b]new[/b][/color] Item(a_value);
      items[free_index][color=#666666]->[/color]next [color=#666666]=[/color] i;
      items[free_index][color=#666666]->[/color]prev [color=#666666]=[/color] items[i][color=#666666]->[/color]prev;
      items[i][color=#666666]->[/color]prev          [color=#666666]=[/color] free_index;
      
      [color=#008000][b]if[/b][/color](i [color=#666666]==[/color] first)
        first[color=#666666]=[/color]free_index;
      
      num[color=#666666]++[/color];
      
    }

[color=#B00040]void[/color] insert_after([color=#B00040]int[/color] i, T a_value){
      [color=#B00040]int[/color] free_index[color=#666666]=[/color]get_free_index();
      
      items[free_index]       [color=#666666]=[/color] [color=#008000][b]new[/b][/color] Item(a_value);
      items[free_index][color=#666666]->[/color]prev [color=#666666]=[/color] i;
      
      items[free_index][color=#666666]->[/color]next [color=#666666]=[/color] items[i][color=#666666]->[/color]next;
      
      [color=#008000][b]if[/b][/color](items[i][color=#666666]->[/color]next[color=#666666]!=[/color]NONE)
        items[items[i][color=#666666]->[/color]next][color=#666666]->[/color]prev[color=#666666]=[/color]free_index;
      
      
      items[i][color=#666666]->[/color]next          [color=#666666]=[/color] free_index;
      
      [color=#008000][b]if[/b][/color](i [color=#666666]==[/color] last)
        last[color=#666666]=[/color]free_index;
      
      num[color=#666666]++[/color];
      
    }
    
    
    [color=#408080][i]//ищем и возвращаем индекс элемента в массиве, чье значение равно аргументу
[/i][/color]    [color=#B00040]int[/color] findItem(T value){
      [color=#008000][b]if[/b][/color](isEmpty()) [color=#008000][b]return[/b][/color] NONE;
      [color=#408080][i]//будем возвращать первый найденный индекс
[/i][/color]      
      [color=#B00040]int[/color] i [color=#666666]=[/color] first;
      
      [color=#008000][b]while[/b][/color](items[i][color=#666666]->[/color]next [color=#666666]!=[/color] NONE [color=#666666]&&[/color] items[i][color=#666666]->[/color]value [color=#666666]!=[/color] value){
        i[color=#666666]=[/color]items[i][color=#666666]->[/color]next;
      }
      
      [color=#008000][b]if[/b][/color](items[i][color=#666666]->[/color]value [color=#666666]==[/color] value)
        [color=#008000][b]return[/b][/color] i;

[color=#008000][b]return[/b][/color] NONE;
    }

[color=#408080][i]//получить индекс на элемент по номеру его в списке
[/i][/color]    [color=#B00040]int[/color] getItem([color=#B00040]unsigned[/color] [color=#B00040]int[/color] index){
      [color=#008000][b]if[/b][/color](isEmpty())      [color=#008000][b]return[/b][/color] NONE;
      [color=#008000][b]if[/b][/color](index[color=#666666]==[/color][color=#666666]0[/color])       [color=#008000][b]return[/b][/color] first;
      [color=#008000][b]if[/b][/color](index[color=#666666]==[/color](num[color=#666666]-[/color][color=#666666]1[/color])) [color=#008000][b]return[/b][/color] last;
      [color=#008000][b]if[/b][/color](index[color=#666666]>=[/color]num)     [color=#008000][b]return[/b][/color] NONE; 
      
      [color=#B00040]int[/color] i;

[color=#408080][i]//определяем с какого конца легче двигатся
[/i][/color]      [color=#008000][b]if[/b][/color](index[color=#666666]>=[/color]num[color=#666666]/[/color][color=#666666]2[/color]){
        i[color=#666666]=[/color]last;
        index[color=#666666]=[/color]num[color=#666666]-[/color]index[color=#666666]-[/color][color=#666666]1[/color];
        [color=#008000][b]while[/b][/color](index){
          i[color=#666666]=[/color]items[i][color=#666666]->[/color]prev;
          index[color=#666666]--[/color];
        }
      }
      [color=#008000][b]else[/b][/color]{
        i[color=#666666]=[/color]first;
        [color=#008000][b]while[/b][/color](index){
          i[color=#666666]=[/color]items[i][color=#666666]->[/color]next;
          index[color=#666666]--[/color];
        }
      }
      
      [color=#008000][b]return[/b][/color] i;
    }

[color=#408080][i]//удаляем элемент по его номеру в массиве
[/i][/color]    [color=#B00040]void[/color] removeItem([color=#B00040]int[/color] i){
      [color=#008000][b]if[/b][/color](isEmpty()) [color=#008000][b]return[/b][/color];
      
      [color=#008000][b]if[/b][/color](items[i][color=#666666]->[/color]prev [color=#666666]!=[/color] NONE)
        items[items[i][color=#666666]->[/color]prev][color=#666666]->[/color]next[color=#666666]=[/color]items[i][color=#666666]->[/color]next;
        
      [color=#008000][b]if[/b][/color](items[i][color=#666666]->[/color]next [color=#666666]!=[/color] NONE)
        items[items[i][color=#666666]->[/color]next][color=#666666]->[/color]prev[color=#666666]=[/color]items[i][color=#666666]->[/color]prev;

num[color=#666666]--[/color];
      
      [color=#008000][b]if[/b][/color](i [color=#666666]==[/color] first){
          first[color=#666666]=[/color]items[i][color=#666666]->[/color]next;
      }

[color=#008000][b]if[/b][/color](i [color=#666666]==[/color] last){
          last[color=#666666]=[/color]items[i][color=#666666]->[/color]prev;        
      }
      
      items[i][color=#666666]->[/color]prev[color=#666666]=[/color]NONE;
      items[i][color=#666666]->[/color]next[color=#666666]=[/color]NONE;
      
      
      [color=#008000][b]if[/b][/color]([color=#666666]![/color]num){
        first[color=#666666]=[/color][color=#666666]0[/color];
        last[color=#666666]=[/color][color=#666666]0[/color];
      }

}

[color=#008000][b]public[/b][/color][color=#666666]:[/color]
    List (){
      num[color=#666666]=[/color][color=#666666]0[/color];
      first[color=#666666]=[/color][color=#666666]0[/color];
      last[color=#666666]=[/color][color=#666666]0[/color];
      [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] i[color=#666666]=[/color][color=#666666]0[/color];i[color=#666666]<[/color]MAX;i[color=#666666]++[/color]){
        items[i][color=#666666]=[/color][color=#008000][b]new[/b][/color] Item;
      }
      
    }
    
    [color=#666666]~[/color]List (){
      
    }
    
    [color=#408080][i]// добавить в конец
[/i][/color]    [color=#B00040]void[/color] add(T value){
      [color=#B00040]int[/color] free_index[color=#666666]=[/color]get_free_index();
      items[free_index] [color=#666666]=[/color] [color=#008000][b]new[/b][/color] Item(value);
      [color=#008000][b]if[/b][/color]([color=#666666]![/color]num){
        first [color=#666666]=[/color] free_index;
        last  [color=#666666]=[/color] free_index;
      }
      [color=#008000][b]else[/b][/color]{
        items[free_index][color=#666666]->[/color]prev [color=#666666]=[/color] last;
        items[last]      [color=#666666]->[/color]next [color=#666666]=[/color] free_index;
        last                    [color=#666666]=[/color] free_index;
      }
      num[color=#666666]++[/color];
    }
    
    [color=#408080][i]// добавить элемент в позицию с указанным индексом
[/i][/color]    [color=#B00040]void[/color] insert([color=#B00040]unsigned[/color] [color=#B00040]int[/color] index, T a_value){
      [color=#408080][i]//будем добавлять перед этим эл-том
[/i][/color]      [color=#408080][i]//cначало досчитаем до этого элемента
[/i][/color]      
      [color=#008000][b]if[/b][/color]([color=#666666]![/color]index)
        [color=#008000][b]return[/b][/color] insert_before(first, a_value);
        
      [color=#408080][i]//если индекс превышает число эл-тов то добавляем в конец
[/i][/color]      [color=#008000][b]if[/b][/color](index[color=#666666]>[/color]num)
        [color=#008000][b]return[/b][/color] add(a_value);
      
      [color=#B00040]int[/color] i;
      
     
      [color=#408080][i]//определяем с какого конца легче двигатся
[/i][/color]      [color=#008000][b]if[/b][/color](index[color=#666666]>=[/color]num[color=#666666]/[/color][color=#666666]2[/color]){
        i[color=#666666]=[/color]last;
        index[color=#666666]=[/color]num[color=#666666]-[/color]index;
        [color=#008000][b]while[/b][/color](index){
          i[color=#666666]=[/color]items[i][color=#666666]->[/color]prev;
          index[color=#666666]--[/color];
        }
      }
      [color=#008000][b]else[/b][/color]{
        i[color=#666666]=[/color]first;
        [color=#008000][b]while[/b][/color](index){
          i[color=#666666]=[/color]items[i][color=#666666]->[/color]next;
          index[color=#666666]--[/color];
        }
      }
      printf([color=#BA2121]"found %i[/color][color=#BB6622][b]\n[/b][/color][color=#BA2121]"[/color],i);
      [color=#008000][b]return[/b][/color] insert_after(i,a_value);
    }
    
    [color=#408080][i]// установить значение по индексу 
[/i][/color]    [color=#B00040]void[/color] set([color=#B00040]int[/color] index, T value){
      [color=#B00040]int[/color] i [color=#666666]=[/color] getItem(index);
      items[i][color=#666666]->[/color]value[color=#666666]=[/color]value;
    };
    
    
    
    [color=#408080][i]// получить значение по индексу
[/i][/color]    T get([color=#B00040]int[/color] index){
      [color=#B00040]int[/color] i[color=#666666]=[/color]getItem(index);
      [color=#008000][b]if[/b][/color](i[color=#666666]!=[/color]NONE)
        [color=#008000][b]return[/b][/color] items[i][color=#666666]->[/color]value;
      [color=#008000][b]return[/b][/color] NONE;
    }
    
    [color=#408080][i]// очистить список 
[/i][/color]    [color=#B00040]void[/color] clear (){
      num[color=#666666]=[/color][color=#666666]0[/color];
      first[color=#666666]=[/color][color=#666666]0[/color];
      last[color=#666666]=[/color][color=#666666]0[/color];
      [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] i[color=#666666]=[/color][color=#666666]0[/color];i[color=#666666]<[/color]MAX;i[color=#666666]++[/color]){
        items[i][color=#666666]=[/color][color=#008000][b]new[/b][/color] Item;
      }
    }
    
    [color=#408080][i]// получить количество 
[/i][/color]    [color=#B00040]int[/color] count(){
      [color=#008000][b]return[/b][/color] num;
    }
    
    [color=#408080][i]// пустой ли список 
[/i][/color]    [color=#B00040]bool[/color] isEmpty(){
      [color=#008000][b]return[/b][/color] [color=#666666]![/color]num;
    }
    
    [color=#408080][i]// получить индекс указаного элемента. Если: элемента нет, вернуть -1
[/i][/color]    [color=#B00040]int[/color] indexOf(T value){
      [color=#408080][i]//будем возвращать первый найденный индекс
[/i][/color]      
      [color=#B00040]int[/color] i[color=#666666]=[/color]first;
      [color=#B00040]int[/color] j[color=#666666]=[/color][color=#666666]0[/color];
      [color=#008000][b]while[/b][/color](items[i][color=#666666]->[/color]next [color=#666666]!=[/color] NONE [color=#666666]&&[/color] items[i][color=#666666]->[/color]value [color=#666666]!=[/color] value){
        i[color=#666666]=[/color]items[i][color=#666666]->[/color]next;
        j[color=#666666]++[/color];
      }
      
      [color=#008000][b]if[/b][/color](items[i][color=#666666]->[/color]value [color=#666666]==[/color] value)
        [color=#008000][b]return[/b][/color] j;

[color=#008000][b]return[/b][/color] NONE;
      
    }
    
    [color=#408080][i]// проверить, принадлежит ли элемент списку
[/i][/color]    [color=#B00040]bool[/color] contains(T value){
      [color=#008000][b]return[/b][/color] ([color=#B00040]bool[/color])(indexOf(value)[color=#666666]+[/color][color=#666666]1[/color]);
    }
    
    [color=#408080][i]// удалить все вхождения элемента из списка
[/i][/color]    [color=#B00040]void[/color] remove(T value){
      
      [color=#008000][b]while[/b][/color]([color=#008000][b]true[/b][/color]){
        [color=#B00040]int[/color] i[color=#666666]=[/color]findItem(value);
        
        [color=#008000][b]if[/b][/color](i[color=#666666]==[/color]NONE)
          [color=#008000][b]break[/b][/color];
          
        removeItem(i);
      }
        
      
      
    }
    
    [color=#408080][i]// удалить элемент с заданным индексом
[/i][/color]    [color=#B00040]void[/color] removeAt([color=#B00040]int[/color] index){
      [color=#B00040]int[/color] i[color=#666666]=[/color]getItem(index);
      [color=#008000][b]if[/b][/color](i[color=#666666]!=[/color]NONE)
        removeItem(i);
      
    }
    
    
    
    [color=#B00040]void[/color] print_all(){
      [color=#B00040]int[/color] i[color=#666666]=[/color]first;
      printf([color=#BA2121]"[/color][color=#BB6622][b]\n\n[/b][/color][color=#BA2121]  Count elements: %i [/color][color=#BB6622][b]\n[/b][/color][color=#BA2121]"[/color], num);
      printf([color=#BA2121]"  First index: %i [/color][color=#BB6622][b]\n[/b][/color][color=#BA2121]"[/color],first);
      printf([color=#BA2121]"  Last index: %i [/color][color=#BB6622][b]\n[/b][/color][color=#BA2121]"[/color],last);
      printf([color=#BA2121]"  index  |  prev  |  next  |  value  |  arr_key  [/color][color=#BB6622][b]\n[/b][/color][color=#BA2121]"[/color]);
      [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] j[color=#666666]=[/color][color=#666666]0[/color];j[color=#666666]<[/color]num;j[color=#666666]++[/color]){
        [color=#408080][i]//if(i==NONE) break;
[/i][/color]        printf([color=#BA2121]"  %4i   |  %3i   |  %3i   |  %3i  |   %3i [/color][color=#BB6622][b]\n[/b][/color][color=#BA2121]"[/color],i,items[i][color=#666666]->[/color]prev,items[i][color=#666666]->[/color]next, items[i][color=#666666]->[/color]value, i);
        i[color=#666666]=[/color]items[i][color=#666666]->[/color]next;
      }
      
    }

[color=#408080][i]// скопировать список в массив (предполагается, что массив содержит достаточное количество элементов для выполнения операции) 
[/i][/color]    [color=#B00040]void[/color] copyTo(T[color=#666666]*[/color] arr){
      [color=#B00040]int[/color] i[color=#666666]=[/color]first;
      [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] j[color=#666666]=[/color][color=#666666]0[/color];j[color=#666666]<[/color]num;j[color=#666666]++[/color]){
        arr[j] [color=#666666]=[/color] items[i][color=#666666]->[/color]value;
        i      [color=#666666]=[/color] items[i][color=#666666]->[/color]next;
      }
    }
    
    [color=#408080][i]// получить итератор для обхода спискa
[/i][/color]    [color=#408080][i]//Iterator* getIterator(){
[/i][/color]      
    [color=#408080][i]//}
[/i][/color]

};

[color=#B00040]void[/color] test(){
    List[color=#666666]*[/color] list [color=#666666]=[/color] [color=#008000][b]new[/b][/color] List();
    
    [color=#408080][i]/*тестирование на пустоту*/[/i][/color]
    assert(list[color=#666666]->[/color]isEmpty() ) ;
    assert(list[color=#666666]->[/color]count() [color=#666666]==[/color] [color=#666666]0[/color]);

[color=#408080][i]/*тестирование на дополнение в конец, изменение числа элементов, наличие элементов */[/i][/color]
    [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] i[color=#666666]=[/color][color=#666666]0[/color];i[color=#666666]<[/color][color=#666666]10[/color];i[color=#666666]++[/color]){
      list[color=#666666]->[/color]add(i);
      assert([color=#666666]![/color]list[color=#666666]->[/color]isEmpty());
      assert(list[color=#666666]->[/color]get(i)[color=#666666]==[/color]i);
      assert(list[color=#666666]->[/color]count() [color=#666666]==[/color] i[color=#666666]+[/color][color=#666666]1[/color]);
      
      assert(list[color=#666666]->[/color]contains(i));
      assert(list[color=#666666]->[/color]indexOf(i)[color=#666666]==[/color]i);
      
      assert([color=#666666]![/color]list[color=#666666]->[/color]contains(i[color=#666666]+[/color][color=#666666]1[/color]));
      assert(list[color=#666666]->[/color]indexOf(i[color=#666666]+[/color][color=#666666]1[/color])[color=#666666]==[/color]NONE);
    }
    
    
    [color=#408080][i]/*Тестирование удаления по значению*/[/i][/color]
    [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] i[color=#666666]=[/color][color=#666666]0[/color];i[color=#666666]<[/color][color=#666666]10[/color];i[color=#666666]+=[/color][color=#666666]2[/color]){
      list[color=#666666]->[/color]remove(i);
      assert(list[color=#666666]->[/color]count() [color=#666666]==[/color] [color=#666666]10[/color][color=#666666]-[/color]i[color=#666666]/[/color][color=#666666]2[/color][color=#666666]-[/color][color=#666666]1[/color]);
      assert([color=#666666]![/color]list[color=#666666]->[/color]contains(i));
    }

[color=#408080][i]/*Тестирование удаления по номеру элемента в списке*/[/i][/color]    
    list[color=#666666]->[/color]removeAt([color=#666666]4[/color]);
    list[color=#666666]->[/color]removeAt([color=#666666]3[/color]);
    list[color=#666666]->[/color]removeAt([color=#666666]2[/color]);
    list[color=#666666]->[/color]removeAt([color=#666666]1[/color]);
    list[color=#666666]->[/color]removeAt([color=#666666]0[/color]);

assert(list[color=#666666]->[/color]isEmpty()) ;
    assert(list[color=#666666]->[/color]count() [color=#666666]==[/color] [color=#666666]0[/color]);

[color=#408080][i]/*Тестирование вставки в начало*/[/i][/color]
    [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] i[color=#666666]=[/color][color=#666666]1[/color];i[color=#666666]<[/color][color=#666666]10[/color];i[color=#666666]++[/color]){
      list[color=#666666]->[/color]insert([color=#666666]0[/color],i);
    }
    
    [color=#408080][i]/*Тестирование очистки*/[/i][/color]
    list[color=#666666]->[/color]clear();
    assert(list[color=#666666]->[/color]isEmpty() ) ;
    assert(list[color=#666666]->[/color]count() [color=#666666]==[/color] [color=#666666]0[/color]);
    
    [color=#408080][i]/*Тестирование удаления одинаковых элементов*/[/i][/color]
    [color=#008000][b]for[/b][/color]([color=#B00040]int[/color] i[color=#666666]=[/color][color=#666666]0[/color];i[color=#666666]<[/color][color=#666666]100[/color];i[color=#666666]++[/color])
      list[color=#666666]->[/color]add([color=#666666]486[/color]);
    list[color=#666666]->[/color]remove([color=#666666]486[/color]);
    assert(list[color=#666666]->[/color]isEmpty() ) ;
    assert(list[color=#666666]->[/color]count() [color=#666666]==[/color] [color=#666666]0[/color]);

[color=#408080][i]/*Тестирование изменения*/[/i][/color]
    list[color=#666666]->[/color]add([color=#666666]1[/color]);
    assert(list[color=#666666]->[/color]get([color=#666666]0[/color])[color=#666666]==[/color][color=#666666]1[/color]);
    list[color=#666666]->[/color]set([color=#666666]0[/color],[color=#666666]31337[/color]);
    assert(list[color=#666666]->[/color]get([color=#666666]0[/color])[color=#666666]==[/color][color=#666666]31337[/color]);
    
    list[color=#666666]->[/color]insert([color=#666666]0[/color],[color=#666666]1[/color]);
  list[color=#666666]->[/color]print_all();

list[color=#666666]->[/color]insert([color=#666666]1[/color],[color=#666666]2[/color]);
    list[color=#666666]->[/color]insert([color=#666666]1[/color],[color=#666666]3[/color]);
    list[color=#666666]->[/color]insert([color=#666666]1[/color],[color=#666666]4[/color]);
    list[color=#666666]->[/color]insert([color=#666666]1[/color],[color=#666666]5[/color]);

list[color=#666666]->[/color]print_all();

[color=#408080][i]//assert(list->contains(1));
[/i][/color]    [color=#408080][i]//assert(!list->contains(568));
[/i][/color]
}

[color=#B00040]int[/color] main(){
  test();
  [color=#B00040]int[/color] i;
  scanf([color=#BA2121]"%i"[/color],[color=#666666]&[/color]i);
  [color=#008000][b]return[/b][/color] [color=#666666]0[/color];
}

--------------------------------------
Colored with http://dumpz.org

Light HTML Copy To Clipboarddone!

That method generates HTML with CSS classes. Hence you'll need the style sheet file

<div class="highlight"><pre><div id="lc1"><span class="cp">#include &lt;cstdio&gt;</span>
</div><div id="lc2"><span class="cp">#include &lt;cassert&gt;</span>
</div><div id="lc3">
</div><div id="lc4">
</div><div id="lc5"><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
</div><div id="lc6">
</div><div id="lc7"><span class="k">typedef</span> <span class="kt">int</span> <span class="n">T</span><span class="p">;</span>
</div><div id="lc8"><span class="k">const</span> <span class="kt">int</span> <span class="n">MAX</span><span class="o">=</span><span class="mi">1000</span><span class="p">;</span>
</div><div id="lc9"><span class="k">const</span> <span class="kt">int</span> <span class="n">NONE</span><span class="o">=-</span><span class="mi">1</span><span class="p">;</span>
</div><div id="lc10">
</div><div id="lc11"><span class="k">class</span> <span class="nc">List</span><span class="p">{</span>
</div><div id="lc12">    <span class="k">struct</span> <span class="n">Item</span><span class="p">{</span>
</div><div id="lc13">      <span class="kt">int</span> <span class="n">prev</span><span class="p">;</span>
</div><div id="lc14">      <span class="kt">int</span> <span class="n">next</span><span class="p">;</span>
</div><div id="lc15">      <span class="n">T</span> <span class="n">value</span><span class="p">;</span>
</div><div id="lc16">      
</div><div id="lc17">      
</div><div id="lc18">      <span class="n">Item</span><span class="p">(</span><span class="kt">int</span> <span class="n">a_prev</span><span class="p">,</span> <span class="kt">int</span> <span class="n">a_next</span><span class="p">,</span> <span class="n">T</span> <span class="n">a_value</span><span class="p">){</span>
</div><div id="lc19">        <span class="n">prev</span><span class="o">=</span><span class="n">a_prev</span><span class="p">;</span>
</div><div id="lc20">        <span class="n">next</span><span class="o">=</span><span class="n">a_next</span><span class="p">;</span>
</div><div id="lc21">        <span class="n">value</span><span class="o">=</span><span class="n">a_value</span><span class="p">;</span>
</div><div id="lc22">      <span class="p">}</span>
</div><div id="lc23">      
</div><div id="lc24">      <span class="n">Item</span><span class="p">(</span><span class="n">T</span> <span class="n">a_value</span><span class="p">){</span>
</div><div id="lc25">        <span class="n">prev</span><span class="o">=</span><span class="n">NONE</span><span class="p">;</span>
</div><div id="lc26">        <span class="n">next</span><span class="o">=</span><span class="n">NONE</span><span class="p">;</span>
</div><div id="lc27">        <span class="n">value</span><span class="o">=</span><span class="n">a_value</span><span class="p">;</span>
</div><div id="lc28">      <span class="p">}</span>
</div><div id="lc29">      
</div><div id="lc30">      <span class="n">Item</span><span class="p">(){</span>
</div><div id="lc31">        <span class="n">prev</span><span class="o">=</span><span class="n">NONE</span><span class="p">;</span>
</div><div id="lc32">        <span class="n">next</span><span class="o">=</span><span class="n">NONE</span><span class="p">;</span>
</div><div id="lc33">        <span class="n">value</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc34">      <span class="p">}</span>
</div><div id="lc35">      
</div><div id="lc36">    <span class="p">};</span>
</div><div id="lc37">  
</div><div id="lc38">    <span class="n">Item</span><span class="o">*</span> <span class="n">items</span><span class="p">[</span><span class="n">MAX</span><span class="p">];</span>
</div><div id="lc39">    <span class="kt">int</span> <span class="n">first</span><span class="p">;</span>       <span class="c1">//индекс начального элемента</span>
</div><div id="lc40">    <span class="kt">int</span> <span class="n">last</span><span class="p">;</span>        <span class="c1">//индекс конечного элемента</span>
</div><div id="lc41">    <span class="kt">int</span> <span class="n">num</span><span class="p">;</span>         <span class="c1">//общее число элементов</span>
</div><div id="lc42">     
</div><div id="lc43">     
</div><div id="lc44">    <span class="c1">//ищем следующее свободное место в массиве</span>
</div><div id="lc45">    <span class="kt">int</span> <span class="n">get_free_index</span><span class="p">(){</span>
</div><div id="lc46">      <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc47">      <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</div><div id="lc48">       <span class="k">if</span><span class="p">(</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="o">==</span><span class="n">NONE</span> <span class="o">&amp;&amp;</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">==</span><span class="n">NONE</span> <span class="p">){</span>      
</div><div id="lc49">            <span class="k">return</span> <span class="n">i</span><span class="o">+</span><span class="p">(</span><span class="n">num</span><span class="o">==</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc50">       <span class="p">}</span>
</div><div id="lc51">      <span class="p">}</span>
</div><div id="lc52">      
</div><div id="lc53">      <span class="k">return</span> <span class="n">NONE</span><span class="p">;</span>
</div><div id="lc54">
</div><div id="lc55">    <span class="p">}</span>
</div><div id="lc56">
</div><div id="lc57">    <span class="c1">//вставляем значение перед выбранным элементом массива</span>
</div><div id="lc58">    <span class="kt">void</span> <span class="n">insert_before</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">T</span> <span class="n">a_value</span><span class="p">){</span>
</div><div id="lc59">      <span class="kt">int</span> <span class="n">free_index</span><span class="o">=</span><span class="n">get_free_index</span><span class="p">();</span>
</div><div id="lc60">      
</div><div id="lc61">      <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span>       <span class="o">=</span> <span class="k">new</span> <span class="n">Item</span><span class="p">(</span><span class="n">a_value</span><span class="p">);</span>
</div><div id="lc62">      <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
</div><div id="lc63">      <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span> <span class="o">=</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="p">;</span>
</div><div id="lc64">      <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span>          <span class="o">=</span> <span class="n">free_index</span><span class="p">;</span>
</div><div id="lc65">      
</div><div id="lc66">      <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">first</span><span class="p">)</span>
</div><div id="lc67">        <span class="n">first</span><span class="o">=</span><span class="n">free_index</span><span class="p">;</span>
</div><div id="lc68">      
</div><div id="lc69">      <span class="n">num</span><span class="o">++</span><span class="p">;</span>
</div><div id="lc70">      
</div><div id="lc71">    <span class="p">}</span>
</div><div id="lc72">
</div><div id="lc73">
</div><div id="lc74">    <span class="kt">void</span> <span class="n">insert_after</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">T</span> <span class="n">a_value</span><span class="p">){</span>
</div><div id="lc75">      <span class="kt">int</span> <span class="n">free_index</span><span class="o">=</span><span class="n">get_free_index</span><span class="p">();</span>
</div><div id="lc76">      
</div><div id="lc77">      <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span>       <span class="o">=</span> <span class="k">new</span> <span class="n">Item</span><span class="p">(</span><span class="n">a_value</span><span class="p">);</span>
</div><div id="lc78">      <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
</div><div id="lc79">      
</div><div id="lc80">      <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc81">      
</div><div id="lc82">      <span class="k">if</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">!=</span><span class="n">NONE</span><span class="p">)</span>
</div><div id="lc83">        <span class="n">items</span><span class="p">[</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="o">=</span><span class="n">free_index</span><span class="p">;</span>
</div><div id="lc84">      
</div><div id="lc85">      
</div><div id="lc86">      <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span>          <span class="o">=</span> <span class="n">free_index</span><span class="p">;</span>
</div><div id="lc87">      
</div><div id="lc88">      <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">last</span><span class="p">)</span>
</div><div id="lc89">        <span class="n">last</span><span class="o">=</span><span class="n">free_index</span><span class="p">;</span>
</div><div id="lc90">      
</div><div id="lc91">      <span class="n">num</span><span class="o">++</span><span class="p">;</span>
</div><div id="lc92">      
</div><div id="lc93">    <span class="p">}</span>
</div><div id="lc94">    
</div><div id="lc95">    
</div><div id="lc96">    <span class="c1">//ищем и возвращаем индекс элемента в массиве, чье значение равно аргументу</span>
</div><div id="lc97">    <span class="kt">int</span> <span class="n">findItem</span><span class="p">(</span><span class="n">T</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc98">      <span class="k">if</span><span class="p">(</span><span class="n">isEmpty</span><span class="p">())</span> <span class="k">return</span> <span class="n">NONE</span><span class="p">;</span>
</div><div id="lc99">      <span class="c1">//будем возвращать первый найденный индекс</span>
</div><div id="lc100">      
</div><div id="lc101">      <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">first</span><span class="p">;</span>
</div><div id="lc102">      
</div><div id="lc103">      <span class="k">while</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">!=</span> <span class="n">NONE</span> <span class="o">&amp;&amp;</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span> <span class="o">!=</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc104">        <span class="n">i</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc105">      <span class="p">}</span>
</div><div id="lc106">      
</div><div id="lc107">      <span class="k">if</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span> <span class="o">==</span> <span class="n">value</span><span class="p">)</span>
</div><div id="lc108">        <span class="k">return</span> <span class="n">i</span><span class="p">;</span>
</div><div id="lc109">
</div><div id="lc110">      <span class="k">return</span> <span class="n">NONE</span><span class="p">;</span>
</div><div id="lc111">    <span class="p">}</span>
</div><div id="lc112">
</div><div id="lc113">    <span class="c1">//получить индекс на элемент по номеру его в списке</span>
</div><div id="lc114">    <span class="kt">int</span> <span class="n">getItem</span><span class="p">(</span><span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">index</span><span class="p">){</span>
</div><div id="lc115">      <span class="k">if</span><span class="p">(</span><span class="n">isEmpty</span><span class="p">())</span>      <span class="k">return</span> <span class="n">NONE</span><span class="p">;</span>
</div><div id="lc116">      <span class="k">if</span><span class="p">(</span><span class="n">index</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span>       <span class="k">return</span> <span class="n">first</span><span class="p">;</span>
</div><div id="lc117">      <span class="k">if</span><span class="p">(</span><span class="n">index</span><span class="o">==</span><span class="p">(</span><span class="n">num</span><span class="o">-</span><span class="mi">1</span><span class="p">))</span> <span class="k">return</span> <span class="n">last</span><span class="p">;</span>
</div><div id="lc118">      <span class="k">if</span><span class="p">(</span><span class="n">index</span><span class="o">&gt;=</span><span class="n">num</span><span class="p">)</span>     <span class="k">return</span> <span class="n">NONE</span><span class="p">;</span> 
</div><div id="lc119">      
</div><div id="lc120">      <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
</div><div id="lc121">
</div><div id="lc122">      <span class="c1">//определяем с какого конца легче двигатся</span>
</div><div id="lc123">      <span class="k">if</span><span class="p">(</span><span class="n">index</span><span class="o">&gt;=</span><span class="n">num</span><span class="o">/</span><span class="mi">2</span><span class="p">){</span>
</div><div id="lc124">        <span class="n">i</span><span class="o">=</span><span class="n">last</span><span class="p">;</span>
</div><div id="lc125">        <span class="n">index</span><span class="o">=</span><span class="n">num</span><span class="o">-</span><span class="n">index</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
</div><div id="lc126">        <span class="k">while</span><span class="p">(</span><span class="n">index</span><span class="p">){</span>
</div><div id="lc127">          <span class="n">i</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="p">;</span>
</div><div id="lc128">          <span class="n">index</span><span class="o">--</span><span class="p">;</span>
</div><div id="lc129">        <span class="p">}</span>
</div><div id="lc130">      <span class="p">}</span>
</div><div id="lc131">      <span class="k">else</span><span class="p">{</span>
</div><div id="lc132">        <span class="n">i</span><span class="o">=</span><span class="n">first</span><span class="p">;</span>
</div><div id="lc133">        <span class="k">while</span><span class="p">(</span><span class="n">index</span><span class="p">){</span>
</div><div id="lc134">          <span class="n">i</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc135">          <span class="n">index</span><span class="o">--</span><span class="p">;</span>
</div><div id="lc136">        <span class="p">}</span>
</div><div id="lc137">      <span class="p">}</span>
</div><div id="lc138">      
</div><div id="lc139">      <span class="k">return</span> <span class="n">i</span><span class="p">;</span>
</div><div id="lc140">    <span class="p">}</span>
</div><div id="lc141">
</div><div id="lc142">    <span class="c1">//удаляем элемент по его номеру в массиве</span>
</div><div id="lc143">    <span class="kt">void</span> <span class="n">removeItem</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">){</span>
</div><div id="lc144">      <span class="k">if</span><span class="p">(</span><span class="n">isEmpty</span><span class="p">())</span> <span class="k">return</span><span class="p">;</span>
</div><div id="lc145">      
</div><div id="lc146">      <span class="k">if</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span> <span class="o">!=</span> <span class="n">NONE</span><span class="p">)</span>
</div><div id="lc147">        <span class="n">items</span><span class="p">[</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc148">        
</div><div id="lc149">      <span class="k">if</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">!=</span> <span class="n">NONE</span><span class="p">)</span>
</div><div id="lc150">        <span class="n">items</span><span class="p">[</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="p">;</span>
</div><div id="lc151">
</div><div id="lc152">
</div><div id="lc153">      <span class="n">num</span><span class="o">--</span><span class="p">;</span>
</div><div id="lc154">      
</div><div id="lc155">      <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">first</span><span class="p">){</span>
</div><div id="lc156">          <span class="n">first</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc157">      <span class="p">}</span>    
</div><div id="lc158">      
</div><div id="lc159">
</div><div id="lc160">      <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">last</span><span class="p">){</span>
</div><div id="lc161">          <span class="n">last</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="p">;</span>        
</div><div id="lc162">      <span class="p">}</span>
</div><div id="lc163">      
</div><div id="lc164">      <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="o">=</span><span class="n">NONE</span><span class="p">;</span>
</div><div id="lc165">      <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">=</span><span class="n">NONE</span><span class="p">;</span>
</div><div id="lc166">      
</div><div id="lc167">      
</div><div id="lc168">      <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">num</span><span class="p">){</span>
</div><div id="lc169">        <span class="n">first</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc170">        <span class="n">last</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc171">      <span class="p">}</span>
</div><div id="lc172">      
</div><div id="lc173">
</div><div id="lc174">    <span class="p">}</span>
</div><div id="lc175">
</div><div id="lc176">    <span class="k">public</span><span class="o">:</span>
</div><div id="lc177">    <span class="n">List</span> <span class="p">(){</span>
</div><div id="lc178">      <span class="n">num</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc179">      <span class="n">first</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc180">      <span class="n">last</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc181">      <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</div><div id="lc182">        <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="k">new</span> <span class="n">Item</span><span class="p">;</span>
</div><div id="lc183">      <span class="p">}</span>
</div><div id="lc184">      
</div><div id="lc185">    <span class="p">}</span>
</div><div id="lc186">    
</div><div id="lc187">    <span class="o">~</span><span class="n">List</span> <span class="p">(){</span>
</div><div id="lc188">      
</div><div id="lc189">    <span class="p">}</span>
</div><div id="lc190">    
</div><div id="lc191">    <span class="c1">// добавить в конец</span>
</div><div id="lc192">    <span class="kt">void</span> <span class="n">add</span><span class="p">(</span><span class="n">T</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc193">      <span class="kt">int</span> <span class="n">free_index</span><span class="o">=</span><span class="n">get_free_index</span><span class="p">();</span>
</div><div id="lc194">      <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Item</span><span class="p">(</span><span class="n">value</span><span class="p">);</span>
</div><div id="lc195">      <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">num</span><span class="p">){</span>
</div><div id="lc196">        <span class="n">first</span> <span class="o">=</span> <span class="n">free_index</span><span class="p">;</span>
</div><div id="lc197">        <span class="n">last</span>  <span class="o">=</span> <span class="n">free_index</span><span class="p">;</span>
</div><div id="lc198">      <span class="p">}</span>
</div><div id="lc199">      <span class="k">else</span><span class="p">{</span>
</div><div id="lc200">        <span class="n">items</span><span class="p">[</span><span class="n">free_index</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span> <span class="o">=</span> <span class="n">last</span><span class="p">;</span>
</div><div id="lc201">        <span class="n">items</span><span class="p">[</span><span class="n">last</span><span class="p">]</span>      <span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">free_index</span><span class="p">;</span>
</div><div id="lc202">        <span class="n">last</span>                    <span class="o">=</span> <span class="n">free_index</span><span class="p">;</span>
</div><div id="lc203">      <span class="p">}</span>
</div><div id="lc204">      <span class="n">num</span><span class="o">++</span><span class="p">;</span>
</div><div id="lc205">    <span class="p">}</span>
</div><div id="lc206">    
</div><div id="lc207">    <span class="c1">// добавить элемент в позицию с указанным индексом</span>
</div><div id="lc208">    <span class="kt">void</span> <span class="n">insert</span><span class="p">(</span><span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">index</span><span class="p">,</span> <span class="n">T</span> <span class="n">a_value</span><span class="p">){</span>
</div><div id="lc209">      <span class="c1">//будем добавлять перед этим эл-том</span>
</div><div id="lc210">      <span class="c1">//cначало досчитаем до этого элемента</span>
</div><div id="lc211">      
</div><div id="lc212">      <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">index</span><span class="p">)</span>
</div><div id="lc213">        <span class="k">return</span> <span class="n">insert_before</span><span class="p">(</span><span class="n">first</span><span class="p">,</span> <span class="n">a_value</span><span class="p">);</span>
</div><div id="lc214">        
</div><div id="lc215">      <span class="c1">//если индекс превышает число эл-тов то добавляем в конец</span>
</div><div id="lc216">      <span class="k">if</span><span class="p">(</span><span class="n">index</span><span class="o">&gt;</span><span class="n">num</span><span class="p">)</span>
</div><div id="lc217">        <span class="k">return</span> <span class="n">add</span><span class="p">(</span><span class="n">a_value</span><span class="p">);</span>
</div><div id="lc218">      
</div><div id="lc219">      <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
</div><div id="lc220">      
</div><div id="lc221">     
</div><div id="lc222">      <span class="c1">//определяем с какого конца легче двигатся</span>
</div><div id="lc223">      <span class="k">if</span><span class="p">(</span><span class="n">index</span><span class="o">&gt;=</span><span class="n">num</span><span class="o">/</span><span class="mi">2</span><span class="p">){</span>
</div><div id="lc224">        <span class="n">i</span><span class="o">=</span><span class="n">last</span><span class="p">;</span>
</div><div id="lc225">        <span class="n">index</span><span class="o">=</span><span class="n">num</span><span class="o">-</span><span class="n">index</span><span class="p">;</span>
</div><div id="lc226">        <span class="k">while</span><span class="p">(</span><span class="n">index</span><span class="p">){</span>
</div><div id="lc227">          <span class="n">i</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="p">;</span>
</div><div id="lc228">          <span class="n">index</span><span class="o">--</span><span class="p">;</span>
</div><div id="lc229">        <span class="p">}</span>
</div><div id="lc230">      <span class="p">}</span>
</div><div id="lc231">      <span class="k">else</span><span class="p">{</span>
</div><div id="lc232">        <span class="n">i</span><span class="o">=</span><span class="n">first</span><span class="p">;</span>
</div><div id="lc233">        <span class="k">while</span><span class="p">(</span><span class="n">index</span><span class="p">){</span>
</div><div id="lc234">          <span class="n">i</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc235">          <span class="n">index</span><span class="o">--</span><span class="p">;</span>
</div><div id="lc236">        <span class="p">}</span>
</div><div id="lc237">      <span class="p">}</span>
</div><div id="lc238">      <span class="n">printf</span><span class="p">(</span><span class="s">&quot;found %i</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc239">      <span class="k">return</span> <span class="n">insert_after</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">a_value</span><span class="p">);</span>
</div><div id="lc240">    <span class="p">}</span>
</div><div id="lc241">    
</div><div id="lc242">    <span class="c1">// установить значение по индексу </span>
</div><div id="lc243">    <span class="kt">void</span> <span class="n">set</span><span class="p">(</span><span class="kt">int</span> <span class="n">index</span><span class="p">,</span> <span class="n">T</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc244">      <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">getItem</span><span class="p">(</span><span class="n">index</span><span class="p">);</span>
</div><div id="lc245">      <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span><span class="o">=</span><span class="n">value</span><span class="p">;</span>
</div><div id="lc246">    <span class="p">};</span>
</div><div id="lc247">    
</div><div id="lc248">    
</div><div id="lc249">    
</div><div id="lc250">    <span class="c1">// получить значение по индексу</span>
</div><div id="lc251">    <span class="n">T</span> <span class="n">get</span><span class="p">(</span><span class="kt">int</span> <span class="n">index</span><span class="p">){</span>
</div><div id="lc252">      <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">getItem</span><span class="p">(</span><span class="n">index</span><span class="p">);</span>
</div><div id="lc253">      <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">!=</span><span class="n">NONE</span><span class="p">)</span>
</div><div id="lc254">        <span class="k">return</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">;</span>
</div><div id="lc255">      <span class="k">return</span> <span class="n">NONE</span><span class="p">;</span>
</div><div id="lc256">    <span class="p">}</span>
</div><div id="lc257">    
</div><div id="lc258">    <span class="c1">// очистить список </span>
</div><div id="lc259">    <span class="kt">void</span> <span class="n">clear</span> <span class="p">(){</span>
</div><div id="lc260">      <span class="n">num</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc261">      <span class="n">first</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc262">      <span class="n">last</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc263">      <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</div><div id="lc264">        <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="k">new</span> <span class="n">Item</span><span class="p">;</span>
</div><div id="lc265">      <span class="p">}</span>
</div><div id="lc266">    <span class="p">}</span>
</div><div id="lc267">    
</div><div id="lc268">    <span class="c1">// получить количество </span>
</div><div id="lc269">    <span class="kt">int</span> <span class="n">count</span><span class="p">(){</span>
</div><div id="lc270">      <span class="k">return</span> <span class="n">num</span><span class="p">;</span>
</div><div id="lc271">    <span class="p">}</span>
</div><div id="lc272">    
</div><div id="lc273">    <span class="c1">// пустой ли список </span>
</div><div id="lc274">    <span class="kt">bool</span> <span class="n">isEmpty</span><span class="p">(){</span>
</div><div id="lc275">      <span class="k">return</span> <span class="o">!</span><span class="n">num</span><span class="p">;</span>
</div><div id="lc276">    <span class="p">}</span>
</div><div id="lc277">    
</div><div id="lc278">    <span class="c1">// получить индекс указаного элемента. Если: элемента нет, вернуть -1</span>
</div><div id="lc279">    <span class="kt">int</span> <span class="n">indexOf</span><span class="p">(</span><span class="n">T</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc280">      <span class="c1">//будем возвращать первый найденный индекс</span>
</div><div id="lc281">      
</div><div id="lc282">      <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">first</span><span class="p">;</span>
</div><div id="lc283">      <span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
</div><div id="lc284">      <span class="k">while</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">!=</span> <span class="n">NONE</span> <span class="o">&amp;&amp;</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span> <span class="o">!=</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc285">        <span class="n">i</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc286">        <span class="n">j</span><span class="o">++</span><span class="p">;</span>
</div><div id="lc287">      <span class="p">}</span>
</div><div id="lc288">      
</div><div id="lc289">      <span class="k">if</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span> <span class="o">==</span> <span class="n">value</span><span class="p">)</span>
</div><div id="lc290">        <span class="k">return</span> <span class="n">j</span><span class="p">;</span>
</div><div id="lc291">
</div><div id="lc292">      
</div><div id="lc293">      <span class="k">return</span> <span class="n">NONE</span><span class="p">;</span>
</div><div id="lc294">      
</div><div id="lc295">    <span class="p">}</span>
</div><div id="lc296">    
</div><div id="lc297">    <span class="c1">// проверить, принадлежит ли элемент списку</span>
</div><div id="lc298">    <span class="kt">bool</span> <span class="n">contains</span><span class="p">(</span><span class="n">T</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc299">      <span class="k">return</span> <span class="p">(</span><span class="kt">bool</span><span class="p">)(</span><span class="n">indexOf</span><span class="p">(</span><span class="n">value</span><span class="p">)</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc300">    <span class="p">}</span>
</div><div id="lc301">    
</div><div id="lc302">    <span class="c1">// удалить все вхождения элемента из списка</span>
</div><div id="lc303">    <span class="kt">void</span> <span class="n">remove</span><span class="p">(</span><span class="n">T</span> <span class="n">value</span><span class="p">){</span>
</div><div id="lc304">      
</div><div id="lc305">      <span class="k">while</span><span class="p">(</span><span class="kc">true</span><span class="p">){</span>
</div><div id="lc306">        <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">findItem</span><span class="p">(</span><span class="n">value</span><span class="p">);</span>
</div><div id="lc307">        
</div><div id="lc308">        <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">==</span><span class="n">NONE</span><span class="p">)</span>
</div><div id="lc309">          <span class="k">break</span><span class="p">;</span>
</div><div id="lc310">          
</div><div id="lc311">        <span class="n">removeItem</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc312">      <span class="p">}</span>
</div><div id="lc313">        
</div><div id="lc314">      
</div><div id="lc315">      
</div><div id="lc316">    <span class="p">}</span>
</div><div id="lc317">    
</div><div id="lc318">    <span class="c1">// удалить элемент с заданным индексом</span>
</div><div id="lc319">    <span class="kt">void</span> <span class="n">removeAt</span><span class="p">(</span><span class="kt">int</span> <span class="n">index</span><span class="p">){</span>
</div><div id="lc320">      <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">getItem</span><span class="p">(</span><span class="n">index</span><span class="p">);</span>
</div><div id="lc321">      <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">!=</span><span class="n">NONE</span><span class="p">)</span>
</div><div id="lc322">        <span class="n">removeItem</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc323">      
</div><div id="lc324">    <span class="p">}</span>
</div><div id="lc325">    
</div><div id="lc326">    
</div><div id="lc327">    
</div><div id="lc328">    <span class="kt">void</span> <span class="n">print_all</span><span class="p">(){</span>
</div><div id="lc329">      <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">first</span><span class="p">;</span>
</div><div id="lc330">      <span class="n">printf</span><span class="p">(</span><span class="s">&quot;</span><span class="se">\n\n</span><span class="s">  Count elements: %i </span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">num</span><span class="p">);</span>
</div><div id="lc331">      <span class="n">printf</span><span class="p">(</span><span class="s">&quot;  First index: %i </span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">first</span><span class="p">);</span>
</div><div id="lc332">      <span class="n">printf</span><span class="p">(</span><span class="s">&quot;  Last index: %i </span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">last</span><span class="p">);</span>
</div><div id="lc333">      <span class="n">printf</span><span class="p">(</span><span class="s">&quot;  index  |  prev  |  next  |  value  |  arr_key  </span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>
</div><div id="lc334">      <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">num</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
</div><div id="lc335">        <span class="c1">//if(i==NONE) break;</span>
</div><div id="lc336">        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;  %4i   |  %3i   |  %3i   |  %3i  |   %3i </span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">i</span><span class="p">,</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">prev</span><span class="p">,</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">,</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">,</span> <span class="n">i</span><span class="p">);</span>
</div><div id="lc337">        <span class="n">i</span><span class="o">=</span><span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc338">      <span class="p">}</span>
</div><div id="lc339">      
</div><div id="lc340">    <span class="p">}</span>
</div><div id="lc341">    
</div><div id="lc342">    
</div><div id="lc343">
</div><div id="lc344">
</div><div id="lc345">    <span class="c1">// скопировать список в массив (предполагается, что массив содержит достаточное количество элементов для выполнения операции) </span>
</div><div id="lc346">    <span class="kt">void</span> <span class="n">copyTo</span><span class="p">(</span><span class="n">T</span><span class="o">*</span> <span class="n">arr</span><span class="p">){</span>
</div><div id="lc347">      <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">first</span><span class="p">;</span>
</div><div id="lc348">      <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">num</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
</div><div id="lc349">        <span class="n">arr</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">;</span>
</div><div id="lc350">        <span class="n">i</span>      <span class="o">=</span> <span class="n">items</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
</div><div id="lc351">      <span class="p">}</span>
</div><div id="lc352">    <span class="p">}</span>
</div><div id="lc353">    
</div><div id="lc354">    <span class="c1">// получить итератор для обхода спискa</span>
</div><div id="lc355">    <span class="c1">//Iterator* getIterator(){</span>
</div><div id="lc356">      
</div><div id="lc357">    <span class="c1">//}</span>
</div><div id="lc358">
</div><div id="lc359">
</div><div id="lc360"><span class="p">};</span>
</div><div id="lc361">
</div><div id="lc362"><span class="kt">void</span> <span class="n">test</span><span class="p">(){</span>
</div><div id="lc363">    <span class="n">List</span><span class="o">*</span> <span class="n">list</span> <span class="o">=</span> <span class="k">new</span> <span class="n">List</span><span class="p">();</span>
</div><div id="lc364">    
</div><div id="lc365">    <span class="cm">/*тестирование на пустоту*/</span>
</div><div id="lc366">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">isEmpty</span><span class="p">()</span> <span class="p">)</span> <span class="p">;</span>
</div><div id="lc367">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">count</span><span class="p">()</span> <span class="o">==</span> <span class="mi">0</span><span class="p">);</span>
</div><div id="lc368">
</div><div id="lc369">    <span class="cm">/*тестирование на дополнение в конец, изменение числа элементов, наличие элементов */</span>
</div><div id="lc370">    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">10</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</div><div id="lc371">      <span class="n">list</span><span class="o">-&gt;</span><span class="n">add</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc372">      <span class="n">assert</span><span class="p">(</span><span class="o">!</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">isEmpty</span><span class="p">());</span>
</div><div id="lc373">      <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">get</span><span class="p">(</span><span class="n">i</span><span class="p">)</span><span class="o">==</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc374">      <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">count</span><span class="p">()</span> <span class="o">==</span> <span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc375">      
</div><div id="lc376">      <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">contains</span><span class="p">(</span><span class="n">i</span><span class="p">));</span>
</div><div id="lc377">      <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">indexOf</span><span class="p">(</span><span class="n">i</span><span class="p">)</span><span class="o">==</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc378">      
</div><div id="lc379">      <span class="n">assert</span><span class="p">(</span><span class="o">!</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">contains</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">));</span>
</div><div id="lc380">      <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">indexOf</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">==</span><span class="n">NONE</span><span class="p">);</span>
</div><div id="lc381">    <span class="p">}</span>
</div><div id="lc382">    
</div><div id="lc383">    
</div><div id="lc384">    <span class="cm">/*Тестирование удаления по значению*/</span>
</div><div id="lc385">    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">10</span><span class="p">;</span><span class="n">i</span><span class="o">+=</span><span class="mi">2</span><span class="p">){</span>
</div><div id="lc386">      <span class="n">list</span><span class="o">-&gt;</span><span class="n">remove</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc387">      <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">count</span><span class="p">()</span> <span class="o">==</span> <span class="mi">10</span><span class="o">-</span><span class="n">i</span><span class="o">/</span><span class="mi">2</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc388">      <span class="n">assert</span><span class="p">(</span><span class="o">!</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">contains</span><span class="p">(</span><span class="n">i</span><span class="p">));</span>
</div><div id="lc389">    <span class="p">}</span>
</div><div id="lc390">
</div><div id="lc391">    <span class="cm">/*Тестирование удаления по номеру элемента в списке*/</span>    
</div><div id="lc392">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">removeAt</span><span class="p">(</span><span class="mi">4</span><span class="p">);</span>
</div><div id="lc393">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">removeAt</span><span class="p">(</span><span class="mi">3</span><span class="p">);</span>
</div><div id="lc394">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">removeAt</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span>
</div><div id="lc395">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">removeAt</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc396">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">removeAt</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
</div><div id="lc397">
</div><div id="lc398">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">isEmpty</span><span class="p">())</span> <span class="p">;</span>
</div><div id="lc399">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">count</span><span class="p">()</span> <span class="o">==</span> <span class="mi">0</span><span class="p">);</span>
</div><div id="lc400">
</div><div id="lc401">    <span class="cm">/*Тестирование вставки в начало*/</span>
</div><div id="lc402">    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">10</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</div><div id="lc403">      <span class="n">list</span><span class="o">-&gt;</span><span class="n">insert</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc404">    <span class="p">}</span>
</div><div id="lc405">    
</div><div id="lc406">    <span class="cm">/*Тестирование очистки*/</span>
</div><div id="lc407">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">clear</span><span class="p">();</span>
</div><div id="lc408">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">isEmpty</span><span class="p">()</span> <span class="p">)</span> <span class="p">;</span>
</div><div id="lc409">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">count</span><span class="p">()</span> <span class="o">==</span> <span class="mi">0</span><span class="p">);</span>
</div><div id="lc410">    
</div><div id="lc411">    <span class="cm">/*Тестирование удаления одинаковых элементов*/</span>
</div><div id="lc412">    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">100</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
</div><div id="lc413">      <span class="n">list</span><span class="o">-&gt;</span><span class="n">add</span><span class="p">(</span><span class="mi">486</span><span class="p">);</span>
</div><div id="lc414">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">remove</span><span class="p">(</span><span class="mi">486</span><span class="p">);</span>
</div><div id="lc415">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">isEmpty</span><span class="p">()</span> <span class="p">)</span> <span class="p">;</span>
</div><div id="lc416">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">count</span><span class="p">()</span> <span class="o">==</span> <span class="mi">0</span><span class="p">);</span>
</div><div id="lc417">
</div><div id="lc418"><span class="cm">/*Тестирование изменения*/</span>
</div><div id="lc419">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">add</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc420">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">get</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="o">==</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc421">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">set</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">31337</span><span class="p">);</span>
</div><div id="lc422">    <span class="n">assert</span><span class="p">(</span><span class="n">list</span><span class="o">-&gt;</span><span class="n">get</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="o">==</span><span class="mi">31337</span><span class="p">);</span>
</div><div id="lc423">    
</div><div id="lc424">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">insert</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">);</span>
</div><div id="lc425">  <span class="n">list</span><span class="o">-&gt;</span><span class="n">print_all</span><span class="p">();</span>
</div><div id="lc426">
</div><div id="lc427">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">insert</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">);</span>
</div><div id="lc428">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">insert</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">);</span>
</div><div id="lc429">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">insert</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">4</span><span class="p">);</span>
</div><div id="lc430">    <span class="n">list</span><span class="o">-&gt;</span><span class="n">insert</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">5</span><span class="p">);</span>
</div><div id="lc431">
</div><div id="lc432">    
</div><div id="lc433">  <span class="n">list</span><span class="o">-&gt;</span><span class="n">print_all</span><span class="p">();</span>
</div><div id="lc434">
</div><div id="lc435">
</div><div id="lc436">
</div><div id="lc437">    <span class="c1">//assert(list-&gt;contains(1));</span>
</div><div id="lc438">    <span class="c1">//assert(!list-&gt;contains(568));</span>
</div><div id="lc439">
</div><div id="lc440"><span class="p">}</span>
</div><div id="lc441">
</div><div id="lc442">
</div><div id="lc443"><span class="kt">int</span> <span class="n">main</span><span class="p">(){</span>
</div><div id="lc444">  <span class="n">test</span><span class="p">();</span>
</div><div id="lc445">  <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
</div><div id="lc446">  <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%i&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">i</span><span class="p">);</span>
</div><div id="lc447">  <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
</div><div id="lc448"><span class="p">}</span>
</div></pre></div>
<p style="padding: 0; margin: 2em 0 1em 0; font-size: 0.8em; color: #666;"><span style="padding: 0 1em; background-color: #f5f5f5;"> Colored with <a style="color: #333" href="http://dumpz.org">dumpz.org</a></span></p>

Habrahabr.ru HTML Copy To Clipboarddone!

Use that HTML for publications on habrahabr.ru

<blockquote><code><font color="#BC7A00">#include&nbsp;&lt;cstdio&gt;
#include&nbsp;&lt;cassert&gt;
</font>

<font color="#008000"><strong>using</strong></font>&nbsp;<font color="#008000"><strong>namespace</strong></font>&nbsp;std;

<font color="#008000"><strong>typedef</strong></font>&nbsp;<font color="#B00040">int</font>&nbsp;T;
<font color="#008000"><strong>const</strong></font>&nbsp;<font color="#B00040">int</font>&nbsp;MAX<font color="#666666">=1000</font>;
<font color="#008000"><strong>const</strong></font>&nbsp;<font color="#B00040">int</font>&nbsp;NONE<font color="#666666">=-1</font>;

<font color="#008000"><strong>class</strong></font>&nbsp;<font color="#0000FF"><strong>List</strong></font>{
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>struct</strong></font>&nbsp;Item{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;prev;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;T&nbsp;value;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Item(<font color="#B00040">int</font>&nbsp;a_prev,&nbsp;<font color="#B00040">int</font>&nbsp;a_next,&nbsp;T&nbsp;a_value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prev<font color="#666666">=</font>a_prev;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next<font color="#666666">=</font>a_next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;value<font color="#666666">=</font>a_value;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Item(T&nbsp;a_value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prev<font color="#666666">=</font>NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next<font color="#666666">=</font>NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;value<font color="#666666">=</font>a_value;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Item(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prev<font color="#666666">=</font>NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next<font color="#666666">=</font>NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;value<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;};
&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;Item<font color="#666666">*</font>&nbsp;items[MAX];
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;first;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//индекс&nbsp;начального&nbsp;элемента
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;last;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//индекс&nbsp;конечного&nbsp;элемента
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;num;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//общее&nbsp;число&nbsp;элементов
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//ищем&nbsp;следующее&nbsp;свободное&nbsp;место&nbsp;в&nbsp;массиве
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;get_free_index(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(i<font color="#666666">=0</font>;i<font color="#666666">&lt;</font>MAX;i<font color="#666666">++</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(&nbsp;items[i]<font color="#666666">-&gt;</font>prev<font color="#666666">==</font>NONE&nbsp;<font color="#666666">&amp;&amp;</font>&nbsp;items[i]<font color="#666666">-&gt;</font>next<font color="#666666">==</font>NONE&nbsp;){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;i<font color="#666666">+</font>(num<font color="#666666">==1</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;NONE;

&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//вставляем&nbsp;значение&nbsp;перед&nbsp;выбранным&nbsp;элементом&nbsp;массива
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;insert_before(<font color="#B00040">int</font>&nbsp;i,&nbsp;T&nbsp;a_value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;free_index<font color="#666666">=</font>get_free_index();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">=</font>&nbsp;<font color="#008000"><strong>new</strong></font>&nbsp;Item(a_value);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]<font color="#666666">-&gt;</font>next&nbsp;<font color="#666666">=</font>&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]<font color="#666666">-&gt;</font>prev&nbsp;<font color="#666666">=</font>&nbsp;items[i]<font color="#666666">-&gt;</font>prev;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[i]<font color="#666666">-&gt;</font>prev&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">=</font>&nbsp;free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(i&nbsp;<font color="#666666">==</font>&nbsp;first)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first<font color="#666666">=</font>free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num<font color="#666666">++</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;insert_after(<font color="#B00040">int</font>&nbsp;i,&nbsp;T&nbsp;a_value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;free_index<font color="#666666">=</font>get_free_index();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">=</font>&nbsp;<font color="#008000"><strong>new</strong></font>&nbsp;Item(a_value);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]<font color="#666666">-&gt;</font>prev&nbsp;<font color="#666666">=</font>&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]<font color="#666666">-&gt;</font>next&nbsp;<font color="#666666">=</font>&nbsp;items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(items[i]<font color="#666666">-&gt;</font>next<font color="#666666">!=</font>NONE)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[items[i]<font color="#666666">-&gt;</font>next]<font color="#666666">-&gt;</font>prev<font color="#666666">=</font>free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[i]<font color="#666666">-&gt;</font>next&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">=</font>&nbsp;free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(i&nbsp;<font color="#666666">==</font>&nbsp;last)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last<font color="#666666">=</font>free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num<font color="#666666">++</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//ищем&nbsp;и&nbsp;возвращаем&nbsp;индекс&nbsp;элемента&nbsp;в&nbsp;массиве,&nbsp;чье&nbsp;значение&nbsp;равно&nbsp;аргументу
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;findItem(T&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(isEmpty())&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//будем&nbsp;возвращать&nbsp;первый&nbsp;найденный&nbsp;индекс
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i&nbsp;<font color="#666666">=</font>&nbsp;first;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>(items[i]<font color="#666666">-&gt;</font>next&nbsp;<font color="#666666">!=</font>&nbsp;NONE&nbsp;<font color="#666666">&amp;&amp;</font>&nbsp;items[i]<font color="#666666">-&gt;</font>value&nbsp;<font color="#666666">!=</font>&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(items[i]<font color="#666666">-&gt;</font>value&nbsp;<font color="#666666">==</font>&nbsp;value)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;i;

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;NONE;
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//получить&nbsp;индекс&nbsp;на&nbsp;элемент&nbsp;по&nbsp;номеру&nbsp;его&nbsp;в&nbsp;списке
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;getItem(<font color="#B00040">unsigned</font>&nbsp;<font color="#B00040">int</font>&nbsp;index){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(isEmpty())&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(index<font color="#666666">==0</font>)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;first;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(index<font color="#666666">==</font>(num<font color="#666666">-1</font>))&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;last;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(index<font color="#666666">&gt;=</font>num)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;NONE;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i;

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//определяем&nbsp;с&nbsp;какого&nbsp;конца&nbsp;легче&nbsp;двигатся
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(index<font color="#666666">&gt;=</font>num<font color="#666666">/2</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>last;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index<font color="#666666">=</font>num<font color="#666666">-</font>index<font color="#666666">-1</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>(index){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>prev;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index<font color="#666666">--</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>else</strong></font>{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>first;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>(index){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index<font color="#666666">--</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//удаляем&nbsp;элемент&nbsp;по&nbsp;его&nbsp;номеру&nbsp;в&nbsp;массиве
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;removeItem(<font color="#B00040">int</font>&nbsp;i){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(isEmpty())&nbsp;<font color="#008000"><strong>return</strong></font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(items[i]<font color="#666666">-&gt;</font>prev&nbsp;<font color="#666666">!=</font>&nbsp;NONE)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[items[i]<font color="#666666">-&gt;</font>prev]<font color="#666666">-&gt;</font>next<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(items[i]<font color="#666666">-&gt;</font>next&nbsp;<font color="#666666">!=</font>&nbsp;NONE)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[items[i]<font color="#666666">-&gt;</font>next]<font color="#666666">-&gt;</font>prev<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>prev;

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num<font color="#666666">--</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(i&nbsp;<font color="#666666">==</font>&nbsp;first){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(i&nbsp;<font color="#666666">==</font>&nbsp;last){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>prev;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[i]<font color="#666666">-&gt;</font>prev<font color="#666666">=</font>NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[i]<font color="#666666">-&gt;</font>next<font color="#666666">=</font>NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(<font color="#666666">!</font>num){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>public</strong></font><font color="#666666">:</font>
&nbsp;&nbsp;&nbsp;&nbsp;List&nbsp;(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;i<font color="#666666">=0</font>;i<font color="#666666">&lt;</font>MAX;i<font color="#666666">++</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[i]<font color="#666666">=</font><font color="#008000"><strong>new</strong></font>&nbsp;Item;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">~</font>List&nbsp;(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;добавить&nbsp;в&nbsp;конец
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;add(T&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;free_index<font color="#666666">=</font>get_free_index();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]&nbsp;<font color="#666666">=</font>&nbsp;<font color="#008000"><strong>new</strong></font>&nbsp;Item(value);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(<font color="#666666">!</font>num){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first&nbsp;<font color="#666666">=</font>&nbsp;free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last&nbsp;&nbsp;<font color="#666666">=</font>&nbsp;free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>else</strong></font>{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[free_index]<font color="#666666">-&gt;</font>prev&nbsp;<font color="#666666">=</font>&nbsp;last;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[last]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">-&gt;</font>next&nbsp;<font color="#666666">=</font>&nbsp;free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">=</font>&nbsp;free_index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num<font color="#666666">++</font>;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;добавить&nbsp;элемент&nbsp;в&nbsp;позицию&nbsp;с&nbsp;указанным&nbsp;индексом
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;insert(<font color="#B00040">unsigned</font>&nbsp;<font color="#B00040">int</font>&nbsp;index,&nbsp;T&nbsp;a_value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//будем&nbsp;добавлять&nbsp;перед&nbsp;этим&nbsp;эл-том
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//cначало&nbsp;досчитаем&nbsp;до&nbsp;этого&nbsp;элемента
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(<font color="#666666">!</font>index)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;insert_before(first,&nbsp;a_value);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//если&nbsp;индекс&nbsp;превышает&nbsp;число&nbsp;эл-тов&nbsp;то&nbsp;добавляем&nbsp;в&nbsp;конец
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(index<font color="#666666">&gt;</font>num)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;add(a_value);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//определяем&nbsp;с&nbsp;какого&nbsp;конца&nbsp;легче&nbsp;двигатся
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(index<font color="#666666">&gt;=</font>num<font color="#666666">/2</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>last;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index<font color="#666666">=</font>num<font color="#666666">-</font>index;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>(index){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>prev;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index<font color="#666666">--</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>else</strong></font>{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>first;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>(index){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index<font color="#666666">--</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(<font color="#BA2121">&quot;found&nbsp;%i</font><font color="#BB6622"><strong>\n</strong></font><font color="#BA2121">&quot;</font>,i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;insert_after(i,a_value);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;установить&nbsp;значение&nbsp;по&nbsp;индексу&nbsp;
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;set(<font color="#B00040">int</font>&nbsp;index,&nbsp;T&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i&nbsp;<font color="#666666">=</font>&nbsp;getItem(index);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[i]<font color="#666666">-&gt;</font>value<font color="#666666">=</font>value;
&nbsp;&nbsp;&nbsp;&nbsp;};
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;получить&nbsp;значение&nbsp;по&nbsp;индексу
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;T&nbsp;get(<font color="#B00040">int</font>&nbsp;index){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i<font color="#666666">=</font>getItem(index);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(i<font color="#666666">!=</font>NONE)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;items[i]<font color="#666666">-&gt;</font>value;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;NONE;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;очистить&nbsp;список&nbsp;
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;clear&nbsp;(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;i<font color="#666666">=0</font>;i<font color="#666666">&lt;</font>MAX;i<font color="#666666">++</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;items[i]<font color="#666666">=</font><font color="#008000"><strong>new</strong></font>&nbsp;Item;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;получить&nbsp;количество&nbsp;
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;count(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;num;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;пустой&nbsp;ли&nbsp;список&nbsp;
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">bool</font>&nbsp;isEmpty(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;<font color="#666666">!</font>num;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;получить&nbsp;индекс&nbsp;указаного&nbsp;элемента.&nbsp;Если:&nbsp;элемента&nbsp;нет,&nbsp;вернуть&nbsp;-1
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;indexOf(T&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//будем&nbsp;возвращать&nbsp;первый&nbsp;найденный&nbsp;индекс
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i<font color="#666666">=</font>first;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;j<font color="#666666">=0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>(items[i]<font color="#666666">-&gt;</font>next&nbsp;<font color="#666666">!=</font>&nbsp;NONE&nbsp;<font color="#666666">&amp;&amp;</font>&nbsp;items[i]<font color="#666666">-&gt;</font>value&nbsp;<font color="#666666">!=</font>&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j<font color="#666666">++</font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(items[i]<font color="#666666">-&gt;</font>value&nbsp;<font color="#666666">==</font>&nbsp;value)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;j;

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;NONE;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;проверить,&nbsp;принадлежит&nbsp;ли&nbsp;элемент&nbsp;списку
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">bool</font>&nbsp;contains(T&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;(<font color="#B00040">bool</font>)(indexOf(value)<font color="#666666">+1</font>);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;удалить&nbsp;все&nbsp;вхождения&nbsp;элемента&nbsp;из&nbsp;списка
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;remove(T&nbsp;value){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>(<font color="#008000"><strong>true</strong></font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i<font color="#666666">=</font>findItem(value);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(i<font color="#666666">==</font>NONE)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>break</strong></font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;removeItem(i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;удалить&nbsp;элемент&nbsp;с&nbsp;заданным&nbsp;индексом
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;removeAt(<font color="#B00040">int</font>&nbsp;index){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i<font color="#666666">=</font>getItem(index);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>(i<font color="#666666">!=</font>NONE)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;removeItem(i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;print_all(){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i<font color="#666666">=</font>first;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(<font color="#BA2121">&quot;</font><font color="#BB6622"><strong>\n\n</strong></font><font color="#BA2121">&nbsp;&nbsp;Count&nbsp;elements:&nbsp;%i&nbsp;</font><font color="#BB6622"><strong>\n</strong></font><font color="#BA2121">&quot;</font>,&nbsp;num);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(<font color="#BA2121">&quot;&nbsp;&nbsp;First&nbsp;index:&nbsp;%i&nbsp;</font><font color="#BB6622"><strong>\n</strong></font><font color="#BA2121">&quot;</font>,first);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(<font color="#BA2121">&quot;&nbsp;&nbsp;Last&nbsp;index:&nbsp;%i&nbsp;</font><font color="#BB6622"><strong>\n</strong></font><font color="#BA2121">&quot;</font>,last);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(<font color="#BA2121">&quot;&nbsp;&nbsp;index&nbsp;&nbsp;|&nbsp;&nbsp;prev&nbsp;&nbsp;|&nbsp;&nbsp;next&nbsp;&nbsp;|&nbsp;&nbsp;value&nbsp;&nbsp;|&nbsp;&nbsp;arr_key&nbsp;&nbsp;</font><font color="#BB6622"><strong>\n</strong></font><font color="#BA2121">&quot;</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;j<font color="#666666">=0</font>;j<font color="#666666">&lt;</font>num;j<font color="#666666">++</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//if(i==NONE)&nbsp;break;
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(<font color="#BA2121">&quot;&nbsp;&nbsp;%4i&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;%3i&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;%3i&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;%3i&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;%3i&nbsp;</font><font color="#BB6622"><strong>\n</strong></font><font color="#BA2121">&quot;</font>,i,items[i]<font color="#666666">-&gt;</font>prev,items[i]<font color="#666666">-&gt;</font>next,&nbsp;items[i]<font color="#666666">-&gt;</font>value,&nbsp;i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i<font color="#666666">=</font>items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;скопировать&nbsp;список&nbsp;в&nbsp;массив&nbsp;(предполагается,&nbsp;что&nbsp;массив&nbsp;содержит&nbsp;достаточное&nbsp;количество&nbsp;элементов&nbsp;для&nbsp;выполнения&nbsp;операции)&nbsp;
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;copyTo(T<font color="#666666">*</font>&nbsp;arr){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i<font color="#666666">=</font>first;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;j<font color="#666666">=0</font>;j<font color="#666666">&lt;</font>num;j<font color="#666666">++</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr[j]&nbsp;<font color="#666666">=</font>&nbsp;items[i]<font color="#666666">-&gt;</font>value;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">=</font>&nbsp;items[i]<font color="#666666">-&gt;</font>next;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//&nbsp;получить&nbsp;итератор&nbsp;для&nbsp;обхода&nbsp;спискa
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//Iterator*&nbsp;getIterator(){
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//}
</em></font>

};

<font color="#B00040">void</font>&nbsp;test(){
&nbsp;&nbsp;&nbsp;&nbsp;List<font color="#666666">*</font>&nbsp;list&nbsp;<font color="#666666">=</font>&nbsp;<font color="#008000"><strong>new</strong></font>&nbsp;List();
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>/*тестирование&nbsp;на&nbsp;пустоту*/</em></font>
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>isEmpty()&nbsp;)&nbsp;;
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>count()&nbsp;<font color="#666666">==</font>&nbsp;<font color="#666666">0</font>);

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>/*тестирование&nbsp;на&nbsp;дополнение&nbsp;в&nbsp;конец,&nbsp;изменение&nbsp;числа&nbsp;элементов,&nbsp;наличие&nbsp;элементов&nbsp;*/</em></font>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;i<font color="#666666">=0</font>;i<font color="#666666">&lt;10</font>;i<font color="#666666">++</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>add(i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(<font color="#666666">!</font>list<font color="#666666">-&gt;</font>isEmpty());
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>get(i)<font color="#666666">==</font>i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>count()&nbsp;<font color="#666666">==</font>&nbsp;i<font color="#666666">+1</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>contains(i));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>indexOf(i)<font color="#666666">==</font>i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(<font color="#666666">!</font>list<font color="#666666">-&gt;</font>contains(i<font color="#666666">+1</font>));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>indexOf(i<font color="#666666">+1</font>)<font color="#666666">==</font>NONE);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>/*Тестирование&nbsp;удаления&nbsp;по&nbsp;значению*/</em></font>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;i<font color="#666666">=0</font>;i<font color="#666666">&lt;10</font>;i<font color="#666666">+=2</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>remove(i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>count()&nbsp;<font color="#666666">==</font>&nbsp;<font color="#666666">10-</font>i<font color="#666666">/2-1</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert(<font color="#666666">!</font>list<font color="#666666">-&gt;</font>contains(i));
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>/*Тестирование&nbsp;удаления&nbsp;по&nbsp;номеру&nbsp;элемента&nbsp;в&nbsp;списке*/</em></font>&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>removeAt(<font color="#666666">4</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>removeAt(<font color="#666666">3</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>removeAt(<font color="#666666">2</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>removeAt(<font color="#666666">1</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>removeAt(<font color="#666666">0</font>);

&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>isEmpty())&nbsp;;
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>count()&nbsp;<font color="#666666">==</font>&nbsp;<font color="#666666">0</font>);

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>/*Тестирование&nbsp;вставки&nbsp;в&nbsp;начало*/</em></font>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;i<font color="#666666">=1</font>;i<font color="#666666">&lt;10</font>;i<font color="#666666">++</font>){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>insert(<font color="#666666">0</font>,i);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>/*Тестирование&nbsp;очистки*/</em></font>
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>clear();
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>isEmpty()&nbsp;)&nbsp;;
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>count()&nbsp;<font color="#666666">==</font>&nbsp;<font color="#666666">0</font>);
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>/*Тестирование&nbsp;удаления&nbsp;одинаковых&nbsp;элементов*/</em></font>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>(<font color="#B00040">int</font>&nbsp;i<font color="#666666">=0</font>;i<font color="#666666">&lt;100</font>;i<font color="#666666">++</font>)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>add(<font color="#666666">486</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>remove(<font color="#666666">486</font>);
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>isEmpty()&nbsp;)&nbsp;;
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>count()&nbsp;<font color="#666666">==</font>&nbsp;<font color="#666666">0</font>);

<font color="#408080"><em>/*Тестирование&nbsp;изменения*/</em></font>
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>add(<font color="#666666">1</font>);
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>get(<font color="#666666">0</font>)<font color="#666666">==1</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>set(<font color="#666666">0</font>,<font color="#666666">31337</font>);
&nbsp;&nbsp;&nbsp;&nbsp;assert(list<font color="#666666">-&gt;</font>get(<font color="#666666">0</font>)<font color="#666666">==31337</font>);
&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>insert(<font color="#666666">0</font>,<font color="#666666">1</font>);
&nbsp;&nbsp;list<font color="#666666">-&gt;</font>print_all();

&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>insert(<font color="#666666">1</font>,<font color="#666666">2</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>insert(<font color="#666666">1</font>,<font color="#666666">3</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>insert(<font color="#666666">1</font>,<font color="#666666">4</font>);
&nbsp;&nbsp;&nbsp;&nbsp;list<font color="#666666">-&gt;</font>insert(<font color="#666666">1</font>,<font color="#666666">5</font>);

&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;list<font color="#666666">-&gt;</font>print_all();

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//assert(list-&gt;contains(1));
</em></font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#408080"><em>//assert(!list-&gt;contains(568));
</em></font>
}

<font color="#B00040">int</font>&nbsp;main(){
&nbsp;&nbsp;test();
&nbsp;&nbsp;<font color="#B00040">int</font>&nbsp;i;
&nbsp;&nbsp;scanf(<font color="#BA2121">&quot;%i&quot;</font>,<font color="#666666">&amp;</font>i);
&nbsp;&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;<font color="#666666">0</font>;
}
</code></blockquote><p><font color="gray">Colored with <a href="http://dumpz.org">dumpz.org</a></p>