SHARE
TWEET

Linked List Tutorial C++

sp2danny Jun 5th, 2015 (edited) 474 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     This is a small tutorial showing how to design a linked list in C++ using a sentry node.
  2.     It's intended for novices that have tried to create a linked list implementation themselves,
  3.     and discovered that there are a lot of special cases needed to handle empty list, first node,
  4.     last node, etc.
  5.      
  6.     Let's first show intended use, since it affects design:
  7.      
  8.     Here is a small example creating a list, filling it up with values, and printing them
  9.      
  10.         #include <iostream>
  11.         #include "LinkedList.h++"
  12.        
  13.         int main()
  14.         {
  15.             List<int> lst;
  16.            
  17.             // add items
  18.             lst.PushBack( 3 );
  19.             lst.PushBack( 5 );
  20.             lst.PushBack( 7 );
  21.            
  22.             // iterate and print
  23.             auto iter = lst.Begin();
  24.             while( iter != lst.End() )
  25.             {
  26.                 std::cout << iter->data << " ";
  27.                 iter = iter->next;
  28.             }
  29.             std::cout << std::endl;
  30.         }
  31.      
  32.     A few things to note:
  33.      
  34.     1. The implementation is a template, this is not as complicated to write as
  35.        you may think.
  36.     2. The use of the concept 'iterator'. As the tutorial unfold, it will become
  37.        clear why this is advantageous.
  38.      
  39.      
  40.     Let's take a look in the first few lines of LinkedList.h++
  41.     For brevity, all error checking is omitted, and const considerations largely ignored
  42.      
  43.         #pragma once
  44.        
  45.         #include <cstddef>
  46.        
  47.         template<typename T>
  48.         class List
  49.         {
  50.             struct Node
  51.             {
  52.                 Node* next;
  53.                 Node* prev;
  54.                 T data;
  55.             };
  56.        
  57.             struct Sentry // since T might not be default-constructible, we need a separate Sentry type
  58.             {
  59.                 Node* next;
  60.                 Node* prev;
  61.             };
  62.      
  63.             Node* sentry;  // this will be our sentry node. it will be of type Sentry, but 'poses' as a Node
  64.             std::size_t size;
  65.        
  66.             // helper function to link 2 nodes
  67.             void Link( Node* n1, Node* n2 )
  68.             {
  69.                 n1->next = n2;
  70.                 n2->prev = n1;
  71.             }
  72.        
  73.         public:
  74.            
  75.             typedef Node* Iterator;
  76.      
  77.      
  78.     You may notice that this is a doubly linked list, this is very useful even if you don't
  79.     iterate backwards, it simplifies node insertion, node deletion, and last item access.
  80.      
  81.     Second, there is no head item, but rather a sentry node. In this implementation, the list
  82.     is never really empty, it always contains at least one item (the dummy 'sentry' node).
  83.     This removes the need for ALL special cases, as you will see.
  84.      
  85.     Effectively, sentry->next functions as a head pointer, and sentry->prev as a tail pointer.
  86.      
  87.      
  88.     Let's have a look at a few more lines:
  89.      
  90.             // this creates a new empty list
  91.             List()
  92.             {
  93.                 sentry = (Node*) new Sentry;  // make a new sentry node
  94.                 Link( sentry, sentry );       // that points to itself
  95.                 size = 0;
  96.             }
  97.            
  98.             // returns true if list is empty
  99.             bool Empty() const
  100.             {
  101.                 return sentry->next == sentry;  // when sentry points to itself, the list is empty
  102.             }
  103.        
  104.             // returns size of list
  105.             std::size_t Size() const
  106.             {
  107.                 return size;
  108.             }
  109.      
  110.     Please note that here is no copy-constructor, assignment operator etc. The List class is not
  111.     really complete without those, but the point of this tutorial is to demonstrate benefits of
  112.     using a sentry node, so I cut away some 'clutter'
  113.      
  114.      
  115.     Let's see how Begin and End are implemented:
  116.      
  117.             // pointer to first item of list, or end if empty
  118.             Iterator Begin()
  119.             {
  120.                 return sentry->next;  // no special-cases needed when using sentry
  121.             }
  122.            
  123.             // pointer to end (one past last)
  124.             Iterator End()
  125.             {
  126.                 return sentry;
  127.             }
  128.      
  129.     As you can see, the sentry node also doubles as the 'one past last' marker.
  130.      
  131.     If you are unfamiliar with the 'iterator' concept, the begin marker points to the first item,
  132.     and the end marker points one past last item. This can be used for arrays too, like this:
  133.      
  134.         constexpr int SZ = 15;
  135.         int arr[SZ];
  136.         int* iter = arr;
  137.         int* end = arr+SZ;
  138.         while( iter != end )
  139.         {
  140.             (*iter) = 3; // set value for all items to 3
  141.             ++iter;
  142.         }
  143.      
  144.     With an array, the iterator type is an item pointer, item access is done with '*', and
  145.     iterating to next item with '++'
  146.      
  147.     With our list implementation, the iterator type is a Node*, item access is done with
  148.     '->data' and iterating to next item is done with 'i=i->next'
  149.      
  150.     With macros, these could be handled the same way. Then you could change mid-project if
  151.     you are using an array or a list, without having to rewrite your algorithms.
  152.      
  153.     It could look something like this:
  154.      
  155.         // for array
  156.         #define NXT(i) ++i
  157.         #define ACC(i) *i
  158.         // for list
  159.         #define NXT(i) i=i->next
  160.         #define ACC(i) i->data
  161.      
  162.     But it's beyond the scope of this tutorial, so let's not delve further into that.
  163.      
  164.     My apologies for the use of macros, but if you are capable of parsing the replacement
  165.     templates, you don't qualify as a novice, or need this tutorial.
  166.      
  167.     Note that iterators in the standard library's std::list, std::vector etc mimic
  168.     C-style array iterators with '++' and '*'
  169.      
  170.      
  171.     Lets see how adding items to the list is implemented:
  172.      
  173.             // this inserts new data before 'here'
  174.             Iterator Insert( Iterator here, const T& data )
  175.             {
  176.                 Iterator item = new Node{0,0,data};  // create new item. use T's copy-constructor
  177.                 Link( here->prev, item );            // link in new node. item comes before here,
  178.                 Link( item, here );                  // so in-between `here->prevĀ“ and `hereĀ“
  179.                 size += 1;                           // update size
  180.                 return item;
  181.             }
  182.            
  183.             // adds new item last
  184.             void PushBack( const T& d )
  185.             {
  186.                 Insert( End(), d );
  187.             }
  188.            
  189.             // adds new item first
  190.             void PushFront( const T& d )
  191.             {
  192.                 Insert( Begin(), d );
  193.             }
  194.      
  195.     As you can see, the Insert function adds the new item *before* its marker node,
  196.     this way you can easily insert nodes everywhere, even first and last,
  197.     as the PushBack and PushFront functions demonstrate.
  198.      
  199.      
  200.     Let's have a look at the erase implementation:
  201.      
  202.             // erase one item. erasing end is harmless
  203.             Iterator Erase( Iterator here )
  204.             {
  205.                 if( here == sentry ) return sentry;  // check for end
  206.                 Iterator nxt = here->next;           // save next item for return value
  207.                 Link( here->prev, here->next );      // unlink item. no special cases needed when using sentry
  208.                 delete here;                         // delete item. this will call T's destructor
  209.                 size -= 1;                           // update size
  210.                 return nxt;
  211.             }
  212.      
  213.     A curious thing is that Erase returns the next item. This is for a reason:
  214.      
  215.     This is how you iterate a list, while deleting some items that fulfills some criteria:
  216.      
  217.         auto iter = lst.Begin();
  218.         while( iter != lst.End() )
  219.         {
  220.             DoSomething( iter->data );
  221.             if( SomeCriteria( iter->data ) )
  222.                 iter = lst.Erase( iter ); // this is why Erase returns an iterator
  223.             else
  224.                 iter = iter->next;
  225.         }
  226.      
  227.     Also note that erasing end is NOT harmless on STL containers.
  228.      
  229.      
  230.     A List is sometimes used as a stack. We have Push functions, let's have Pop too:
  231.      
  232.             // remove last item. don't call on empty list
  233.             void PopBack()
  234.             {
  235.                 Erase( sentry->prev );  // sentry->prev points to last item
  236.             }
  237.            
  238.             // remove first item. don't call on empty list
  239.             void PopFront()
  240.             {
  241.                 Erase( sentry->next );  // sentry->next points to first item
  242.             }
  243.      
  244.     I chose to let the Pop functions return void, since T may not be lightweight
  245.      
  246.      
  247.     We are nearing the end. Lets have a way to clean up after us.
  248.      
  249.             // erase all items
  250.             void Clear()
  251.             {
  252.                 Iterator cur = sentry->next;
  253.                 while( cur != sentry )
  254.                 {
  255.                     Iterator nxt = cur->next; // we have to save the next pointer, since deletion invalidates access
  256.                     delete cur;               // this will call T's destructor
  257.                     cur = nxt;
  258.                 }
  259.                 size = 0;
  260.                 // note that the list is left in a usable (but empty) state
  261.                 // while(!Empty()) Erase(Begin());  // would have been simpler
  262.             }
  263.            
  264.             // this destroys the list itself
  265.             ~List()
  266.             {
  267.                 Clear();
  268.                 delete (Sentry*) sentry;
  269.             }
  270.      
  271.      
  272.     A few more convenience functions:
  273.      
  274.             // returns last item by reference
  275.             T& Back()
  276.             {
  277.                 return sentry->prev->data;
  278.             }
  279.            
  280.             // returns first item by reference
  281.             T& Front()
  282.             {
  283.                 return sentry->next->data;
  284.             }
  285.            
  286.             // non-range-checked index access
  287.             T& operator [] ( std::size_t idx )
  288.             {
  289.                 Iterator iter = Begin();
  290.                 while( idx-- ) iter = iter->next;  // this loop is why index access in O(n)
  291.                 return iter->data;
  292.             }
  293.      
  294.      
  295.     Now lastly an integrity check for debugging purpose:
  296.      
  297.             bool IntegrityCheck()
  298.             {
  299.                 if( ! sentry ) return false;                // not even allocated?
  300.                 Iterator prev = sentry;
  301.                 Iterator curr = sentry->next;
  302.                 std::size_t sz = 0;
  303.                 while( curr != sentry )
  304.                 {
  305.                     if( ! curr ) return false;              // there should be no null pointers in the list
  306.                     if( sz >= size ) return false;          // list is longer than what size suggest
  307.                     ++sz;
  308.                     if( curr->prev != prev ) return false;  // back-pointer dont point to previous item
  309.                     prev = curr;
  310.                     curr = curr->next;
  311.                 }
  312.                 if( sz != size ) return false;              // list is shorter than what size suggest
  313.                 if( sentry->prev != prev ) return false;    // 'tail' pointer don't point to last item
  314.                
  315.                 return true;
  316.             }
  317.        
  318.         };
  319.      
  320.     That concludes the content of LinkedList.h++, lets have a complete example:
  321.      
  322.         #include <iostream>
  323.         #include <cassert>
  324.         #include <string>
  325.        
  326.         #include "LinkedList.h++"
  327.        
  328.         // lets create an adaptor, so we can use range-based for loops
  329.         template<typename T> struct ll_iter {
  330.             typename List<T>::Iterator i;
  331.             ll_iter& operator++() { i=i->next; return *this; }
  332.             T& operator*() { return i->data; }
  333.             bool operator!=(ll_iter other) { return i != other.i; }
  334.         };
  335.         template<typename T> ll_iter<T> begin ( List<T>& l ) { return {l.Begin()}; }
  336.         template<typename T> ll_iter<T> end   ( List<T>& l ) { return {l.End()};   }
  337.        
  338.         using namespace std;
  339.        
  340.         string TestList()
  341.         {
  342.             List<int> list;
  343.        
  344.             assert( list.IntegrityCheck() );
  345.        
  346.             list.PushBack( 1 );
  347.             list.PushBack( 2 );
  348.             list.PushBack( 3 );
  349.             list.PushBack( 4 );
  350.        
  351.             // list should be 1, 2, 3, 4
  352.        
  353.             assert( list.IntegrityCheck() );
  354.        
  355.             auto iter = list.Begin();
  356.             while( iter != list.End() )
  357.             {
  358.                 iter->data *= 3; // triple values to 3, 6, 9, 12
  359.                 if( iter->data % 2 )
  360.                     iter = list.Erase( iter ); // remove odd, now 6, 12
  361.                 else
  362.                     iter = iter->next;
  363.             }
  364.        
  365.             assert( list.IntegrityCheck() );
  366.        
  367.             string str;
  368.        
  369.             for( auto&& val : list )
  370.             {
  371.                 str += to_string( val ) + " ";
  372.             }
  373.        
  374.             return str; // this should return "6 12 "
  375.         }
  376.        
  377.         int main() { cout << TestList() << endl; }
  378.        
  379.        
  380.      
  381.     For reference, the whole content of LinkedList.h++ can be accessed at http://pastebin.com/U2CSvtr7
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top