java hmwk help - linked lists

[julylee06]

Ok, so I need some guidance. Am trying to implement a linked list in java. I can't get it. I have been on here - dreaminncode, wikipedia, and some other colleges sites - I still don't/can't get it. I did look at the previous threads on this but they didn't quite cover it for me. Any advice would be greatly appreciated.

Here's the assignment:
Design your own List class to hold a series of integers in ListNode classes. The list class must implement the following methods:

· No Argument Constructor – this will initialize the list as having no elements
· Copy Constructor – this will copy the elements from another List
· appendItem – create a new node and add it to the end
· insertItem – insert a new node into a list such that it is after a smaller integer and before a larger one
· deleteItem – delete all instances of the item from the list
· print – print the list in order to the console
· sort (extra credit) – sort the items in the list and put them in ascending order

Here's all of my code:

public class List 
{
	private ListNode head;
	
	//constructor
	public List()
	{
		head = null;
	}
	
	//to append the list
	public void appendItem(int item)
	{
		ListNode newNode = new ListNode(item);
		
		if (head == null)		
		{
			head = newNode;
		}
		else					
		{
			// find last item in list
			ListNode nextNode = head;
			
			while (nextNode.getNext() != null)
			{
				nextNode = nextNode.getNext();
			}
			
			nextNode.setNext(newNode);
		}
	}
	
	public void insertItem(int item)
	{
		ListNode temp = new ListNode(item);
		ListNode current = head;
		
		for(int i = 1; i < i && current.getNext() != null; i++)
		{
			current = current.getNext();
		}
		temp.setNext(current.getNext());
		current.setNext(temp);
	}

	public boolean deleteItem(int index)
	{
		ListNode current = head;
		for(int i = 1; i < index; i++)
		{
			if(current.getNext() == null)
				return false;
			current = current.getNext();
		}
		current.setNext(current.getNext().getNext());
		
		return true;
	}

	
	public void printItem()
	{ 
		ListNode nextNode = head;
		
		while (nextNode.getNext() != null)
		{
			System.out.print(nextNode.getNext());
		}
		
	}
	
	
	public ListNode getHead()
	{
		return head;
	}

	
	
	public void setHead(ListNode listNode)
	{
		head = listNode;
	}

}

public class ListNode 
{
	private int newItem;
	private ListNode nextNode;
	
	
	public ListNode()
	{
		newItem = 0;
		nextNode = null;
	}
	
	public ListNode(int item)
	{
		newItem = item;
		nextNode = null;
	}
	
	public void setNext(ListNode next)
	{
		nextNode = next;
	}
	
	public ListNode getNext()
	{
		return nextNode;
	}
	
	public void setItem(int item)
	{
		newItem = item;
	}
	
	public int getItem()
	{
		return newItem;
	}
}

public class LinkedListDriver 

{

       public static void main(String[] args) 

       {

              List list = new List();

       

              list.appendItem(1);

              list.appendItem(2);

              list.appendItem(3);

              list.appendItem(42);

              list.appendItem(5);

              list.appendItem(2);

              

              list.insertItem(0);

              list.insertItem(5);

 

              list.insertItem(4);

              list.insertItem(192);

              list.appendItem(9);

              

              list.insertItem(3);

              list.appendItem(3);

              

              System.out.println("Print after insert and appends");

              list.printItem();

              

              //list.deleteItem(9);

              //list.deleteItem(1);

                           

              //list.deleteItem(3);

 

              System.out.println("Print after deletes");

              list.printItem();

 

              list.appendItem(44);

              list.appendItem(22);

              list.appendItem(1);

              

              System.out.println("Print prior to sort");

              list.printItem();

              

              //list.sort();

              

              System.out.println("Print after sort");

              list.printItem();
       }

}

The error I am getting in Eclipse keeps crashing the school's computer - here's a very small snipet:
ListNode@19821fListNode@19821fListNode@19821fListNode@19821fListNode@19821fListNode@19821fListNode@19821f

[Taywin]

The error you got and posted from Eclipse is garbage for debugging. You can't debug with that.

Anyway, your ListNode class is fine. There are problems with your List class. There is questionable for one of your requirement in the "insertItem()" method. Should the insertion occurs after the "head" node only? To me, it should NOT occur only after "head" node. You may need to get the answer from your instructor. However, in my suggestion, it is from my interpretation.

Here are my list of things your code won't work or not properly work.

// *** Please do not use "for" loop when you are working with linked list.
//     Because you can simply go through the list without knowing the size
//     of the list. "for" loop should be used when you know how many times
//     you want to go through before the loop starts. Please use "while"
//     loop instead because it is more appropriated.
public void insertItem(int item) {
  ListNode temp = new ListNode(item);
  ListNode current = head;

  // Why do you exclude the "head" node out of the insertion?
  // The insert method requirement is to add an item whose value is
  // between 2 first value pair you found.
  //   i.e.  existing linked list is  7->22->3->9->0
  //         call insertItem(8);
  //         result should be  7->8->22->3->9->0
  //         call insertItem(5)
  //         result should be  5->7->8->22->3->9->0
  // *** The loop is also incorrect. You need to check whether the current node value
  //     is less than the item you are inserting. And also, you need to check whether
  //     the next node value after the node you are checking is greater than the
  //     item you are inserting. Therefore, the "current" node you get from the
  //     loop result should be the one which has the value less than the inserting
  //     item value. Please fix this loop. And please use while loop instead.
  for(int i = 1; i < i && current.getNext() != null; i++) {
    current = current.getNext();
  }

  // *** This insertion is correct if and only if you correctly find the
  //     "current" node.
  temp.setNext(current.getNext());
  current.setNext(temp);
}


