Linkedlist Template with strings...

Question

karolik 0 Newbie Poster

14 Years Ago

So I made a template...I tried declaring a string linkedlist like so...

LinkedList<string> str;

Then i called the function insertLast to insert a string called hello..like so...

str.insertLast("hello")

Then it gives me null pointer error...I cannot see how there can be a null pointer...help would be appreciated..Here is the insertLast function. The trouble comes on the newNode=new ListNode<T> line...apparently it doesn't like that...and i have no idea why..yes i did use using namespace std;

Here is the function insertLast

void LinkedList<T>::insertLast(T newobj)//O(n)
{
	
  ListNode<T> *newNode;
  newNode=new ListNode<T>;  
  cout<<newobj;
  newNode->obj=newobj;
  newNode->next=NULL; 
  ListNode<T> *current;
   
  if(head==NULL){
	 head=newNode;
	 tail=newNode;
  }
  else{
	  current=head;
	  while(current->next)
		current=current->next;
		
	  current->next=newNode;
	  tail=newNode;
  }

 
}

Here is entire template code

//LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "RuntimeException.h"
using namespace std;
class LinkedList;

class ListNode {
 private:
   char obj;
   ListNode *next;
   friend class LinkedList;
   
 public:
   ListNode(char e = 0, ListNode *n = NULL) : obj(e), next(n) { }
   char getElem() const { return obj; }
   ListNode * getNext() const { return next; }
};

class LinkedList {
 private:
   ListNode *head, *tail;
   
 public:
   // user-defined exceptions
   class EmptyLinkedListException : public RuntimeException {
    public:
     EmptyLinkedListException() : RuntimeException("Empty linked list") {}
   };
   class InvalidPointerException : public RuntimeException {
    public:
     InvalidPointerException() : RuntimeException("Attempt to use null pointer") {}
   };   
   
   LinkedList() {head=NULL; tail=NULL; } // default constructor
   ~LinkedList() { //O(n)
	ListNode *current = head;
	ListNode *nextnode;
	while(current!=NULL){
		nextnode=current->next;
		delete current;
		current=nextnode;
     
	}
   head=NULL;
   } // destructor
   LinkedList(const LinkedList& ll) {//O(n)
    head=NULL;
	tail=NULL;
	ListNode *current =ll.getHead();
	this->insertLast(current->getElem());
	while(current->next!=NULL){
		current=current->next;
		insertLast(current->getElem());
	
	}
    
	
   
   
   } // copy constructor
   LinkedList & operator=(const LinkedList & ll); // assignment operator
     
   // query function
   int size() const;
   bool isEmpty() const { 
	if (head==NULL) return true; 
	else return false;
   }
   // accessor functions
   char first() const throw(EmptyLinkedListException);
   ListNode *getHead() const { return head; }
   ListNode *getTail() const { return tail; }

   // update functions
   void insertFirst(char newobj);
   char removeFirst() throw(EmptyLinkedListException);
   void insertLast(char newobj);
   void insertAfter(char newobj, ListNode *node) throw(InvalidPointerException);
   char remove(ListNode *node) throw(InvalidPointerException);
   void removeAll();
   
   friend ostream & operator<<(ostream& out, const LinkedList &ll); //overload <<
};


#endif

c++

Edited 14 Years Ago by karolik because: n/a

4 Contributors
10 Replies
170 Views
16 Hours Discussion Span
Latest Post 14 Years Ago Latest Post by mattbond

All 10 Replies

mattjbond 54 Junior Poster

14 Years Ago

So I made a template...I tried declaring a string linkedlist like so...

LinkedList<string> str;

Then i called the function insertLast to insert a string called hello..like so...

str.insertLast("hello")

Then it gives me null pointer error...I cannot see how there can be a null pointer...help would be appreciated..Here is the insertLast function. The trouble comes on the newNode=new ListNode<T> line...apparently it doesn't like that...and i have no idea why..yes i did use using namespace std;

Here is the function insertLast

