Linked List

recursive method to print linked list backwards

Page 1 of 1

11 Replies - 4414 Views - Last Post: 29 October 2009 - 02:23 AM Rate Topic: -----

#1 hidden_within  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 07-April 09

Linked List

Post icon  Posted 28 October 2009 - 11:37 AM

Anyone have any suggestion on writing a method to print a linked list backwards?
Is This A Good Question/Topic? 0
  • +

Replies To: Linked List

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Linked List

Posted 28 October 2009 - 11:39 AM

Is it doubly linked?
Was This Post Helpful? 0
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1954
  • View blog
  • Posts: 4,053
  • Joined: 11-December 07

Re: Linked List

Posted 28 October 2009 - 11:53 AM

If it's singly linked call the next iteration before you print the current item. That way you work your way to the end of the list and then print out each node as you go back along the stack. The end result will be your list printed out in reverse order.
Was This Post Helpful? 0
  • +
  • -

#4 hidden_within  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 07-April 09

Re: Linked List

Posted 28 October 2009 - 12:04 PM

its a single linked list. I dont quite understand

Quote

call the next iteration before you print the current item. That way you work your way to the end of the list and then print out each node as you go back along the stack

Was This Post Helpful? 0
  • +
  • -

#5 hidden_within  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 07-April 09

Re: Linked List

Posted 28 October 2009 - 12:43 PM

This is what I have so far but I keep getting an error "Cannot find symbol error"

Will this code work to print the linked list backwards?


import java.util.NoSuchElementException;

public abstract class LinkedListClass<T> implements LinkedListADT<T>
{
	protected class LinkedListNode<T> implements Cloneable
	{
		public T info;
		public LinkedListNode<T> link;

		   //Default constructor
		   //Postcondition: info = null; link = null;
		public LinkedListNode()
		{
			info = null;
			link = null;
		}

		   //Constructor with parameters
		   //This method sets info pointing to the object to
		   //which elem points to and link is set to point to
		   //the object to which ptr points to.
		   //Postcondition:  info = elem; link = ptr;
		public LinkedListNode(T elem, LinkedListNode<T> ptr)
		{
			info = elem;
			link = ptr;
		}

		   //Returns a copy of objects data in store.
		   //This method clones only the references stored in
		   //the node. The objects that the nodes point to
		   //are not cloned.
		public Object clone()
		{
			LinkedListNode<T> copy = null;

			try
			{
				copy = (LinkedListNode<T>) super.clone();

			}
			catch (CloneNotSupportedException e)
			{
				return null;
			}

			return copy;
		}

		   //Method to return the info as a string.
		   //Postcondition: info as a String object is
		   //			   returned.
		public String toString()
		{
			return info.toString();
		}
	} //end class LinkedListNode


	public class LinkedListIterator<T>
	{
		protected LinkedListNode<T> current;  //variable to
											  //point to the
											  //current node in
											  //list
		protected LinkedListNode<T> previous; //variable to
											  //point to the
											  //node before the
											  //current node

		   //Default constructor
		   //Sets current to point to the first node in the
		   //list and sets previous to null.
		   //Postcondition: current = first; previous = null;
		public LinkedListIterator()
		{
			current = (LinkedListNode<T>) first;
			previous = null;
		}

		   //Method to reset the iterator to the first node
		   //in the list.
		   //Postcondition: current = first; previous = null;
		public void reset()
		{
			current = (LinkedListNode<T>) first;
			previous = null;
		}

		   //Method to return a reference of the info of the
		   //current node in the list and to advance iterator
		   //to the next node.
		   //Postcondition: previous = current;
		   //			   current = current.link;
		   //			   A refrence of the current node
		   //			   is returned.
		public T next()
		{
			if (!hasNext())
				throw new NoSuchElementException();

			LinkedListNode<T> temp = current;

			previous = current;
			current = current.link;

			return temp.info;
		}

			//Method to determine whether there is a next
			//element in the list.
			//Postcondition: Returns true if there is a next
			//			   node in the list; otherwise
			//			   returns false.
		public boolean hasNext()
		{
			return (current != null);
		}

		   //Method to remove the node currently pointed to
		   //by the iterator.
		   //Postcondition: If iterator is not null, then the
		   //			   node that the iterator points to
		   //			   is removed. Otherwise the method
		   //			   throws NoSuchElementException.
		public void remove()
		{
			if (current == null)
				throw new NoSuchElementException();

			if (current == first)
			{
				first = first.link;
				current = (LinkedListNode<T>) first;
				previous = null;

				if (first == null)
					last = null;
			}
			else
			{
				previous.link = current.link;

				if (current == last)
				{
					last = first;
					while (last.link != null)
						last = last.link;
				}

				current = current.link;
			}

			count--;
		}

