CSci 2101 Data Structures: Lab 4

Problem 1 (paper-and-pencil)

For the following program draw the memory picture at two points of the program execution: right before each of the print statement gets executed. Based on your picture, what would each of the statements print? Run the program to check your result. If they are different from what your pictures predict, correct the pictures. 

public class WhatHappens {
    public static void main(String [] args) {
	Node n1 = new Node(1);
	Node n2 = new Node(2);
	Node n3 = n1;

	n3.setNext(n2);
	System.out.println( (n1.getNext()).getData() );
	
	n3 = new Node(3);
	(n1.getNext()).setNext(n3);
	System.out.println( (n2.getNext()).getData() );

    }
}
Submit the two memory pictures (on paper). You don't need to submit any files for this problem.

Problem 2

In the file TestLinkedLists.java write a loop to count the number of nodes of the list with data value 5. Test the program, submit ALL your test results.

Problem 3

In the file LinkedList.java add a method length() which counts the number of elements on the list. The list itself should not change in any way.
Write testing code for the method in a new file TestLength.java (create a linked list, add some elements to it or keep it empty, and call the method length() on the list). Make sure to test the method thoroughly before going on to the next problem.

Problem 4

Copy/paste the following program into a file WeirdList.java: 

public class WeirdList {
   public static void main(String [] args) {
      Node n;
      // fill in your code here to initialize node n 
      // you may create other nodes if needed


      // don't change any code below this point
      LinkedList weirdlist = new LinkedList();
      weirdlist.setFirst(n);
      System.out.println("the length of the list is " + weirdlist.length());
   }
}
Don't modify any code after the last line of comments.

Problem 5

Look at the following program and try to predict what happens when you run it (drawing memory pictures helps). Then run the program. Important: press Ctrl-C (the Ctrl key and the C key at the same time) to stop the program. 

public class Why {
    public static void main(String [] args) {
	// testing nodes:
	Node first = new Node(5);
	Node second = new Node(6);
	first.setNext(second);
	second.setNext(first);

	// testing linked lists:
	LinkedList list = new LinkedList();

	// add the two nodes to the list
	list.setFirst(first);
	list.addFront(second);

	// print the list
	System.out.println("The list elements are:");
	Node n = list.getFirst(); // if the list is empty, first is null
	while(n != null) {
	    int data = n.getData();
	    System.out.println(data);
	    n = n.getNext();
	}

    }
}

On the Wiki submission page explain why the program's behaves this way. You don't need to submit any code for this problem.

Problem 6

For this and the next problem assume that linked lists don't have any peculiarities, such as those in problem 5.
In a new file create a linked list. Then write a loop that will go through the list and duplicate each node. For instance, if the list had three nodes with data 5, 4, 3, then after the loop the list should have 6 nodes with data 5, 5, 4, 4, 3, 3. Make sure that the program works correctly for an empty list. Print out the list at the end to test the program. Submit all your test cases.

*Problem 7* (extra credit)

In a new file create a linked list and then write a loop to remove all the elements of the list with a data value 5. Print the list at the end to check the result. BR> This is a hard problem. Test it carefully. Make sure to submit ALL your test cases with the program. If it doesn't work in some cases, submit the test cases and explain what doesn't work (and, ideally, what you think is the reason for the problem). Partial credit will be given for programs that work in some, but not all, cases. Explanations contribute to the grade.
This is a lab from CSci 2101 course.