CSC 225 Fall 2017 Lab #1:
Your first lab will be Sept. 11, 12, or 15.

Try to complete the exercises posted before attending the lab. Attend the lab even if you do not find time to complete everything beforehand.

Learning objectives: This tutorial reviews linked lists (material that should have been covered in CSC 115 or 116 or an equivalent class). The goal is to make sure you are able to write correct programs using singly linked lists of integers. You also should be able to step through the code given drawing pictures to indicate how the data structure is updated as each statement is executed.

The data structure considered has values for:
n- the number of items in the list,
start- a pointer to the first cell on the list, and
rear- a pointer to the last cell on the list.

During the lab, we will discuss the bugs in the Java code given below and the important issues for writing correct code.

Given the class ListNode:

class ListNode{
   public int data;
   public ListNode next;
   public ListNode(int x, ListNode ptr)
   {
       data= x;
       next= ptr;
   }
}

public class LinkedList
{
   int n;
   ListNode start;
   ListNode rear;

   public LinkedList()
   {
       n= 0;
       start= null;
       rear= null;
   }
// Assumes the list is already sorted and inserts a new
// cell into the list with the data value.
// This code is buggy. What are the bugs and
// how can the code be fixed?

   public void insertList(int value)
   {
       ListNode current;
       current= start;

       while (current.next.data < value)
       {
           current= current.next;
       }
       current.next= new ListNode(value, current.next);
   }
}

1. Draw pictures that show what happens to the linked list data structure if you start the linked list sortedList that looks like this:
   
   and try these insertions:

   sortedList.insertList(5);
   sortedList.insertList(1);
   sortedList.insertList(42);
   

2. What are the bugs in the insertList method? In the tutorial, I would like you to discuss this in small groups and also check to make sure you understand what happens when the code is executed.
3. Write a insertList method that works correctly and bring this code to your tutorial.
4. If I gave you a linked list and asked you to check if it was set up correctly, what would you check for in a checkList routine?

1. Main.java
2. ListNode.java
3. LinkedList.java
4. in_lab1.txt

If you run it like this:
java Main < in_lab1.txt > out_lab1.txt
The final output in the file out_lab1.txt should look like this:

The original list:
The list has 4 items: 
2 4 6 8 
After inserting 5:
The list has 5 items: 
2 4 5 6 8 
After inserting 1:
The list has 6 items: 
1 2 4 5 6 8 
After inserting 42:
The list has 7 items: 
1 2 4 5 6 8 42 
Try inserting into an empty list:
The list has 1 items: 
7