CSC212 Lab 6 2014

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

---

Singly-Linked Lists

Problem 1

Watch the video below first.

• 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 );
}

Problem 2: A Better Linked-List

In this problem you build a Linked List from scratch.

Question 1

• 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 2: 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 3: Add an isEmpty() Method

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

Question 4: 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)!

Question 6: Full Test

• Add this new method to your linked-list class:

	public void printStatus( String caption ) {
		System.out.println( "+===========================================\n|" + caption );
		System.out.println( "+===========================================\n| List:");
		System.out.println( isEmpty()? "| is empty": "| is not empty" );
		System.out.println( "| contains " + length + " element" + ((length!=1)? "s":"" ) );
		System.out.print( "| elements: " );
		printAll();
		System.out.println( "+===========================================" );
	}

• Replace your main() with this new version:

        public static void main(String[] args) {
                MyLinkedList L = new MyLinkedList();
                
                L.printStatus( "Brand new list" );
                
                for ( int i=10; i<50; i+= 10 ) 
                        L.addToTail( i );
                
                L.printStatus( "After adding 10, 20, ...  to tail...");
                
                L = new MyLinkedList();
                L.printStatus( "Brand new list" );
                
                for ( int i=5; i<50; i+= 10 ) 
                        L.addToHead( i );
                
                L.printStatus( "After adding 5, 15, ... to head...");
                
                while ( ! L.isEmpty() ) {
                        int el = L.deleteFromHead();
                        L.printStatus( "After removing " + el );
                }
       }

• Test your program and verify that it behaves correctly.
• Here's the output you should get:

+===========================================
|Brand new list
+===========================================
| List:
| is empty
| contains 0 elements
| elements: 
+===========================================
+===========================================
|After adding 10, 20, ...50  to tail...
+===========================================
| List:
| is not empty
| contains 5 elements
| elements: 10 20 30 40 50 
+===========================================
+===========================================
|Brand new list
+===========================================
| List:
| is empty
| contains 0 elements
| elements: 
+===========================================
+===========================================
|After adding 5, 15, ... to head...
+===========================================
| List:
| is not empty
| contains 5 elements
| elements: 45 35 25 15 5 
+===========================================
+===========================================
|After removing 45
+===========================================
| List:
| is not empty
| contains 4 elements
| elements: 35 25 15 5 
+===========================================
+===========================================
|After removing 35
+===========================================
| List:
| is not empty
| contains 3 elements
| elements: 25 15 5 
+===========================================
+===========================================
|After removing 25
+===========================================
| List:
| is not empty
| contains 2 elements
| elements: 15 5 
+===========================================
+===========================================
|After removing 15
+===========================================
| List:
| is not empty
| contains 1 element
| elements: 5 
+===========================================
+===========================================
|After removing 5
+===========================================
| List:
| is empty
| contains 0 elements
| elements: 
+===========================================

Problem 3: Java Linked List

Question 1

Java contains a LinkedList data structure. All you need to do to create and save some elements in such a list is illustrated in the snippet below:

/**
 * declares a linked list, stores some numbers in it, then display the contents
 * @author Thiebaut
 */
import java.util.Iterator;
import java.util.LinkedList;


/**
  * The main class demonstrating the LinkedList
  */
public class Lab6_3 {

	
        /**
         * main entry point
         */  
	public static void main(String[] args) {
                // create a new linked list
		LinkedList L = new LinkedList();
		
                // add 5 integers to it.
		for ( int i=10; i<=50; i+= 10 ) 
			L.addFirst( i );
		
               // display contents of list
               System.out.println( L );
	}

}

• Create a new class with the code above.
• Run it.
• Verify that it runs correctly.

Question 2

• Search the Web for the Oracle page describing LinkedLists.
• Using the documentation for this data structure, perform the same tests you performed with your linked list in Question 6 above. In particular you should make your main program:

• Add 5 ints to the front of the list
• Display the list
• Get a new empty list
• Add 5 ints at the end of the list
• Display the list
• Empty the list until it is empty. Every step,

• get the element removed,
• display it
• display the remaining list
• display the length of the remaining list

• Stop when the list is empty.