CSC212 Lab 6 2014

--D. Thiebaut (talk) 10:56, 1 October 2014 (EDT)

---

Singly-Linked Lists

Watch the video below first.

Question 1

• Take the IntSLLNode code from the video and put it in a separate class in your directory. Make sure it's public.
• Create a new file with a class called BasicLinkedList.
• Put the code from the video that creates a list of 3 elements in the main() method of your new class.
• You can printAll your list with this code:

for ( IntSLLNode it = head; it  != null; it = it.next ) {
    System.out.println( it.info );
}

Question 2: A Better Linked-List

• Create a new class called MyLinkedList
• Make head and tail two private members of the new class
• Add a constructor that will set head and tail to null
• Add an addToHead( int el ) method that inserts a new integer at the front of the list. Note that the code is different depending whether the list is empty, or not.
• Add an addToTail( int el ) method that inserts a new integer at the end of the list. Note, as well, that the code is different depending on whether the list is empty or not.
• Add a printAll() method that will use a loop to printAll the contents of your list.
• Add this code in the main() method:

public static int main( String[] args ) {
    MyLinkedList L = new MyLinkedList();

    L.addToHead( 5 );
    L.addToHead( 10 );
    L.addToTail( 3 );
    L.printAll();

}

• Verify that you get a list with 10, 5, and 3 listed in that order.

Question 3: Testing!

• Try this code, and verify that it works with your list.

public static int main( String[] args ) {
    MyLinkedList L = new MyLinkedList();

    L.addToTail( 30 );
    L.addToTail( 20 );
    L.addToTail( 10 );

    L.printAll();

}

• Make sure you fix any errors you may get!

Question 4: Add an isEmpty() Method

• Add an isEmpty() method. Make it return true if the list is empty, false otherwise.
• Test your method.

Question 5: Add a length() Method

• Add a new method that will return the length.
• Instead of creating a loop that will go through all the elements of the list and count them (why is it a bad idea?), add new member variable called length, and set it to 0 in the constructor. Then increment it by 1 in every method that inserts an item, and decrement it by 1 in every method that removes an item.
• The new method just has to return the field length.
• Test your new method thoroughly

Question 5: add a deleteFromHead( ) Method

• First, figure out on a piece of paper how to remove the front element of a non-empty list.
• Once you have a diagram ready, code the series of actions that need to take place. We will assume that deleteFromHead() will always be called on a non-empty list. The user will have to use isEmpty() first before trying to remove anything.
• Make your method return the integer in the element just removed.
• Test your new method as follows:

public static int main( String[] args ) {
    MyLinkedList L = new MyLinkedList();

    L.addToTail( 30 );
    L.addToTail( 20 );
    L.addToTail( 10 );

    while ( ! L.isEmpty() ) {
        int el = L.deleteFromHead();
        System.out.println( "--- Just removed: " + el );
        System.out.print( "L = " );
        L.printAll();
    }
}

• Fix any errors that may come up (in particular, make sure you make your list officially empty when you remove the very last element)!