Week 1. Summary

This week we started with the simplest linear data structure: arrays. Arrays are collections of elements of the same type, either primitive data types or objects of class types. Arrays have an attribute length, which helps us traverse arrays with for/while loops. Nevertheless, arrays have an important limitation: once the capacity is set it cannot be modified. Therefore, we cannot store in arrays more elements than the number defined in their capacity. While accessing any element in an array takes roughly the same amount of time, operations such as concatenating or splitting arrays are computationally expensive. Inserting an element in a given position of the array is also computationally expensive as it requires shifting to the right all the remaining elements from that position to the end of the array.

Recent Java versions allow working with generics, which serve to define the data types a class can handle. Generics are particularly relevant when working with data structures, as we can indicate what type of objects can be stored in the data structure, and check at compile time that everything is correct. Generics add stability to our code and act as a safety measure precluding from having errors at runtime due to incompatible types. It is important to note that errors at runtime are much more problematic than errors at compile time. We can use Java classes that make use of generics, but we can also define our own classes to make use of generics, as we saw with examples throughout this week...

Linked lists are linear data structures that overcome some of the limitations of arrays. They can be extended to store a non-predefined number of elements, and allow inserting elements, concatenating and splitting lists with much less effort than in the case of arrays. The access to certain elements of the linked list takes, however, more effort than in the case of arrays, due to the need of traversing the list until the desired position. Linked Lists can be traversed in one way (singly linked lists, where each node has a reference to the next node) or in two ways (doubly linked lists, where each node has a reference to the next and to the previous nodes)

Finally, this week also introduced some important Java interfaces and classes which helps us work with linear data structures. These were the interfaces Collection<E> and List<E>, and the classes LinkedList<E> and ArrayList<E>. Some of the main methods of these classes and interfaces have been explored in this week with specific exercises, although there are many more methods that could not be covered due to lack of time. We invite you to delve into the APIs for these classes and interfaces, and test the different methods to understand them better.

---

Solution to Operations with Arrays

Notice that in both methods we should traverse the array from index 1 to length -1 (including the latter). We are not including index 0 because we have already initialized the variable var with the proper value (the index 0 in the indexMin() method, the value of the position 0 in the min() method).

/**
 * Operations with Arrays. Solution
 */
public class ArraysTest{
    
    private static void print(String name, int a[]){
	    System.out.print(name +" = [");
	    for (int i=0; i < a.length-1; i++){
	        System.out.print(a[i]+", ");
	    }
	    System.out.println(a[a.length-1]+"]");
    }

    private static int indexMin(int[] array) {
    	int var = 0;
	    for (int i = 1; i < array.length; i++) {
	        if (array[i] < array[var]) {
		        var = i;
	        }
	    }
	    return var;
    }

    private static int min(int[] array) {
	    int var = array[0];
	    for (int i = 1; i < array.length; i++) {
	        if (array[i] < var) {
		        var = array[i];
	        }
	    }
	    return var;
    }

    public static void main(String args[]){
	    int[] arrayA = new int[]{0,1,2,3,4,5};
    	int[] arrayB = new int[10];
	
	    for (int i = 0; i<10; i++){
	        arrayB[i] = (int) (Math.random()*100);
	    }

	    print("A", arrayA);
	    // This sentence behaves exactly the same as the previous method call
	    System.out.println("A = "+java.util.Arrays.toString(arrayA));
    	print("B", arrayB);
	    System.out.println("B = "+java.util.Arrays.toString(arrayB));
	
	    System.out.println("min(A) = "+ min(arrayA));
	    System.out.println("indexMin(A) = "+ indexMin(arrayA));

	    System.out.println("min(B) = "+ min(arrayB));
	    System.out.println("indexMin(B) = "+ indexMin(arrayB));
    }
}

---

solution to exercise about classes with generics

/**
 * Classes with Generics (Solution)
 */

/**
 *  When compiling, a warning will be printed due to the unchecked cast
 *  (MyClass<E>)other in class MyClass.java
 */
public class GenericsTest{