		   //Method to return the info as a string.
		   //Postcondition: info as a String object is returned.
		public String toString()
		{
			return current.info.toString();
		}

	} //end class LinkedListIterator


	   //Instance variables of the class LinkedListClass
	protected LinkedListNode<T> first; //variable to store the
									   //address of the first
									   //node of the list
	protected LinkedListNode<T> last;  //variable to store the
									   //address of the last
									   //node of the list
	protected int count;  //variable to store the number of
						  //nodes in the list

	   //Default constructor
	   //Initializes the list to an empty state.
	   //Postcondition: first = null, last = null,
	   //			   count = 0
	public LinkedListClass()
	{
		first = null;
		last = null;
		count = 0;
	}

	   //Method to determine whether the list is empty.
	   //Postcondition: Returns true if the list is empty;
	   //			   false otherwise.
	public boolean isEmptyList()
	{
		return (first == null);
	}

	   //Method to initialize the list to an empty state.
	   //Postcondition: first = null, last = null,
	   //			   count = 0
	public void initializeList()
	{
		first = null;
		last = null;
		count = 0;
	}

	   //Method to output the data contained in each node.
	public void print()
	{
		LinkedListNode<T> current; //variable to traverse
								   //the list

		current = first;	//set current so that it points to
							//the first node
		while (current != null) //while more data to print
		{
			System.out.print(current.info + " ");
			current = current.link;
		}
	}//end print
	 
	   
	  public void printReverse(LinkedListNode<T> head)
   		{
   			if (head == null)
					System.out.print(" ");
				  if (head.next == null)
   				System.out.print(head.info);
   			else
   				System.out.print(printReverse(head.next) + "," + head.info);
		  }

	   //Method to return the number of nodes in the list.
	   //Postcondition: The value of count is returned.
	public int length()
	{
		return count;
	}

	   //Method to return a reference of the object containing
	   //the data of the first node of the list.
	   //Precondition: The list must exist and must not be empty.
	   //Postcondition: The reference of the object that
	   //			   contains the info of the first node
	   //			   is returned.
	public T front()
	{
		return first.info;
	}

		//Method to return a reference of object containing
		//the data of the last node of the list.
		//Precondition: The list must exist and must not be empty.
		//Postcondition: The reference of the object that
		//			   contains the info of the last node
		//			   is returned.
	public T back()
	{
		return last.info;
	}

	   //Returns a copy of objects data in store.
	   //This method clones only the references stored in
	   //each node of the list. The objects that the
	   //list nodes point to are not cloned.
	public Object clone()
	{
		LinkedListClass<T> copy = null;

		try
		{
			copy = (LinkedListClass<T>) super.clone();

		}
		catch (CloneNotSupportedException e)
		{
			return null;
		}

			//If the list is not empty clone each node of
			//the list.
		if (first != null)
		{
			   //Clone the first node
			copy.first = (LinkedListNode<T>) first.clone();
			copy.last = copy.first;

			LinkedListNode<T> current;

			if (first != null)
				current = first.link;
			else
				current = null;

			   //Clone the remaining nodes of the list
			while (current != null)
			{
				copy.last.link =
						(LinkedListNode<T>) current.clone();
				copy.last = copy.last.link;
				current = current.link;
			}
		}

		return copy;
	}

	   //Method to return an iterator of the list.
	   //Postcondition: An iterator is instantiated and
	   //			   returned.
	public LinkedListIterator<T> iterator()
	{
		return new LinkedListIterator<T>();
	}

	   //Method to determine whether searchItem is in
	   //the list.
	   //Postcondition: Returns true if searchItem is found
	   //			   in the list; false otherwise.
	public abstract boolean search(T searchItem);

	   //Method to insert newItem in the list.
	   //Postcondition: first points to the new list
	   //			   and newItem is inserted at the
	   //			   beginning of the list. Also,
	   //			   last points to the last node and
	   //			   count is incremented by 1.
	public abstract void insertFirst(T newItem);

	   //Method to insert newItem at the end of the list.
	   //Postcondition: first points to the new list and
	   //			   newItem is inserted at the end
	   //			   of the list. Also, last points to
	   //			   the last node and
	   //			   count is incremented by 1.
	public abstract void insertLast(T newItem);

