I was tasked with creating my own linked list class, using a book class i made. One of the questions was to Determine the book that appears first alphabetically.

i was able to sort the Linked list alphabetically using bubble sort(i know its not efficient but im still new) here is the code.

public void alphaBubbleSort() {
    int size = size();

    if (size > 1) {
        boolean wasChanged;

        do {
            Node current = head;
            Node previous = null;
            Node next = head.next;
            wasChanged = false;
            while (next != null) {
                if (current.book.getName().compareToIgnoreCase(next.book.getName()) > 0) {

                    wasChanged = true;

                    if (previous != null) {
                        Node sig = next.next;

                        previous.next = next;
                        next.next = current;
                        current.next = sig;
                    } else {
                        Node temp = next.next;

                        head = next;
                        next.next = current;
                        current.next = temp;
                    }

                    previous = next;
                    next = current.next;
                } else {
                    previous = current;
                    current = next;
                    next = next.next;
                }
            }
        } while (wasChanged);
    }
}

my problem is i only want the front node and i do not want to alter the linked list order. i tried to do this in my main.

Linky tempLinky = new Linky(); // create temp linked list
           tempLinky = linky; // copy temp main linked list to temp
           tempLinky.alphaBubbleSort(); // sort temp list
           System.out.println(tempLinky.peek());// return object in first node

This did not seem to work. Ive tried some other code that does not work, so ive come here as a last resort.

CodePudding user response：

If you need to find the first book alphabetically, there's no need to sort the entire list (and, as you commented, you don't want to alter the list's order anyway).

Instead, you could iterate over the list and keep the "first" object as you go:

public Book getFirstAlphabetically() {
     Node current = head;
     Book retVal = head.book;
     while (current != null) {
         if (current.book.getName().compareToIgnoreCase(retVal.getName()) < 0) {
             retVal = current.book;
         }
         current = current.next;
     }
     return retVal;
}

CodePudding user response：

Here's an example:

import java.util.Random;

class Book {
    String title;
    Book(String title){this.title = title;}
}

class Node {
    Book b; Node next;
    Node(Book b){this.b = b;}
}

public class Main {

    static Book least(Node head){
        if (head == null) return null;
        Book least = head.b;
        for(Node n=head.next; n.next!=null; n=n.next)
            least = least.title.compareTo(n.b.title) > 0 ? n.b : least;
        return least;
    }
    
    static void print(Node head){        
        for(Node n=head; n.next!=null; n=n.next)
            System.out.println(n.b.title);
    }
    
    static String randString(){
        Random r = new Random();
        int len = r.nextInt(20) 1;
        char[] chars = new char[len];
        for(int i=0; i<chars.length; i  )
            chars[i]= (char) (r.nextInt(26) 97);
        return new String(chars);
    }
    
    public static void main(String[] args) {
        
        Node head = new Node(new Book(randString()));
        Node next = head;
        for(int i = 0; i<20; i  )
            next = next.next = new Node(new Book(randString()));
        
        print(head);
        System.out.println("==========");      
        System.out.println(least(head).title);

    }
}