linked list only showing first and last nodes

[Grea]

M linked list class is only showing the first and last elements of my list. I think the issue has to be in the pushBack,or the << overload in the linked-list impl. Or in the insert function in the iterator implementation. If someone could point me in the right direction that would be extremely helpful.

  /*
 * iterator.h
 * Declaration of Iterator class (used by LinkedList)
 */
 
#ifndef ITERATOR_H
#define ITERATOR_H

#include "node.h"

// Inform C++ compiler that there is a class named LinkedList<Element>
// (this is called a "forward declaration")
template <typename Element>
class LinkedList;

template <typename Element>
class Iterator
{
private:
    LinkedList<Element> &list;
    int index;
    Node<Element> *prev, *next;
    
public:
    // Default constructor (index = 0, prev = next = null)
    Iterator(LinkedList<Element> &parentList);
    
    // Getters
    int getIndex() const;
    bool hasNext() const;
    bool hasPrevious() const;
    
    // Element access
    Element & getNext();
    const Element & getNext() const;
    Element & getPrevious();
    const Element & getPrevious() const;
    
    // List operations
    void insert(const Element &e);
    Element removeNext();
    Element removePrevious();
    
    // Iteration
    void moveToNext();
    void moveToPrevious();
    
    // Allow a LinkedList<Element> to access private variables
    friend class LinkedList<Element>;
};

#include "iterator-impl.cpp"

#endif // ifndef ITERATOR_H

***************************

/*
 *iterator-impld.cpp
 *implementation of iterator class
 */
#include <stdexcept>
using std::range_error;
 
 
 
template <typename Element>
Iterator<Element>::Iterator(LinkedList<Element> &parentList):
      list(parentList),
      index(0),
      prev(NULL),
      next(NULL)
{}

template <typename Element>
bool Iterator<Element>::hasNext() const
{
     return (next != NULL);
}



template <typename Element>
Element & Iterator<Element>::getNext()
{
    return next->value;
}

template <typename Element>
const Element & Iterator<Element>::getNext() const
{
    return next->vlaue;
}

template <typename Element>
Element & Iterator<Element>::getPrevious()
{
        return prev->vale;
}

template <typename Element>
const Element & Iterator<Element>::getPrevious() const
{
        return prev->vale;
}

template <typename Element>
void Iterator<Element>::insert(const Element &e)
{
   
   Node<Element> *newNode = new Node<Element>(e);
   
   newNode->prev = prev;
   newNode->next = next;
   
   if(list.first ==NULL)
   list.first = list.last = newNode;
   
   else if(prev != NULL)
   prev->next = newNode;
   
   else 
   next->prev = newNode;
   
  
   
   next = newNode;
   
   ++list.size;
}

template <typename Element>
void Iterator<Element>::moveToNext()
{
     if(!hasNext())
        throw range_error("no next node in iteration");
        
     prev = next;
     next = next->next;
     
}


******************************************************

/*
 * linked-list.h
 * Declaration of linked list class
 */

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
using std::ostream;

#include "node.h"
#include "iterator.h"

template <typename Element>
class LinkedList
{
private:
    Node<Element> *first, *last;
    int size;
    
public:
    // Default constructor
    LinkedList();
    // Destructor
    ~LinkedList();
    
    // Accessors
    int getSize() const;
    
    // Element access
    Element & operator[](int index);
    const Element & operator[](int index) const;
    
    // Insertion operation
    void insert(const Element &e, int index);
    
    // Removal operation
    Element remove(int index);
    
    // Deque operations
    // Adds an element to the front, i.e. inserts at index 0
    void pushFront(const Element &e);
    
    // Adds an element to the back, i.e. inserts at maximum index
    void pushBack(const Element &e);
    
    // Removes an element from the front, i.e. removes index 0
    Element removeFront();
    
    // Removes an element from the back, i.e. removes maximum index
    Element removeBack();
    
    // Iteration
    // Returns an iterator starting before the front (beginning) of the list
    Iterator<Element> frontIterator();
    
    // Returns an iterator starting after the back (end) of the list
    Iterator<Element> backIterator();
    
    // Returns an iterator starting before the specified index
    Iterator<Element> seek(int index);  
    
    // Returns an iterator starting before the first occurrence of the specified
    // value; if not found, the return iterator will be the same as the result
    // of calling backIterator().
    Iterator<Element> find(const Element &e);
    
    friend class Iterator<Element>;
    
    template <typename Element2>
    friend ostream & operator<<(ostream &out, LinkedList<Element2> &list);
};

template <typename Element>
ostream & operator<<(ostream &out,  LinkedList<Element> &list);

#include "linked-list-impl.cpp"

#endif // ifndef LINKED_LIST_H

*******************************************

/*
 *
 *
 *implementation of linkedlist class
 */




template <typename Element>
LinkedList<Element>::LinkedList():
   first(NULL), last(NULL),
   size(0)
{}

template <typename Element>
LinkedList<Element>::~LinkedList()
{
    Node<Element> *node = first;
    while(node != NULL)
    {
         // A-> b is the same as (*A).b
         //since node is a pointer not a node itself we need to
         //dereference it to get to its next variable
        Node<Element> *next = node->next;
        delete node;
        node = next;           
    }   
    
    first = last = NULL;
                                 
}
template <typename Element>
void LinkedList<Element>::pushBack(const Element &e)
{
     Iterator<Element> back = backIterator();  
     back.insert(e); 
     
}

