Sorting a Linked List in alphabetical order

» java » Sorting a Linked List in alphabetical order

By : NicoGagnon

Date : November 25 2020, 04:01 AM

around this issue 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).

code :

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

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;
}

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

Share :

Sorting the Visual Studio Function List drop down to code order instead of alphabetical order

By : Aliya

Date : March 29 2020, 07:55 AM

help you fix your problem I know thats this is not what you asking for, but you could try the VS10x CodeMap Visual Studio 2010 extension, it works the way you want.
But if you are very interested on changing the functionality of drop down list, i'm afraid that you would have to develop your own navigation bar.

Linked List manual Alphabetical sorting

By : user2550320

Date : March 29 2020, 07:55 AM

help you fix your problem Except that the sort does not work, I think your code is OK. For example,

code :

public static void main(String[] args) {
    Linked linked = new Linked();
    linked.add("data3");
    linked.add("data2");
    linked.add("data1");
    System.out.println( linked );

    System.out.println( linked.get(1) );
    System.out.println( linked.get(2) );
    System.out.println( linked.get(3) );
    System.out.println( linked.get(4) );
}

[data3][data2][data1]
data3
data2
data1
null

public void add(String data){
    Node linkedTemp = new Node(data);
    Node linkedCurrent = head;
    Node linkedPrev = head;
    while ( linkedCurrent != null ) {
        if ( linkedCurrent.getData() != null && linkedCurrent.getData().compareTo(data) > 0 ) {
            break;              
        }
        linkedPrev = linkedCurrent;
        linkedCurrent = linkedCurrent.getNext();
    }
    linkedTemp.setNext( linkedPrev.getNext() );
    linkedPrev.setNext(linkedTemp);
    listCount++;
}

[data1][data2][data3]
data1
data2
data3
null

Sorting a Linked List into alphabetical order

By : Rakesh Panda

Date : March 29 2020, 07:55 AM

should help you out You are accessing next without checking that it isn't null, and you aren't iterating through the list. Plus you should break after you've found it (unless you want to delete all instances and you should delete the node, as you will be leaking memory. Also, you won't be able to remove the very first element, as you never check it. You could add in a specific check for it as you need to handle changing the root node.

code :

if (A != nullptr && A->name == name)
{
    node *toBeDeleted = A;
    A = A->next;
    delete toBeDeleted;
    return;
}

while(curr && curr->next){
    if(curr->next->name == name){
        nextNode = curr->next;
        curr->next = nextNode->next;
        delete nextNode;
        break;
    }
    curr = curr->next;
}

void display()
{
    node *curr;
    curr = A;
    while(curr){
       cout << curr->name << endl;
       curr = curr->next;
    }
}

How do I sort a linked list in a alphabetical order in c

By : Vaugan

Date : March 29 2020, 07:55 AM

help you fix your problem After looking at the code once more I have optimized it to match the original intention of the @TenTen Peter. The outer loop is not needed. Sorting is done correctly:

code :

#include <stdlib.h>
#include <stdio.h>
#include <dirent.h>
#include <string.h>

// definition of the structure (global scope)
typedef struct  s_file
{
    char        *file_name;
    struct      s_file *next;
} t_file;

int static counter = 0;

void sort_alpha(t_file **begin_list)
{
  t_file    *list;
  char  *tmp;
  list = *begin_list;
  if (list)
    {
        while (list && list->next)
        {
            if (strcmp(list->file_name, list->next->file_name) > 0)
            {
                tmp = list->file_name;
                list->file_name = list->next->file_name;
                list->next->file_name = tmp;
                counter = counter + 1;
                printf("swap=%d\n",counter);
            }
        list = list->next;
        }
    }
}

int list_size(t_file **alst)
{
    int size = 0;
    t_file  *conductor;  // This will point to each node as it traverses the list
    conductor = *alst;      
    if ( conductor != 0 ) 
    {
        size = 1;
        while ( conductor->next != 0)
        {
            conductor = conductor->next;
            size = size + 1;
        }
     }
    return size;
}

void list_add(t_file **alst, t_file *newElement)
{
    printf("list_add->");
    if (newElement)
    {
         newElement->next = *alst;
         *alst = newElement;

        // Printing the added element
        printf("list_add:newElement=%s\n",(*alst)->file_name);

        // sorting:
        sort_alpha(alst); 
    }
    else
    {
        printf("NULL entry\n");
    }
}

t_file  *newEntry(char *file_name)
{
    t_file *file;
    file = (t_file *) malloc( sizeof(t_file) );
    printf("newEntry:file_name= %s\n",file_name);
    if (file)
    {
       file->file_name = file_name;
       file->next = NULL;
   }
   return (file);
}

// Untested
void read_dir(char *dir_name, t_file **begin_list)
{
    DIR *dir;   
    struct dirent *entry;
    dir = opendir(dir_name);
    if (!dir)
   {
        perror(dir_name);
        return;
   }
    while ((entry = readdir(dir)) != NULL){
        list_add(begin_list, newEntry(entry->d_name));
   }    
    closedir(dir);
}

int main(int ac, char **av)
{
    t_file *s,*iter,*e2,*e3,*e4,*e5,*e6,*e7;
    int j=0;

    printf("*Program Start*\n");        

    // Creating entries:
    s  = newEntry("dHea");
    e2 = newEntry("bbcx");
    e3 = newEntry("abcd");
    e4 = newEntry("cbcd");
    e5 = newEntry("cbad");
    e6 = newEntry("bbcd");
    e7 = newEntry("cbaa");

    // Adding entries to the list and sorting at the same time
    list_add(&s, e2);
    list_add(&s, e3);
    list_add(&s, e4);
    list_add(&s, e5);
    list_add(&s, e6);
    list_add(&s, e7);

    // It was done by:
    // read_dir(av[1], &s); // Untested

    // Print the sorted list
    iter = s;
    while (iter)
    {
        j++;
        printf("Printing sorted list: element %d = %s\n",j,iter->file_name);
        iter = iter->next;
    }

    printf("*Program End**\n");
    return 0;
}