    public static void main(String args[]){

    	Integer a = new Integer(65);
	    int b = 65;
	    String foo = new String("A new String");
	
	    MyClass<Integer> one = new MyClass<Integer>(a);
	    System.out.println(one.get());

	    MyClass<Integer> two = new MyClass<Integer>(b);
	    System.out.println(two.get());

	    MyClass<String> first = new MyClass<String>(foo);
	    System.out.println(first.get());

	    MyClass<String> second = new MyClass<String>("A new String");
	    System.out.println(second.get());

        // If no equals method is provided, 
        // equals is the one implemented by the class Object
        // that compares references
        // So, you should override the equals method for this class

	    if (one.equals(two))
	        System.out.println("They are equal");
	    else
	        System.out.println("They are different");

	    if (second.equals(first))
	        System.out.println("They are equal");
	    else
	        System.out.println("They are different");

        MyClass<String> x = new MyClass<String>("x");
	    MyClass<String> n1 = new MyClass<String>(null);
	    MyClass<String> n2 = new MyClass<String>(null);
	    System.out.println(n1.get());
	    System.out.println(n2.get());
	    if (n1.equals(n2) && n2.equals(n1)) {
	    	System.out.println("They are equal");
	    } else {
	    	System.out.println("They are different");
	    }
	    System.out.println(n1.get());
	    System.out.println(x.get());
	    if (n1.equals(x) || x.equals(n1)) {
	    	System.out.println("They are equal (error)");
	    } else {
	    	System.out.println("They are different (ok)");
	    }
	    
	    MyClass<String>  se = new MyClass<String>("e");
	    MyClass<Double> ie = new MyClass<Double>(2.71828);
	    System.out.println(se.get());
	    System.out.println(ie.get());
	    if (se.equals(ie) || ie.equals(se)) {
	    	System.out.println("They are equal (error)");
	    } else {
	    	System.out.println("They are different (ok)");
	    }
    }

}

class MyClass<E>{
    private E attribute;
    
    MyClass(E var){
	    this.attribute = var;
    }
    public E get(){
	    return this.attribute;
    }
    public void set(E value){
	    this.attribute = value;
    }
    public int hashCode() {
    	return attribute.hashCode();
    }
    
    public boolean equals(Object other){
        
        if(other instanceof MyClass<?>) {
	       	if (this.get() == null) {
		        // checks if both attributes are null
		        return this.get() == ((MyClass<E>)other).get();
	        } else {
		    // checks if both attributes are equal
		    return this.get().equals( ((MyClass<E>)other).get());
	        }
        } else {
            return false;
        }        
    }
    
}

---

solution to creation of a linked list and insertion at the end

/*
 * Exercise for Creation of a Linked List and printing
 */
public class CreateLinkedList{

    public static void main(String args[]){
	    MyLinkedList<Integer> first = new MyLinkedList<Integer>();
	    for (int i=0; i< 10; i++){
	        first.insert(i);
	    }
	    first.print();
	    MyLinkedList<Integer> second = new MyLinkedList<Integer>();
	    for (int i=0; i< 10; i++){
	        second.insertEnd(i);
	    }
	    second.print();
    }
}

public class MyLinkedList<E>{
    private Node<E> first;
    
    public MyLinkedList(){
	    this.first = null;
    }
    
    /*
     * Insertion at the beginning
     */
    public void insert(E info){
	    Node<E> newNode = new Node<E>(info);
	    newNode.setNext(first);
	    first = newNode;
    }
    /*
     * Insertion at the end 
     */
     
    public void insertEnd(E info){
	    Node<E> newNode = new Node<E>(info);
	    Node<E> current = first;
	    
	    if (current == null){
	        first = newNode;
	    }
	    else{
	        while (current.getNext()!=null){
	            current = current.getNext();
	        }
	        current.setNext(newNode);
	    }
    }
    
    /*
     * Extraction of the first node
     */
    public E extract(){
	    E data = null;
	    if (first != null){
	        data = first.getInfo();
	        first = first.getNext();
	    }
	    return data;
    }
    /*
     * Print all list
     */
    public void print(){
	    Node<E> current = first;
	    
	    while (current != null){
	        System.out.print(current.getInfo() + " ");
	        current = current.getNext();
	    }
	    System.out.println();
    }
}

public class Node<E>{
    private E info;
    private Node<E> next;

    public Node(){
	    this.next = null;
    }

    public Node(E info){
	    this.info = info;
	    this.next = null;
    }
    public Node(E info, Node<E> next){
	    this.info = info;
	    this.next = next;
    }

    public E getInfo(){
	    return this.info;
    }
    public void setInfo(E info){
	    this.info = info;
    }
    public Node<E> getNext(){
	    return this.next;
    }

    public void setNext(Node<E> next){
	    this.next = next;
    }

}

---

solution to deleting elements from a linked list

public class MyLinkedList<E>{
    private Node<E> first;
    
    public MyLinkedList(){
	    this.first = null;
    }
    