void LinkedList<T>::insertLast(T newobj)//O(n)
{
	
  ListNode<T> *newNode;
  newNode=new ListNode<T>;  
  cout<<newobj;
  newNode->obj=newobj;
  newNode->next=NULL; 
  ListNode<T> *current;
   
  if(head==NULL){
	 head=newNode;
	 tail=newNode;
  }
  else{
	  current=head;
	  while(current->next)
		current=current->next;
		
	  current->next=newNode;
	  tail=newNode;
  }

 
}

Here is entire template code

//LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "RuntimeException.h"
using namespace std;
class LinkedList;

class ListNode {
 private:
   char obj;
   ListNode *next;
   friend class LinkedList;
   
 public:
   ListNode(char e = 0, ListNode *n = NULL) : obj(e), next(n) { }
   char getElem() const { return obj; }
   ListNode * getNext() const { return next; }
};

class LinkedList {
 private:
   ListNode *head, *tail;
   
 public:
   // user-defined exceptions
   class EmptyLinkedListException : public RuntimeException {
    public:
     EmptyLinkedListException() : RuntimeException("Empty linked list") {}
   };
   class InvalidPointerException : public RuntimeException {
    public:
     InvalidPointerException() : RuntimeException("Attempt to use null pointer") {}
   };   
   
   LinkedList() {head=NULL; tail=NULL; } // default constructor
   ~LinkedList() { //O(n)
	ListNode *current = head;
	ListNode *nextnode;
	while(current!=NULL){
		nextnode=current->next;
		delete current;
		current=nextnode;
     
	}
   head=NULL;
   } // destructor
   LinkedList(const LinkedList& ll) {//O(n)
    head=NULL;
	tail=NULL;
	ListNode *current =ll.getHead();
	this->insertLast(current->getElem());
	while(current->next!=NULL){
		current=current->next;
		insertLast(current->getElem());
	
	}
    
	
   
   
   } // copy constructor
   LinkedList & operator=(const LinkedList & ll); // assignment operator
     
   // query function
   int size() const;
   bool isEmpty() const { 
	if (head==NULL) return true; 
	else return false;
   }
   // accessor functions
   char first() const throw(EmptyLinkedListException);
   ListNode *getHead() const { return head; }
   ListNode *getTail() const { return tail; }

   // update functions
   void insertFirst(char newobj);
   char removeFirst() throw(EmptyLinkedListException);
   void insertLast(char newobj);
   void insertAfter(char newobj, ListNode *node) throw(InvalidPointerException);
   char remove(ListNode *node) throw(InvalidPointerException);
   void removeAll();
   
   friend ostream & operator<<(ostream& out, const LinkedList &ll); //overload <<
};


#endif

When posting it is useful to provide a compilable example. Cut out all the extraneous sections and try to post an example of the code which displays the issue. We aren't all clever buggers who can infer problems just by looking at source code.

mattjbond 54 Junior Poster

14 Years Ago

Your problem is in the definition of your template functions and a lack of understanding as to how it should be done. You want your linked list to be able to store nodes holding objects of any type hence your templated function. To achieve this you need to provide more templated items.

Your ListNode class should be rewritten as a class template eg.

template<typename T>
class ListNode
{
private:
...
   T obj; // node can now handle generic type T
...
}

In your insertLast function you have added the template parameter to the wrong object.

void LinkedList::insertLast(T newobj)
{
   ListNode<T> *newNode; // list node is not the generic type in
                                           // itself but it stores a copy of the
                                           // generic type T
...
}

Instead your templated function should pass a generic type and then store this in the ListNode
eg.

template<typename T>
void LinkedList::insertLast(T newobj)
{
   ListNode *newNode; // list node is not the generic type in
   newNode=new ListNode;  
   newNode->obj=newobj;
... 
}

This should get you going for now but is susspect it it not quite what you want. Anyway compilable code here...

//LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

class LinkedList;

