Creates a sorted linked list in a file.

ListInFile.java

import java.io.*;
import java.util.*;

public class ListInFile {

    /*
    Implements a sorted (ascending) list of ints (the keys) and fixed length character
    string fields stored in a random access file.
    Duplicates keys are not allowed. There will be at least 1 character string field
    */
    private RandomAccessFile f;
    private long head; //the address of the head node in the file
    private long free; //the address in the file of the first node in the free list
    private int numFields; //the number of fixed length character fields
    private int[] fieldLengths; //the length of each field

    private class Node {
        private int key;
        private char[][] fields;
        private long next;

        private Node(int k, char[][] fields, long n) {
            //constructor for a new node
            this.key = k;
            this.fields = fields;
            this.next = n;
        }

        private Node(long addr) throws IOException {
            //constructor for a node that exists and is stored in the file
            f.seek(addr);
            this.key = f.readInt();
            this.fields = new char[numFields][];
            for (int i = 0; i < numFields; i++) {
                fields[i] = new char[fieldLengths[i]];
                for (int x = 0; x < fieldLengths[i]; x++) this.fields[i][x] = f.readChar();
            }
            this.next = f.readLong();
        }

        private void writeNode(long addr) throws IOException {
            //writes the node to the file at location addr
            f.seek(addr);
            f.writeInt(key);
            for (char[] field : fields) for (char c : field) f.writeChar(c);
            f.writeLong(next);
        }
    }

    public ListInFile(String fname, int[] fieldLengths) throws IOException {
        //creates a new empty list stored in the file fname
        //the number of character string fields is fieldLengths.length
        f = new RandomAccessFile(fname, "rw");
        this.fieldLengths = fieldLengths;
        numFields = fieldLengths.length;

        // First time setup.
        f.writeLong(0); // init head to null (0)
        f.writeLong(0); // init free to null (0)
        f.writeInt(numFields); // write number of fields
        for (int fieldLength : fieldLengths) f.writeInt(fieldLength); // write in how many chars these arrays can hold
    }

    public ListInFile(String fname) throws IOException {
        File file = new File(fname);
        if (!file.exists()) {
            System.out.println("Wrong constructor used.");
            return;
        }
        //reuse an existing list store in the file fname
        System.out.print("Reopening file " + fname);
        f = new RandomAccessFile(fname, "rw");
        System.out.print(".");
        f.seek(0);
        head = f.readLong();
        free = f.readLong();
        fieldLengths = new int[numFields = f.readInt()];
        System.out.print(".");
        for (int i = 0; i < fieldLengths.length; i++) fieldLengths[i] = f.readInt();
        System.out.print(". Ready.\n");
    }

    public void insert(int k, char[][] fds) throws IOException {
        //PRE: the lengths of rows in fds matches the expects length and
        // the rows are padded with null characters as needed
        //if k is not in the list insert a new item into the list with key k
        //and character fields fds
        //if k is in the list the method does nothing
        long newAddr = f.length(), newNext = 0, prevAddr = head, prevNext, currentAddr;

        if (head == 0) { // Check to see if the list is empty
            if(free != 0) newAddr = getFree(); // There is room on the free list that we should use.
            head = newAddr;
            new Node(k, fds, 0).writeNode(newAddr);
            return;
        }

        Node temp = new Node(head);

        if(k < temp.key){
            // Create a new head node.
            if(free != 0) newAddr = getFree();
            new Node(k, fds, head).writeNode(newAddr);
            head = newAddr;
            return;
        } else if(k == temp.key){
            return;
        } else if(temp.next == 0){
            if(free != 0) newAddr = getFree();
            new Node(k, fds, 0).writeNode(newAddr);
            temp.next = newAddr;
            temp.writeNode(head);
            return;
        }
        // We are dealing with a list with at least one thing and
        // we won't be inserting the node at the head of the list.
        while (true){
            currentAddr = temp.next;
            temp = new Node(currentAddr);
            if(k <= temp.key || temp.next == 0) break;
            prevAddr = currentAddr;
        }

        if(k < temp.key){
            if(free != 0) newAddr = getFree();
            temp = new Node(prevAddr);
            prevNext = temp.next;
            temp.next = newAddr;
            temp.writeNode(prevAddr);
            new Node(k, fds, prevNext).writeNode(newAddr);
        }else if(k == temp.key) return;
        else if(temp.next == 0){
            if(free != 0) newAddr = getFree();
            temp.next = newAddr;
            temp.writeNode(currentAddr);
            new Node(k, fds, 0).writeNode(newAddr);
            return;
        }

    }

