ListIterator in Java as It Relates to File Recovery

Understanding lists and especially linked lists are not just essential for a flexible array operations, but also key concept in data structures.  The list iterator class is a useful class to traverse the list contents in an easy an convenient way.

I can just imagine Bill Gates learning about data structures and linked lists in college and thinking to himself that this kind of structure can be used to catalog file chunks and keep all of the chunks in a simple object array. 

In the technical fields, we can find linked lists in the implementation of file systems like File Allocation Table ( FAT ).  The Directory entry is an array of pointers pointing to the first node in the list of nodes connecting all clusters that belong to a single file.  The end of the file is marked by setting of the next pointer to null or FFFF in a case of FAT16.  Looking at the FAT table, you would expect to see these values in little endian format, 2001 2101 FFFF written at cluster numbers 287, 288,289 respectively.

In this case, you can see the file named _ESTFIL.TXT is the deleted file that we'll try to reconstruct.  We know its size is 1443 bytes and the start of the linked list that contains the file contents is starting at cluster 287.  The underscore character is replaced by the σ ( sigma or 0xE5 in Base-16 value ) character when the file is deleted.  Since we know the file size and since this is a floppy drive with cluster size of 1 or 512 bytes, we can easily calculate that it will take 3 clusters to store this file, thus 3 clusters need to be located in order to recover it.  Thus, we'll have 512bytes in the first cluster, 512 bytes in the second cluster, and 419 bytes in the third cluster.  As you can see below, ( look at the yellow numbers only ) 288,289, and <EOF> are highlighted. The number of 288 is on top of cluster 287 where our file started.  So, 287 is the location of the cluster number and the number is the next pointer that points to cluster 288.  At cluster number 288, the value is 289 meaning that cluster 288 is pointing to 289.  As you can see, cluster value 289 ( see image below ) is holding the value <EOF> designating the end of the file.

java.util.LinkedList -  is a doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

java.util.List - An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

java.util.ListIterator - An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.

java.util.ArrayList - Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null.

Simplified UML diagram of the example code discussed in this post.

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.LinkedList;

public class CarDemo{
  public static void main(String args[]){
    ListIterator<Car> litr = null;
    List<Car> cars = new ArrayList<Car>();
    cars.add(new Car("Toyota","Supra"));
    cars.add(new Car("Honda","Accord"));
    cars.add(new Car("Mazda","MPV"));
    cars.add(new Car("Porsche","Carrera"));
    cars.add(new Car("BMW","M3"));
   
    LinkedList<Car> linkedlist = new LinkedList<Car>();

         linkedlist.add(new Car("Toyota","Supra"));
         linkedlist.add(new Car("Honda","Accord"));
         linkedlist.add(new Car("Mazda","MPV"));
         linkedlist.add(new Car("Porsche","Carrera"));
         linkedlist.add(new Car("BMW","M3"));
        
    litr=cars.listIterator();

    while (litr.hasNext()) { //all of this is done on a single node
           //set a new model for the first node, next() will advance
           litr.next().setModel("Volkswagen");
          //go back to the first node and get its node and get its model, sets the position back one node
          System.out.println(litr.previous().getModel()); 
         //go forward again to the first node and get its make
         System.out.println(litr.next().getMake());
         litr.previous();      //this will cause us to be in an infinite loop
    }
  }
}


public class Car{
    private String make;
    private String model;
    public Car() {
        make="";
        model="";
    }
    public Car(String ma,String mo) {
        make=ma;
        model=mo;
    }
    public String getMake()    {return make;    }
    public String getModel()    {return model;    }
    public void setMake(String ma)    { make=ma;    }
    public void setModel(String mo)    { model=mo;    }
}

The code above will create an array of file objects of Car.

The linked list is structured very differently and it is much closer structure to the file system example we started this discussion.  Each car object added to the list has its next and prev pointers.

         linkedlist.add(new Car("Toyota","Supra"))       //first node, prev=null
         linkedlist.add(new Car("Honda","Accord"))
         linkedlist.add(new Car("Mazda","MPV"))
         linkedlist.add(new Car("Porsche","Carrera"))
         linkedlist.add(new Car("BMW","M3"))              //last node, next=null


Object structure pointing to the first node of the linked list.

As you can see below the last pointer's next pointer is null indicating the last node and the end of the linked list.