    /*
     * Insertion at the beginning
     */
    public void insert(E info){
	    Node<E> newNode = new Node<E>(info);
	    newNode.setNext(first);
	    first = newNode;
    }
    /*
     * Delete the first occurrence of a value 
     * Return a boolean stating if the delete was successful
     */
    public boolean deleteFirstOccurrence(E info){
        boolean found = false;
	    if (first != null){
	        Node<E> current=first;
	        Node<E> previous=first;
	        
	        while ((current !=null)&&(!current.getInfo().equals(info))){
	            previous = current;
	            current = current.getNext();
	        }
	        
	        if (current != null){
	            found = true;
	            if (current ==previous){
	            // The first ocurrence is within the first node
	                first = first.getNext();
	            }else{
	                previous.setNext(current.getNext());
	            }
    	    }
        }
        return found;
    }
    /*
     * Delete all the occurrences of a value
     * Returns the number of deleted nodes
     * Possible implementation using deleteFirstOccurrence
     */
     public int deleteAll(E info){
        int number=0;
	    while (deleteFirstOccurrence(info))
	        number++;
        return number;
    }
    /*
     * Extraction of the first node
     */
    public E extract(){
	    E data = null;
	    if (first != null){
	        data = first.getInfo();
	        first = first.getNext();
	    }
	    return data;
    }
    /*
     * Print all list
     */
    public void print(){
	    Node<E> current = first;
	    
	    while (current != null){
	        System.out.print(current.getInfo() + " ");
	        current = current.getNext();
	    }
	    System.out.println();
    }
}

public class Node<E>{
    private E info;
    private Node<E> next;

    public Node(){
	    this.next = null;
    }

    public Node(E info){
	    this.info = info;
	    this.next = null;
    }
    public Node(E info, Node<E> next){
	    this.info = info;
	    this.next = next;
    }

    public E getInfo(){
	    return this.info;
    }
    public void setInfo(E info){
	    this.info = info;
    }
    public Node<E> getNext(){
	    return this.next;
    }

    public void setNext(Node<E> next){
	    this.next = next;
    }

}

/*
 * Exercise for Removing the first occurrence of a given value
 * and removing all the occurrence of a given value
 */
public class RemoveLinkedList{

    public static void main(String args[]){
        // Create a linked list using MyLinkedList<Integer>
	    MyLinkedList<Integer> mine = new MyLinkedList<Integer>();
	    boolean success;
	   
	    // Insert 10 ints at the beginning (twice)
	    for (int i=0; i< 10; i++){
	        mine.insert(i);
	        mine.insert(i);
	    }
	    
	    System.out.println("Test: deleting first occurrence of a value");
	    //Print the whole list
	    mine.print();
	    
	    System.out.print("Deleting 9: ");
	    success = mine.deleteFirstOccurrence(9);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 9: ");
	    success = mine.deleteFirstOccurrence(9);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 9: ");
	    success = mine.deleteFirstOccurrence(9);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 5: ");
	    success = mine.deleteFirstOccurrence(5);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 5: ");
	    success = mine.deleteFirstOccurrence(5);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 5: ");
	    success = mine.deleteFirstOccurrence(5);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 0: ");
	    success = mine.deleteFirstOccurrence(0);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 0: ");
	    success = mine.deleteFirstOccurrence(0);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    System.out.print("Deleting 0: ");
	    success = mine.deleteFirstOccurrence(0);
	    if (success){
	        System.out.println("First occurence deleted");
	    }else{
	        System.out.println("Element with that info not found");
	    }
	    mine.print();
	    
	    
	    mine = new MyLinkedList<Integer>();
	    int numberdeleted;
	   
	    // Insert 10 ints at the beginning (twice)
	    for (int i=0; i< 10; i++){
	        mine.insert(i);
	        mine.insert(i);
	    }
	    System.out.println("Test: deleting of all the occurrences of a value");
	    //Print the whole list
	    mine.print();
	    
	    System.out.print("Deleting 9: ");
	    numberdeleted = mine.deleteAll(9);
	    System.out.println(numberdeleted + " deleted nodes");
	    mine.print();
	    System.out.print("Deleting 0: ");
	    numberdeleted = mine.deleteAll(0);
	    System.out.println(numberdeleted + " deleted nodes");
	    mine.print();
	    System.out.print("Deleting 5: ");
	    numberdeleted = mine.deleteAll(5);
	    System.out.println(numberdeleted + " deleted nodes");
	    mine.print();
	    System.out.print("Deleting 100: ");
	    numberdeleted = mine.deleteAll(100);
	    System.out.println(numberdeleted + " deleted nodes");
	    mine.print();
    }
}

---

Solution to inserting elements in a linked list in a sorted way

 

---

Solution to linked list with head and tail

---

 

Solution to doubly linked list

 

---

Solution to the interface list<E> and the class arraylist<E> 

 

---

Solution to LAB1: Finding path in maze : modeling the maze