Sorting a Linked List in alphabetical order

Question

I have an assignment where I have to make my one linked list that holds a person name and their vehicle plate number that enters in a compound. but I need to sort the list in alphabetical order by using the license plate number(example: ABS1234). I have been doing some research on sorting for example merge sort or using the collection.sort, but can't wrap my head around it. it will be awesome if I can get a little push on how to do this. Thanks in advance.

public class Node {
//data fields
public String regPlate; // Registration Plate
public String firstName;
public String lastName;

//refrence link
public Node link;

//default constructor
public Node()
{
    regPlate = "";
    firstName = "";
    lastName = "";
}//end of constructor.

}//end of node class

this is the Node class that i created.

public class LinkedList {

Node head;
Node tail;
Node current;
int listLength;
Scanner input = new Scanner(System.in);

//default constructor
public LinkedList () 
{
    head = null;
    listLength = 0;
}

//inserting new node in the beginning of the list
public void insertFirst(String fN, String lN, String rP)
{

    Node newNode = new Node();
    newNode.firstName = fN;
    newNode.lastName = lN;
    newNode.regPlate = rP;

    //make newNode point to the first node in the life
    newNode.link = head;

    //makes head point to the new first node
    head = newNode;

    if(head == null)
        tail = newNode;

    ++listLength;
}//end of insertFirst


public void displayDataLog()
{
    Node current;

    current = head;

    while(current != null)
    {
        System.out.print("\n FullName: " + current.firstName + " " + current.lastName +
                        "\n Registration Plate Number: " + current.regPlate);

        current = current.link;
    }

}//end of display vehicles

public void totalVehicles()
{
    System.out.print("\n Total Vehicle on the campus: " + listLength);
}//end of total vehicles


}//end of linked list

Answer 1

Using Collection.sort() this should be fairly easy.

First, you need to create your own Comparator, since the default one won't work (you want to order by a specific field, the license plate).

class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n1, Node n2) {
        return n1.regPlate.compareTo(n2.regPlate);
    }
}

---

Now you have your Comparator, just use it, here is an example I used (created an ArrayList and introduced every element of the list there):

private static LinkedList sortList(LinkedList list) {
    // I use an ArrayList so I can just use Collections.sort
    LinkedList sortedList = new LinkedList();
    Node current = list.head;
    ArrayList<Node> array = new ArrayList<Node>();

    while (current != null) {
        array.add(current);
        current = current.link;
    }
    array.sort(new NodeComparator());

    for (int i = array.size()-1; i >= 0; i--) {
        sortedList.insertFirst(array.get(i));
    }

    return sortedList;
}

I made a few changes that will, most likely, be easy to adapt to your own program. You can see the full working program here: https://code.sololearn.com/cgzN5sQOI8uW.

---

---

The entire the code, for the sake of completion (and just in case the link stops working):

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

class Playground {
    public static void main(String[ ] args) {
        LinkedList list = new LinkedList();
        list.insertFirst("Robert", "Rodriguez", "RB123");
        list.insertFirst("Andrew", "Andrews", "AB123");
        list.insertFirst("Thomas", "Thomson", "TB123");

        System.out.println(list); // Prints unordered list, opposite order as they were introduced, since they were introduced from the beggining of the list.

        LinkedList sorted = sortList(list);
        System.out.println("\n"+sorted);
    }

    private static LinkedList sortList(LinkedList list) {
        // I use an ArrayList so I can just use Collections.sort
        LinkedList sortedList = new LinkedList();
        Node current = list.head;
        ArrayList<Node> array = new ArrayList<Node>();

        while (current != null) {
            array.add(current);
            current = current.link;
        }
        System.out.println("\nTemp Array:");
        System.out.println(array);

        array.sort(new NodeComparator());

        System.out.println("\nTemp Array (now sorted):");
        System.out.println(array);

        for (int i = array.size()-1; i >= 0; i--) {
            sortedList.insertFirst(array.get(i));
        }

        return sortedList;
    }
}

class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n1, Node n2) {
        return n1.regPlate.compareTo(n2.regPlate);
    }
}

class Node {
    //data fields
    public String regPlate; // Registration Plate
    public String firstName;
    public String lastName;

    //refrence link
    public Node link;

    //default constructor
    public Node()
    {
        regPlate = "";
        firstName = "";
        lastName = "";
    }//end of constructor.

    public String toString() {
        return this.regPlate;
    }



}//end of node class

class LinkedList {

    Node head;
    Node tail;
    Node current;
    int listLength;

    //default constructor
    public LinkedList () 
    {
        head = null;
        listLength = 0;
    }

    //inserting new node in the beginning of the list
    public void insertFirst(String fN, String lN, String rP)
    {

        Node newNode = new Node();
        newNode.firstName = fN;
        newNode.lastName = lN;
        newNode.regPlate = rP;

        insertFirst(newNode);
    }//end of insertFirst

    public void insertFirst(Node newNode) {
        //make newNode point to the first node in the life
        newNode.link = head;

        //makes head point to the new first node
        head = newNode;

        if(head.link == null)
            tail = newNode;

        ++listLength;
    }

    public void displayDataLog()
    {
        Node current;

        current = head;

        while(current != null)
        {
            System.out.print("\n FullName: " + current.firstName + " " + current.lastName +
                            "\n Registration Plate Number: " + current.regPlate);

            current = current.link;
        }

    }//end of display vehicles

    public void totalVehicles()
    {
        System.out.print("\n Total Vehicle on the campus: " + listLength);
    }//end of total vehicles

    public String toString() {
        String str = "List:\nhead -> [ ";
        Node current = head;

        while (current != null) {
            str = str + current + (current == tail ? " ] <- tail" : ", ");
            current = current.link;
        }

        return str;
    }

}//end of linked list