class ListNode {
private:
   char obj;
   ListNode *next;
   friend class LinkedList;

public:
   ListNode(char e = 0, ListNode *n = 0) : obj(e) , next(n) { }
   char getElem() const { return obj; }
   ListNode * getNext() const { return next; }
};


class LinkedList {
private:
   ListNode *head, *tail;

public:
   
   LinkedList() {head=0; tail=0; } // default constructor
   ~LinkedList() { //O(n)
      ListNode *current = head;
      ListNode *nextnode;
      while(current!=0){
         nextnode=current->next;
         delete current;
         current=nextnode;

      }
      head=0;
   } // destructor
   LinkedList(const LinkedList& ll) {//O(n)
      head=0;
      tail=0;
      ListNode *current =ll.getHead();
      this->insertLast(current->getElem());
      while(current->next!=0){
         current=current->next;
         insertLast(current->getElem());

      }




   } // copy constructor
   LinkedList & operator=(const LinkedList & ll); // assignment operator

   // query function
   int size() const;
   bool isEmpty() const { 
      if (head==0) return true; 
      else return false;
   }
   // accessor functions
   char first() const;
   ListNode *getHead() const { return head; }
   ListNode *getTail() const { return tail; }

   // update functions
   void insertFirst(char newobj);
   char removeFirst();
   template<typename T>
   void insertLast(T newobj);
   void insertAfter(char newobj, ListNode *node);
   char remove(ListNode *node);
   void removeAll();

};


#endif

// main to exercise
#include "LinkedList.h"


template<typename T>
void LinkedList::insertLast(T newobj)//O(n)
{

   ListNode *newNode;
   newNode=new ListNode;  
   newNode->obj=newobj;
   newNode->next=0; 
   ListNode *current;

   if(head==0){
      head=newNode;
      tail=newNode;
   }
   else{
      current=head;
      while(current->next)
         current=current->next;

      current->next=newNode;
      tail=newNode;
   }
}


int main()
{

   LinkedList  ll;

   ll.insertLast('C');

   return 0;
}

mattjbond 54 Junior Poster

14 Years Ago

Bit more info.

I suspect that the intended usage for your linked list would be something like

LinkedList<char> char_list;
char_list.insertLast( 'C' );

To achieve this you need to think about how to make your list node generic. Something like...

template<typename T>
class ListNode
{
private:
   T obj;
....
};

Now the list node can store an object of any type, although you need to define the rest of the template class correctly too. I leave that to you. Having done this you now need to address you LinkedList class ans parameterize this so that it can use the new generic nodes.

Something like...

template<typename T>
class LinkedList {
private:
   ListNode<T> *head, *tail;

public:
...
   void insertFirst(T newobj);
...
};

Again making sure you refer to the parameterized types correctly through the class definition. Again I'll leave that to you to try for yourself.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

mrnutty 761 Senior Poster · Answer 1 · 2010-03-04T21:31:12+00:00

This function :

void LinkedList<T>::insertLast(T newobj)//O(n)
{
	
  ListNode<T> *newNode;
  newNode=new ListNode<T>;  
  cout<<newobj;
  newNode->obj=newobj;
  newNode->next=NULL; 
  ListNode<T> *current;
   
  if(head==NULL){
	 head=newNode;
	 tail=newNode;
  }
  else{
	  current=head;
	  while(current->next)
		current=current->next;
		
	  current->next=newNode;
	  tail=newNode;
  }

 
}

should only take O(1) and not O(n), since you are storing a tail pointer.
The tail pointer should always point to the last element, so instead of this part of the code :

else{
	  current=head;
	  while(current->next)
		current=current->next;
		
	  current->next=newNode;
	  tail=newNode;
  }

it should utilize the tail pointer by doing something like this :

else{
          tail.next = newNode;
          tail = tail.next;
  }

see how much simpler that is. The tail pointer should be the last element at all time, so to add one to the end, you just add it to tail.next, so now instead of tail.next being null, it has another node.
Then you move the tail pointer forward, so its still at the end of the list.

karolik 0 Newbie Poster · Answer 2 · 2010-03-04T21:39:06+00:00