template <typename Element>
Iterator<Element> LinkedList<Element>::frontIterator()
{
    Iterator<Element> iter(*this);
    iter.index = 0;
    iter.prev = NULL;
    iter.next = first;  
    return iter;              
}

template <typename Element>
Iterator<Element> LinkedList<Element>::backIterator()
{
    Iterator<Element> iter(*this);
    iter.index = size;
    iter.prev = last;
    iter.next = NULL;  
    
    return iter;               
}

template <typename Element>
ostream & operator<<(ostream &out, LinkedList<Element> &list)
{
    out << "{ ";
    Iterator<Element> front = list.frontIterator();
    while (front.hasNext())
    {
        out << front.getNext() << " ";  
        front.moveToNext();  
                                   
    }    
    
    out << " }";
    
    return out;
}

********************************************************

#include <cstdlib>
#include <iostream>

using namespace std;

#include "linked-list.h"

int main(int argc, char *argv[])
{
    // Create a linked list of ints
    LinkedList<int> list;
    
    // Add a few numbers to the list
    list.pushBack(5);
    list.pushBack(10);
    list.pushBack(15);
    list.pushBack(20);
    
    // Print out the result
    cout << list << endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

**********************************

/*
 * node.h
 * Declaration of Node class (used by LinkedList)
 */

#ifndef NODE_H
#define NODE_H

// Inform C++ compiler that there is a class named LinkedList<Element>
// (this is called a "forward declaration")
template <typename Element>
class LinkedList;

template <typename Element>
class Iterator;

template <typename Element>
class Node
{
private:
    Element value;
    Node<Element> *prev, *next;
    
public:
    Node(const Element &value);
    
    // Determiness whether there is a next node, i.e. whether the "next" link is
    // non-null
    bool hasNext() const;
    
    // Determines whether there is a previous node, i.e. whether the "prev" link
    // is non-null
    bool hasPrevious() const;
    
    // Allow a LinkedList<Element> to access private variables
    friend class LinkedList<Element>;
    friend class Iterator<Element>;
};

#include "node-impl.cpp"

#endif // ifndef NODE_H

******************************************

/*
 *implementation of node class
 */
 #include "node.h"
 
template <typename Element>
Node<Element>::Node(const Element &initialvalue):
   value(initialvalue)
{}
    
template <typename Element>
bool Node<Element>::hasNext() const
{
  return(next!= NULL);     
}
    
template <typename Element>
bool Node<Element>::hasPrevious() const
{
      return(prev != NULL);
}

[coder777]

on line 285 you set next to NULL. On line 122/123 you do not take this into account.

[Catfish666]

Grea, you seem to miss the point of iterators.

Iterators are an interface for the container, so that you can use the same algorithm for different containers.
For instance let's say you want to write a "universal" print_contents() function.

If you write it as a function template, like...

template <typename Iterator>
void print_contents(Iterator b, Iterator e)
{
    for (; b != e; ++b)
        std::cout << *b << ' ';

    std::cout << std::endl;
}

... then you can use it with any container that supplies C++ style begin and one-past-end iterators.

So iterators provide an external interface. Instead you make things harder for yourself by overusing iterators, internally.

In addition, I noticed some typos which seem to go undetected (because of templates?) and a fishy practice of include'ing .cpp files -- at least give them another extension, such as .inc so that other programmers and IDE's not get confused.

template <typename Element>
const Element & Iterator<Element>::getNext() const
{
    return next->vlaue;
}

template <typename Element>
Element & Iterator<Element>::getPrevious()
{
        return prev->vale;
}

template <typename Element>
const Element & Iterator<Element>::getPrevious() const
{
        return prev->vale;
}

Then your Iterator::insert() function, which in my opinion has no right to exist in the first place, seems to only care about the previous and next nodes, ignoring the current node. Since perhaps this is a misunderstanding on my part, I won't comment further.

template <typename Element>
void Iterator<Element>::insert(const Element &e)
{
   
   Node<Element> *newNode = new Node<Element>(e);
   
   newNode->prev = prev;
   newNode->next = next;
   
   if(list.first ==NULL)
   list.first = list.last = newNode;
   
   else if(prev != NULL)
   prev->next = newNode;
   
   else 
   next->prev = newNode;
   
  
   
   next = newNode;
   
   ++list.size;
}

Hopefully other members can help you more than I, because for me the code is too difficult to follow.

[Grea]

Sorry about the difficulty to follow, each class has to have its own header file and implementation for my assignment. even after fixing the values i cant get it to work correctly. Its only displaying the first an last elements, I think it is replacing the last node instead of inserting one after the current last.

[Grea]

just figured it out had to change the insert function to this


Node<Element> *newNode = new Node<Element>(e);

newNode->prev = prev;
newNode->next = next;

if (prev != NULL)
prev->next = newNode;
if (next != NULL)
next->prev = newNode;



if (prev == list.last)

list.last = newNode;
if (next == list.first)

list.first = newNode;

next = newNode;

++list.size;