C++

Forum

 
Doubly Linked List Back Pointer

lin0524 (2)
I have to implement this doubly linked list. The list needs a front pointer pointing to the first valid element and a back pointer pointing to the last valid element.

My problem with this code is with the last few lines when I have to implement T& back. Front was easy to do because it's the same as the begin iterator but i can't figure out how to do back. What I have right now is not working. I think my problem is the way i defined 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
 
#ifndef List_dllist_h
#define List_dllist_h
#include <iterator>

template <class T>
class DList
{
struct Node
{
    Node(const T& x,Node* y = 0):m_data(x),m_next(y),m_prev(y){}
    T m_data;
    Node* m_next;
    Node* m_prev;
};

Node* m_head;
Node* m_back;

public:

class iterator
{
    Node* m_rep;
public:
    friend class DList;

    inline iterator(Node* x=0):m_rep(x){}
    inline iterator(const iterator& x):m_rep(x.m_rep) {}
    inline iterator& operator=(const iterator& x)
    {
        m_rep=x.m_rep; return *this;
    }
    inline iterator& operator++()
    {
        m_rep = m_rep->m_next; return *this;
    }
    inline iterator operator++(int)
    {
        iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
    }
     inline iterator& operator--()
        {
            m_rep= m_rep->m_prev; return *this;
        }
        inline iterator operator--(int)
        {
            iterator tmp(*this); m_rep= m_rep->m_prev; return tmp;
        }
    inline T& operator*() const { return m_rep->m_data; }
    inline Node* operator->() const { return m_rep; }
    inline bool operator==(const iterator& x) const
    {
        return m_rep == x.m_rep;
    }
    inline bool operator!=(const iterator& x) const
    {
        return m_rep != x.m_rep;
    }

   };


DList() : m_head(0), m_back(0) {}
~DList() { clear(); }


inline T& front() { return *begin(); }
inline const T& front() const { return *begin(); }


inline T& back() { return *--end(); }
inline const T& back() const { return *--end(); }

inline iterator begin() { return iterator(m_head); }
inline iterator end() { return iterator(m_back +1); }



};
#endif
Last edited on
kbw (9488)
It depends on what you've used DList::m_back. I would have thought that it should point to the last entry (as you need to traverse forward and backward), in which case your implementation of back() should work. But I don't know what you've done with it.
Topic archived. No new replies allowed.