Whoops..Posted the wrong source code...here is the correct one that is actually templated.

// LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "RuntimeException.h"
#include <iostream>
#include <string>
using namespace std;
template<typename T> class LinkedList;

template<typename T>
std::ostream& operator<<(std::ostream&, const LinkedList<T>&);


template<typename T>
class ListNode {

  private:
   T obj;
   ListNode *next;
   friend class LinkedList<T>;
   
 public:
   ListNode(T e = 0, ListNode *n = NULL) : obj(e), next(n) { }
   T getElem() const { return obj; }
   ListNode * getNext() const { return next; }
  
};

template<typename T>
class LinkedList {
 private:
	 ListNode<T> *head, *tail;
   /* declare member variables here */
   /* declare utility functions here */
   
 public:
   // user-defined exceptions
   class EmptyLinkedListException : public RuntimeException {
    public:
     EmptyLinkedListException() : RuntimeException("Empty linked list") {}
   };
   class InvalidPointerException : public RuntimeException {
    public:
     InvalidPointerException() : RuntimeException("Attempt to use null pointer") {}
   };   
   
	LinkedList<T>();
	~LinkedList<T>();
     
   LinkedList(const LinkedList<T>& ll); // copy constructor
   LinkedList<T> & operator=(const LinkedList<T> & ll); // assignment operator
   
   // query function
   int size() const;
   bool isEmpty() const { 
	if (head==NULL) return true; 
	else return false;
   }
   // accessor functions
   T first() const throw(EmptyLinkedListException);
   ListNode<T> *getHead() const { return head; }
   ListNode<T> *getTail() const { return tail; }

   // update functions
   void insertFirst(T newobj);
   T removeFirst() throw(EmptyLinkedListException);
   void insertLast(T newobj);
   void insertAfter(T newobj, ListNode<T> *node) throw(InvalidPointerException);
   T remove(ListNode<T> *node) throw(InvalidPointerException);
   void removeAll();
   
   friend std::ostream& operator<< <>(std::ostream& out, const LinkedList<T>& ll); //overload <<
};
template<typename T>
LinkedList<T>::LinkedList(){head=NULL; tail=NULL; } 
template<typename T>
LinkedList<T>::~LinkedList() { //O(n)
	ListNode<T> *current = head;
	ListNode<T> *nextnode;
	while(current!=NULL){
		nextnode=current->next;
		delete current;
		current=nextnode;
     
	}
}
template<typename T>
LinkedList<T>::LinkedList(const LinkedList<T>& ll) // copy constructor
{
   head=NULL;
	tail=NULL;
	ListNode<T> *current =ll.getHead();
	this->insertLast(current->getElem());
	while(current->next!=NULL){
		current=current->next;
		insertLast(current->getElem());
	
	}
}

template<typename T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& ll) // assignment operator
{
  if(this->getHead()!=NULL)
	this->~LinkedList();
	
	
	ListNode<T> *current=ll.getHead();
 
	
	
	this->insertLast(current->getElem());
	while(current->next!=NULL){
	current=current->next;
	this->insertLast(current->getElem());

	}

	
	

  return *this;
}
template<typename T>

int LinkedList<T>::size() const {//O(n)
	int count =0;
	if(head==NULL)
	count=0;
	else{
	ListNode<T> *current=this->getHead();
	while(current!=NULL){
		count++;
	    current=current->next;
	
	}
	}
  return count;
}
template<typename T>
T LinkedList<T>::first() const throw(EmptyLinkedListException)
{

	if(head==NULL)	 
	 throw EmptyLinkedListException();
	
	else
	 return this->getHead()->getElem();

  return 0;
}

