need help for implement a doubly linked list
Dec 27, 2016 at 3:08pm UTC
Here I'm trying to implement a List-container with its iterator. I'm not sure how I represent the empty list and the list-end so that an iterator iterates correctly backward from list-end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
/*
* Implementation of a doubly linked list.
*/
#include <initializer_list>
namespace test
{
//======= class Link ===============
// represents a node of the list
template <typename Elem>
struct Link
{
public :
Link * prev; // previous Link
Link * succ; // subsequent Link
Elem val; // element
};
//======= class List ===============
template <typename Elem>
class List
{
private :
Link<Elem> * first; // first node
Link<Elem> * last; // last node
long long int m_size;
public :
class iterator; // nested class
// this seems wrong implemented
List()
: first{ nullptr }
{
first = last;
}
List( std::initializer_list<Elem> izl )
{
for (auto iter = izl.begin(); iter != izl.end(); ++ iter)
{
push_back( * iter );
}
}
long long int size() const { return m_size; }
iterator begin() { return iterator( first); }
// Here seems something wrong
iterator end() { return iterator( last->succ); }
iterator insert( iterator p, const Elem& v)
{
// not implemented
}
iterator erase( iterator p)
{
// not implemented
} // curly brace added at edit
void push_back( const Elem & v)
{
// not implemented
}
void push_front( const Elem & v)
{
// not implemented
}
void pop_back()
{
if (!first) { return ; } // if empty List
// not implemented
}
void pop_front()
{
if (!first) { return ; } // if empty List
//not implemented
}
Elem& front() { return first->val; }
Elem& back() { return last->val; }
};
//======= class List<Elem>::iterator =======
template <typename Elem>
class List<Elem>::iterator
{
private :
Link<Elem> * curr; // current Link
public :
// constructor
iterator( Link<Elem> * p)
: curr{ p }
{}
// forward iteration
iterator& operator ++ ()
{
curr = curr->succ;
return * this ;
}
// backward iteration
iterator& operator -- ()
{
curr = curr->prev;
return * this ;
}
// element access
Elem& operator * ()
{
return curr->val;
}
bool operator == ( const iterator& other) const { return curr == other.curr; }
bool operator != ( const iterator& other) const { return curr != other.curr; }
};
} // namespace test
//====== testing the List =====
#include <iostream>
#include <string>
int main ()
{
test::List<std::string> list = { "banana" , "orange" , "apple" , "cherry" };
for (test::List<std::string>::iterator iter = list.begin(); iter != list.end(); ++iter)
{
std::cout << *iter << ' ' ;
}
}
*edited , line 70
Last edited on Dec 27, 2016 at 4:44pm UTC
Dec 27, 2016 at 4:35pm UTC
I've seen now, at line 70 was missed a closing curly brace, sorry for that. And then i don't know how i could tackle the forward declaration of class iterator.
Last edited on Dec 27, 2016 at 4:51pm UTC
Topic archived. No new replies allowed.