    private void addFree(long addr) throws IOException {
        f.seek(addr);
        f.writeLong(free);
        free = addr;
    }

    public long getFree() throws IOException {
        // returns the first free list value and updates the reference.
        long addr = free;
        // find the free space and grab the next free spot.
        f.seek(free);
        free = f.readLong();

        return addr;
    }

    public void print() throws IOException {
        //Print the contents of the items in the list is ascending order of the key
        //print one item (key and character fields) per line
        long addr = head;
        if (head == 0) System.out.println("The list is blank.");
        while (addr != 0) {
            System.out.print(addr + " ");
            f.seek(addr);
            System.out.print(f.readInt());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < numFields; i++) {
                sb.append(" ");
                for (int x = 0; x < fieldLengths[i]; x++) sb.append(f.readChar());
            }
            System.out.print(sb.toString());
            addr = f.readLong();
            System.out.println(" n" + addr);
        }
    }

    public String[] findByKey(int k) throws IOException {
        //if k is in the list return an array of strings (the fields) associated with k
        //otherwise return null
        Node temp = new Node(head);
        while(temp.next != 0 && temp.key != k)
            temp = new Node(temp.next);
        if(temp.key == k){
            String[] arr = new String[temp.fields.length];
            for(int i=0; i<temp.fields.length; i++){
                StringBuilder sb = new StringBuilder();
                for(int x=0; x<temp.fields[i].length; x++) sb.append(temp.fields[i][x]);
                arr[i] = sb.toString();
            }
            return arr;
        }
        return null;
    }

    public LinkedList<LinkedList<String>> findByString(String s, int i) throws IOException {
        //PRE: i >= 0 and I < the number of character fields
         /*for each list item where the ith field matches s a list of
         the data in the node (key and character fields) is added to the list
         return by the method
         if no node has a match for s in the ith field return an empty list
         */
        LinkedList<LinkedList<String>> temp = new LinkedList<>();
        long addr = head;
        Node tempNode;
        String key;
        while(addr != 0){
            tempNode = new Node(addr);
            StringBuilder sb = new StringBuilder();
            for(int x=0; x<tempNode.fields[i].length; x++){
                if(tempNode.fields[i][x] != '\0'){
                    sb.append(tempNode.fields[i][x]);
                }
            }
            key = sb.toString();
            if(key.equals(s)){
                // Create LinkedList of String type that will
                // store the key and values in that node.
                LinkedList<String> nodeVals = new LinkedList<>();
                nodeVals.add(tempNode.key + "");
                for(int x=0; x<tempNode.fields.length; x++) nodeVals.add(new String(tempNode.fields[x]));
                // Add it to the list of those lists.
                temp.add(nodeVals);
            }
            addr = tempNode.next;
        }

        return temp;
    }

    public void remove(int k) throws IOException {
        //if k is in the list removed the items with key k from the list
        //otherwise do nothing
        // Find k in the list (start with the head)
        long prevAddr = head, currentAddr = head, next;
        if(head == 0)return;

        Node temp = new Node(currentAddr);
        if(temp.key == k){
            // node to be removed is at the head.
            addFree(head);
            head = temp.next;
            return;
        }

        while(temp.next != 0){
            currentAddr = temp.next;
            temp = new Node(currentAddr);
            if(temp.key == k) break;
            prevAddr = currentAddr;
        }

        // the loop can break because we ran out of list or we have found the key in the list
        if(temp.key == k){
            next = temp.next;
            temp = new Node(prevAddr);
            temp.next = next;
            temp.writeNode(prevAddr);
            addFree(currentAddr);
        }
    }

    public void close() throws IOException {
        //update head and free in the file (if necessary)
        //close the random access file
        f.seek(0);
        f.writeLong(head);
        f.writeLong(free);
        f.close();
    }

}