template<typename T>
void LinkedList<T>::insertFirst(T newobj)
{
  
  ListNode<T> *newNode;
  newNode= new ListNode<T>;
  newNode->obj=newobj;
  newNode->next=NULL; 
  ListNode<T> *current;
   
  if(head==NULL)
	 head=newNode;
  else {
	  current=head;
	  head=newNode;
      newNode->next=current;
	  
  }
}
template<typename T>
void LinkedList<T>::insertLast(T newobj)//O(n)
{
	
  ListNode<T> *newNode;
  newNode=new ListNode<T>;  
  cout<<newobj;
  newNode->obj=newobj;
  newNode->next=NULL; 
  ListNode<T> *current;
   
  if(head==NULL){
	 head=newNode;
	 tail=newNode;
  }
  else{
	  current=head;
	  while(current->next)
		current=current->next;
		
	  current->next=newNode;
	  tail=newNode;
  }

 
}
template<typename T>
void LinkedList<T>::insertAfter(T newobj, ListNode<T> *node)// O(n)
    throw(InvalidPointerException)
{	 
	
	ListNode<T> *newNode;
	newNode= new ListNode<T>;
	newNode->obj=newobj;
	newNode->next=NULL;
    ListNode<T> *current=head;
	ListNode<T> *backnode;
	if(node==NULL)
		throw InvalidPointerException();
	if(node==head){
		current=head->next;
		head->next=newNode;
		newNode->next=current;
	}
	else{


	while(current!=NULL&&backnode!=node){
			backnode=current;
			current=current->next;
		}
	if(current==NULL)
	tail=newNode;
	
	backnode->next=newNode;
	newNode->next=current;
	
	}

  /* BONUS QUESTION: complete this function
   * This function inserts a new node with element 'newobj' 
   * after the node pointed by the pointer 'node'.
   * Modify the head and tail pointers when needed.
   * If the pointer "node" is NULL, throw an InvalidPointerException
   */
}
template<typename T>
T LinkedList<T>::removeFirst() throw(EmptyLinkedListException)
{
  /* Complete this function;
   * If the linked list is empty, throw an EmptyLinkedListException
   */
 T temp;	
  ListNode<T> *current;
  if(head==NULL)
 	throw EmptyLinkedListException();
  temp=head->getElem();
  current=head->next;	
  delete head;
  head=current;

  return temp;
}
template<typename T>
T LinkedList<T>::remove(ListNode<T> *node) //O(n)
    throw(InvalidPointerException)
{
   if(node==NULL)
		throw InvalidPointerException();
	
	ListNode<T> *current=head;
	ListNode<T> *backnode;
	if(head==NULL)
	  throw InvalidPointerException();
  
	if(head==node)
	 removeFirst();
	
	else
  {
	while(current!=NULL && current!=node)
	{
		backnode=current;
		current=current->next;


	}
	if (current->next==NULL){
		tail=backnode;
		
	}
	if(current!=NULL){
		backnode->next=current->next;
		delete current;
	}
	
  
	

  

	

  return 0;
	}
}
template<typename T>
void LinkedList<T>::removeAll()//O(n)
{
  /* Complete this function;
   * This function removes all the nodes in the linked list
    */
	head=NULL;
	this->~LinkedList();

}
template<typename T>
std::ostream& operator<<(std::ostream & out, const LinkedList<T>& ll) //overload <<
{
 ListNode<T> *current=ll.getHead();
	
	
	if(current==NULL)
	out<<"empty";
	else{

	while(current!=NULL){
		
		out<<current->getElem()<<" ";
		current=current->getNext();
		

	}
	}
    
	return out;
}

#endif

mattjbond 54 Junior Poster · Answer 3 · 2010-03-04T21:48:42+00:00

I notice that in several places in this code you explicitly call your class destructor. e.g.