public boolean deleteItem(int index) {
  ListNode current = head;

  // Deleting a node must include "head" node. You are excluding the "head" node
  // which is incorrect.
  // *** Please be careful! In the requirement, you need to delete "all" of
  //     the item of the selected item from the list. You are NOT deleting
  //     the node from a specified index value. Also, delete all of them if
  //     you found.
  //     i.e.  existing list node 7->4->5->22->0->7->6->5
  //           call deleteItem(5);
  //           result  7->4->22->0->7->6
  //           call deleteItem(7)
  //           result  4->22->0->6   <-- notice that the "head" is now 4, not 7
  // *** The check for "head" is null should be the first thing to do. If it is
  //     null, return false right away.
  for(int i = 1; i < index; i++) {
    if(current.getNext() == null)
      return false;
    current = current.getNext();
  }

  // This is correct if and only if the "current" node is the node right before
  // the deleting node.
  current.setNext(current.getNext().getNext());
  return true;
}

	
public void printItem()	{ 
  ListNode nextNode = head;
  // *** Problem here. You should compare the nextNode!=null instead of
  //     the next node. The reason is that you will leave out the last node
  //     and not print it out because your loop will exit prematurely when
  //     the last node shows up. ***
  while (nextNode.getNext() != null) {
    System.out.print(nextNode.getNext());
  }
}


// !!! ALERT !!!
// Please delete this method!!! It is very dangerous in design!!!
// You should never let anyone setting the "head" node at all.
// The reason is that if the "head" variable is holding a list already,
// you will lose the whole existing list by calling only this simple method.	
public void setHead(ListNode listNode) {
  head = listNode;
}

PS: Just to give you info. The name of class "List" is already in the java library. You may want to pick another name in the future. :)

[julylee06]

Thank you - I will work on all of this and reply later - to let you know how it goes! Really appreciate all of your advice!

[julylee06]

I think I made it a bigger fuster cluck than before.... I know that my while loop is wrong - you can't compare in that way with those kinds of variables, but I can't figure out how to do it. I really need a tutor or something. I hate to ask again - but anybody willing to look at this new "fixed" mess of mine?

public class List extends ListNode
{
	public ListNode head;
	
	//constructor
	public List()
	{
		head = null;
	}
	
	//to append the list
	public void appendItem(int item)
	{
		ListNode newNode = new ListNode(item);
		
		if (head == null)		
		{
			head = newNode;
		}
		else					
		{
			// find last item in list
			ListNode nextNode = head;
			
			while (nextNode.getNext() != null)
			{
				nextNode = nextNode.getNext();
			}
			
			nextNode.setNext(newNode);
		}
	}
	
	//to insert item at a certain point
	public void insertItem(int item)
	{
		ListNode temp = new ListNode(item);
		ListNode current = head;
		
		while (current.getNext()!= null )
		{
			if (current!< temp) 
			{
				if (current.getNext()!> temp)
					{
			current = current.getNext();
					}
			}
		}
		temp.setNext(current.getNext());
		current.setNext(temp);
	}

	// to delete a specific item
	public boolean deleteItem(int index)
	{
		ListNode current = head;
		if (head == null)
		{
			return false;
		}
		while (current.getNext() == index)
		{
			if(current.getNext() == null)
				return false;
			current = current.getNext();
		}
		current.setNext(current.getNext());
		
		return true;
	}

	// to print the list
	public void printItem()
	{ 
		ListNode nextNode = head;
		
		while (nextNode()!= null)
		{
			System.out.print(nextNode.getNext());
		}
	}
	
	
	public ListNode getHead()
	{
		return head;
	}

}

Thanks! Swear I will look into getting a tutor!

[Taywin]

Hmm.. I think this problem is harder than I thought for you. It may be easier to explain by writing & drawing for you, but I can't do that on a forum. It is too difficult... Anyway, I will show you the "insertItem()" method. Please try to understand how I traversal your list to find the correct location. You could do it in a similar way to your deleteItem() and printItem() as well.

public void insertItem(int item) {
  ListNode temp = new ListNode(item);
  if (head==null) {  // if insert into an empty list, the item becomes head
    head = temp;
  }
  else if (head.getNext()==null) {  // the list has only 1 node
    // i.e. head is 10, temp is 6
    if (head.getItem()>temp.getItem()) { // new item should be in front
      //  6->10
      //      ^
      //      |__ head
      temp.setNext(head);
      //  6->10
      //  ^
      //  |__ head
      head = temp;  // move the head
    }
    else {
      head.setNext(temp);
    }
  }
  else {  // otherwise, search and insert
    ListNode currentNode = head;
    boolean inserted = false;
    // go through the loop until it is either inserted or it is the last node
    while (currentNode.getNext()!=null && !inserted) {
      // using <= and >= to allow node to be inserted inside the same value
      //   i.e.  5->24->6->6->19
      //         insertItem(6)
      //         temp is 6
      //         5->24->6->6->19
      //                ^
      //                |
      //          the currentNode
      if (currentNode.getItem()<=temp.getItem() &&
          // currentNode.getNext()==null will never happen here
          currentNode.getNext().getItem()>=temp.getItem()) {
        //  5->24->6->6->19
        //            ^
        //            |
        //         6__|
        temp.setNext(currentNode.getNext());
        //  5->24->6  6->19
        //         |  ^
        //         v  |
        //         6__|
        currentNode.setNext(temp);
        inserted = true;  // will cause the loop to exit
      }
    }

    // never inserted until the loop gets to the last node
    // then append the current node with the item
    if (!inserted) {
      currentNode.setNext(temp);
    }
  }
}

That's one way to use while loop to deal with linked list. You need to utilize how to check for "null" node in order to find the location of the target you need to deal with.

[julylee06]

Thank you so much for helping and understanding my stupidity! It was very much appreciated!