	   //Method to delete deleteItem from the list.
	   //Postcondition: If found, the node containing
	   //			   deleteItem is deleted from the
	   //			   list. Also, first points to the first
	   //			   node, last points to the last
	   //			   node of the updated list, and count
	   //			   is decremented by 1.
	public abstract void deleteNode(T deleteItem);
}


Was This Post Helpful? 0
  • +
  • -

#6 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Linked List

Posted 28 October 2009 - 01:22 PM

It's in C++ but the concept is the same:

template<class T>
void LinkedList<T>::displayAllBackwards(Node<T>* node){
	if (node == NULL) node = head;
	if (node->getNext() == NULL){
		cout << node->getData() << " ";
		return;
	}
	displayAllBackwards(node->getNext());
	cout << node->getData() << " ";
}



If you need to see the rest of this list, read me.
Was This Post Helpful? 0
  • +
  • -

#7 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1954
  • View blog
  • Posts: 4,053
  • Joined: 11-December 07

Re: Linked List

Posted 28 October 2009 - 03:34 PM

It's actually way simpler.

public void printReverse() {
    printReverse(first);
}

private void printReverse(LinkedListNode<T> head) {
  if (head != null) {
      System.out.println(printReverse(head.next));
      System.out.println(head.info);
  }
}


What line are you getting the symbol not found? I'm not looking through all your code to find it.

This post has been edited by cfoley: 28 October 2009 - 03:38 PM

Was This Post Helpful? 0
  • +
  • -

#8 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Linked List

Posted 28 October 2009 - 03:46 PM

Yup, I over complicated it. Mainly because didn't want to encapsulate a function in another. Ultimately irrelevant though.
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5801
  • View blog
  • Posts: 12,638
  • Joined: 16-October 07

Re: Linked List

Posted 28 October 2009 - 04:49 PM

You don't need the print... ;)

private void printReverse(LinkedListNode<T> head) {
   if (head == null) { return; }
   printReverse(head.next);
   System.out.println(head.info);
}


Was This Post Helpful? 0
  • +
  • -

#10 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1954
  • View blog
  • Posts: 4,053
  • Joined: 11-December 07

Re: Linked List

Posted 28 October 2009 - 05:46 PM

Oh well spotted. Does mine even compile?

Nope!

KYA, I know what you mean about having a public function to kick things off and a private function doing the recursion. However, in this case it was either this or expose the node class... something that should definitely not form part of the public interface.

Maybe C++ is different. In java if we had this header:
public void printReverse(LinkedListNode<T> head) {
we would have to kick it off with printReverse(null)

Could you miss out that null and call it with printReverse() in c++?
Was This Post Helpful? 0
  • +
  • -

#11 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Linked List

Posted 28 October 2009 - 06:04 PM

View Postcfoley, on 28 Oct, 2009 - 05:46 PM, said:

Oh well spotted. Does mine even compile?

Nope!

KYA, I know what you mean about having a public function to kick things off and a private function doing the recursion. However, in this case it was either this or expose the node class... something that should definitely not form part of the public interface.


I thought about that too. Having an accessor for the head node was just a dumb idea, so i ended up doing what you did (with the recursive call being private):

template<class T>
void LinkedList<T>::displayAllBackwards(){
	displayAllBackwards(head);
}

template<class T>
void LinkedList<T>::displayAllBackwards(Node<T>* node){
	if (node != NULL){
		displayAllBackwards(node->getNext());
		cout << node->getData() << " ";
	}	
}



View Postcfoley, on 28 Oct, 2009 - 05:46 PM, said:

Maybe C++ is different. In java if we had this header:
public void printReverse(LinkedListNode<T> head) {
we would have to kick it off with printReverse(null)

Could you miss out that null and call it with printReverse() in c++?


You could do a default parameter, but for some reason I couldn't use the one I wanted. I'm sure I overlooked some finicky rule about default parameters and their usage in templates.
Was This Post Helpful? 0
  • +
  • -

#12 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1954
  • View blog
  • Posts: 4,053
  • Joined: 11-December 07

Re: Linked List

Posted 29 October 2009 - 02:23 AM

mmm default parameters don't exist in Java. The recommended way to get the same functionality is overloading methods. I can see why they made that design decision but it's actually a feature I would like to use.

I should really just bite the bullet and learn c++.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1