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: A Java Linked-List

Question 1

Java contains a Linked-List data structure. Its name is LinkedList. 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.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 the Java LinkedList data structure.
• Locate the different methods you can use to add and remove elements at the front or at the end. Also figure out what methods will indicate if the list is empty, and how many elements are contained. Their names are not the same as the names used in the previous problem.
• 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, one int at a time, until it is empty. At every stop of the loop:

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

• Stop when the list is empty.

Note 1:

if you want to iterate over the element of your LinkedList, you can use this code:

                import java.util.Iterator; // at the top of your program

                Iterator it = L.iterator();
		while ( it.hasNext() ) {
			int el = (int) it.next();
			doSomethingWith( el  );
		}

Note 2:

If you remove an element of your LinkedList, even though you may have stored it as an int, it will come out as an Object, which is the generic type for Java. To store it in an int variable, you will need to typecast it:

          int x = (int) L.removeFirst();