*Program Start*
newEntry:file_name= dHea
newEntry:file_name= bbcx
newEntry:file_name= abcd
newEntry:file_name= cbcd
newEntry:file_name= cbad
newEntry:file_name= bbcd
newEntry:file_name= cbaa
list_add->list_add:newElement=bbcx
list_add->list_add:newElement=abcd
list_add->list_add:newElement=cbcd
swap=1
swap=2
list_add->list_add:newElement=cbad
swap=3
swap=4
list_add->list_add:newElement=bbcd
swap=5
list_add->list_add:newElement=cbaa
swap=6
swap=7
swap=8
Printing sorted list: element 1 = abcd
Printing sorted list: element 2 = bbcd
Printing sorted list: element 3 = bbcx
Printing sorted list: element 4 = cbaa
Printing sorted list: element 5 = cbad
Printing sorted list: element 6 = cbcd
Printing sorted list: element 7 = dHea
*Program End**

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int count = 0; 

int main(void) {

    char name[10][8], tname[10][8], temp[8];
    int i, j, n;

    printf("Enter the number of names\n");
    scanf("%d", &n);
    printf("Enter %d names\n", n);

    // reading names
    for (i = 0; i < n; i++)
    {
        scanf("%s", name[i]);
        strcpy(tname[i], name[i]);
    }

    // standard bubble sort  
    for (i = 0; i < n - 1 ; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (strcmp(name[i], name[j]) > 0)
            {
                strcpy(temp, name[i]);
                strcpy(name[i], name[j]);
                strcpy(name[j], temp);

                count = count + 1;
                printf("swap %d ", count);
            }
        }
    }

    // Print results:
    printf("\n----------------------------------------\n");
    printf("Input Names \tSorted names\n");
    printf("------------------------------------------\n");
    for (i = 0; i < n; i++)
    {
        printf("%s\t\t\t%s\n", tname[i], name[i]);
    }
    printf("------------------------------------------\n"); 
    return 0;
}

7 dHea bbcx abcd cbcd cbad bbcd cbaa

Enter the number of names
Enter 7 names
swap 1 swap 2 swap 3 swap 4 swap 5 swap 6 swap 7 swap 8 swap 9 swap 10 swap 11 swap 12 swap 13 
----------------------------------------
Input Names     Sorted names
------------------------------------------
dHea            abcd
bbcx            bbcd
abcd            bbcx
cbcd            cbaa
cbad            cbad
bbcd            cbcd
cbaa            dHea

Sorting doubly linked list alphabetical

By : user2315578

Date : March 29 2020, 07:55 AM

I hope this helps you . Sorting the list by swapping doubly linked nodes seems quite inefficient because you cannot use fast algorithms like merge sort.
You could instead use only the next links in a recursive merge sort function and reconstruct the back links on the resulting list.

code :

struct student {
    char Vorname[51];
    char Nachname[51];
    int MatNr;
    char Adresse[51];
    int Kurse;
    struct student *next;
    struct student *previous;
};

struct student *first = NULL;
struct student *last = NULL;

/* Merge two sorted lists. p1 and p2 are != NULL */
struct student *merge(struct student *p1, struct student *p2) {
    struct student *head, **pp;
    pp = &head;
    for (;;) {
        if (strcmp(p1->Nachname, p2->Nachname) <= 0) {
            *pp = p1;
            pp = &p1->next;
            p1 = p1->next;
            if (p1 == NULL) {
                *pp = p2;
                break;
            }
        } else {
            *pp = p2;
            pp = &p2->next;
            p2 = p2->next;
            if (p2 == NULL) {
                *pp = p1;
                break;
            }
        }
    }
    return head;
}

/* Recursive top-down merge sort */
struct student *msort(struct student *np) {
    struct student *p1, *p2;
    /* trivial lists are sorted */
    if (np == NULL || np->next == NULL)
        return np;
    /* locate mid-point using 2 finger method */
    for (p1 = np, p2 = np->next; p2 && p2->next; p2 = p2->next->next)
        p1 = p1->next;
    /* split the list at mid-point */
    p2 = p1->next;
    p1->next = NULL;
    p1 = np;
    /* sort the sublists recursively */
    p1 = msort(p1);
    p2 = msort(p2);
    return merge(p1, p2);
}

void sort(void) {
    struct student *p1, *p2;
    /* sort the list as a singly linked list */
    first = msort(first);
    /* reconstruct the backlinks */
    p1 = NULL;
    for (p2 = first; p2; p2 = p2->next) {
        p2->last = p1;
        p1 = p2;
    }
    last = p1;
}

/* bottom-up merge sort with sublist array */
struct student *msort(struct student *head) {
    struct student *array[32] = { NULL };
    int i;

    /* handle trivial lists */
    if (head == NULL || head->next == NULL)
        return head;

    i = 0;  /* avoid warning */
    p1 = head;
    /* merge nodes into pending lists of increasing lengths */
    while (head != NULL) {
        struct student *next = head->next;
        head->next = NULL;
        for (i = 0; i < 32 && array[i] != NULL; i++) {
            head = merge(array[i], head);
            array[i] = NULL;
        }
        /* do not go past end of array */
        if (i == 32)
            i--;
        array[i] = head;
        head = next;
    }
    /* merge pending lists into single list:
     * the last element stored into the array is at offset i and
     * all entries before it are NULL pointers. */
    for (head = array[i++]; i < 32; i++) {
        if (array[i] != NULL)
            head = merge(array[i], head);
    }
    return head;
}