void LinkedList<T>::removeAll()//O(n)
{
  /* Complete this function;
   * This function removes all the nodes in the linked list
    */
	head=NULL;
	this->~LinkedList();

This is not a good idea. I'll leave you to find out why.

In fact to be nice i'll point you towards this...

http://www.parashift.com/c++-faq-lite/dtors.html

for some reasons why.

karolik 0 Newbie Poster · Answer 4 · 2010-03-04T21:57:01+00:00

I notice that in several places in this code you explicitly call your class destructor. e.g.
void LinkedList<T>::removeAll()//O(n)
{
  /* Complete this function;
   * This function removes all the nodes in the linked list
    */
	head=NULL;
	this->~LinkedList();
This is not a good idea. I'll leave you to find out why.
In fact to be nice i'll point you towards this...
http://www.parashift.com/c++-faq-lite/dtors.html
for some reasons why.

Alright...thanks...I'll check it out..Btw...i still have the null pointer exception error when i make a linkedlist of strings...

mattjbond 54 Junior Poster · Answer 5 · 2010-03-04T22:02:03+00:00

Alright...thanks...I'll check it out..Btw...i still have the null pointer exception error when i make a linkedlist of strings...

really? worked ok in the fixed version I sorted earlier. got to go somewhere now but will try to look later. Try to post a cut down version of the code with nothing more that enough in it to demonstrate the problem.

this is the version I fixed up for meself earlier.

//LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template<typename T>
class LinkedList;

template<typename T>
class ListNode {
private:
   T obj;
   ListNode<T> *next;
   friend class LinkedList<T>;

public:
   ListNode(ListNode<T> *n = 0) : next(n) { }
   T getElem() const { return obj; }
   ListNode<T> * getNext() const { return next; }
};

template<typename T>
class LinkedList {
private:
   ListNode<T> *head, *tail;

public:
   
   LinkedList() {head=0; tail=0; } // default constructor
   ~LinkedList() { //O(n)
      ListNode<T> *current = head;
      ListNode<T> *nextnode;
      while(current!=0){
         nextnode=current->next;
         delete current;
         current=nextnode;

      }
      head=0;
   } // destructor
   LinkedList(const LinkedList& ll) {//O(n)
      head=0;
      tail=0;
      ListNode<T> *current =ll.getHead();
      this->insertLast(current->getElem());
      while(current->next!=0){
         current=current->next;
         insertLast(current->getElem());

      }




   } // copy constructor
   LinkedList & operator=(const LinkedList & ll); // assignment operator

   // query function
   int size() const;
   bool isEmpty() const { 
      if (head==0) return true; 
      else return false;
   }
   // accessor functions
   char first() const;
   ListNode<T> *getHead() const { return head; }
   ListNode<T> *getTail() const { return tail; }

   // update functions
   void insertFirst(T newobj);
   char removeFirst();
   void insertLast(T newobj);
   void insertAfter(T newobj, ListNode<T> *node);
   char remove(ListNode<T> *node);
   void removeAll();

};


#endif

// main to exercise
#include "LinkedList.h"
#include <string>

template<typename T>
void LinkedList<T>::insertLast(T newobj)//O(n)
{

   ListNode<T> *newNode;
   newNode=new ListNode<T>;  
   newNode->obj=newobj;
   newNode->next=0; 
   ListNode<T> *current;

   if(head==0){
      head=newNode;
      tail=newNode;
   }
   else{
      current=head;
      while(current->next)
         current=current->next;

      current->next=newNode;
      tail=newNode;
   }
}


int main()
{

   LinkedList<std::string>  ll;

   ll.insertLast("Hello");

   return 0;
}

karolik 0 Newbie Poster · Answer 6 · 2010-03-04T22:19:10+00:00

Ah, figured out the problem looking at your constructor..

ListNode(ListNode *n = NULL) : next(n) { }

Mine was...

ListNode(T e = 0, ListNode *n = NULL) : obj(e), next(n) { }

Apparently it didn't like T e=0...apparently you can't set strings equal to zero? But isn't obj in listnode never initialized? But it works..

mattbond 0 Newbie Poster · Answer 7 · 2010-03-04T23:47:22+00:00

ListNode(T e = 0, ListNode *n = NULL) : obj(e), next(n) { }

This constructor has an initializer list
: obj(e), next(n)
which carries out initialization of the variable before the body of the constructor is entered.

Linkedlist Template with strings...

Recommended Answers Collapse Answers

All 10 Replies

Recommended Answers