I am needing to sort a linked list alphabetically. I have a Linked List full of passengers names and need the passengers name to be sorted alphabetically. How would one do this? Anyone have any references or videos?
1
-
Note that list.sort() is implemented by copying the list to an array, sorting the array, then copying the array back into the list, so it is not a true list sort such as C++ std::list::sort().rcgldr– rcgldr2024-10-17 16:43:19 +00:00Commented Oct 17, 2024 at 16:43
Add a comment
|
10 Answers
You can use Collections#sort to sort things alphabetically.
3 Comments
Matt Ball
If it's a
List<String> there's no need for a custom comparator.
allencoded
humm collections.sort cool. public static LinkedList<String> NameList1 = new LinkedList<String>(); is what I am trying to sort. Thanks
mre
@allencoded, all you need to do is
Collections.sort(NameList1);, and then your list will be sorted alphabetically.In order to sort Strings alphabetically you will need to use a Collator, like:
LinkedList<String> list = new LinkedList<String>();
list.add("abc");
list.add("Bcd");
list.add("aAb");
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return Collator.getInstance().compare(o1, o2);
}
});
Because if you just call Collections.sort(list) you will have trouble with strings that contain uppercase characters.
For instance in the code I pasted, after the sorting the list will be: [aAb, abc, Bcd] but if you just call Collections.sort(list); you will get: [Bcd, aAb, abc]
Note: When using a Collator you can specify the locale Collator.getInstance(Locale.ENGLISH) this is usually pretty handy.
5 Comments
mre
interesting...I was unaware that the sorting of strings was sensitive to upper/lower casing...
Paŭlo Ebermann
Better invoke
getInstance() only once, not once for each compare call. (I just saw that Collator implements Comparator<Object> instead of Comparator<String>. Bah.)
Federico Vera
@Paülo: you are right, but the idea was to create a simple code to paste (not the most efficient one). The perfect scenario (if you sort all the time) will be a static reference to Comparator.getInstance()
Federico Vera
@mre yeahp, this usually create some nasty behavior when users enter their own name in the system (some use uppercase, some lowercase) and lists are never properly sorted.
Maksim
Or: Collections.sort(list, (o1, o2) -> Collator.getInstance().compare(o1, o2));
In java8 you no longer need to use Collections.sort method as LinkedList inherits the method sort from java.util.List, so adapting Fido's answer to Java8:
LinkedList<String>list = new LinkedList<String>();
list.add("abc");
list.add("Bcd");
list.add("aAb");
list.sort( new Comparator<String>(){
@Override
public int compare(String o1,String o2){
return Collator.getInstance().compare(o1,o2);
}
});
References:
http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
http://docs.oracle.com/javase/7/docs/api/java/util/List.html
1 Comment
Dávid Horváth
In java8 you can use a lambda too:
list.sort((a, b) -> Collator.getInstance().compare(a, b)). Sadly, list::sort does not support natural sorting without an explicit Comparator.Elegant solution since JAVA 8:
LinkedList<String>list = new LinkedList<String>();
list.add("abc");
list.add("Bcd");
list.add("aAb");
list.sort(String::compareToIgnoreCase);
Another option would be using lambda expressions:
list.sort((o1, o2) -> o1.compareToIgnoreCase(o2));
Comments
Node mergeSort(Node head) {
if(head == null || head.next == null) {
return head;
}
Node middle = middleElement(head);
Node nextofMiddle = middle.next;
middle.next = null;
Node left = mergeSort(head);
Node right = mergeSort(nextofMiddle);
Node sortdList = merge(left, right);
return sortdList;
}
Node merge(Node left, Node right) {
if(left == null) {
return right;
}
if(right == null) {
return left;
}
Node temp = null;
if(left.data < right.data) {
temp = left;
temp.next = merge(left.next, right);
} else {
temp = right;
temp.next = merge(left, right.next);
}
return temp;
}
Node middleElement(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
Comments
Here is the example to sort implemented linked list in java without using any standard java libraries.
package SelFrDemo;
class NodeeSort {
Object value;
NodeeSort next;
NodeeSort(Object val) {
value = val;
next = null;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public NodeeSort getNext() {
return next;
}
public void setNext(NodeeSort next) {
this.next = next;
}
}
public class SortLinkList {
NodeeSort head;
int size = 0;
NodeeSort add(Object val) {
// TODO Auto-generated method stub
if (head == null) {
NodeeSort nodee = new NodeeSort(val);
head = nodee;
size++;
return head;
}
NodeeSort temp = head;
while (temp.next != null) {
temp = temp.next;
}
NodeeSort newNode = new NodeeSort(val);
temp.setNext(newNode);
newNode.setNext(null);
size++;
return head;
}
NodeeSort sort(NodeeSort nodeSort) {
for (int i = size - 1; i >= 1; i--) {
NodeeSort finalval = nodeSort;
NodeeSort tempNode = nodeSort;
for (int j = 0; j < i; j++) {
int val1 = (int) nodeSort.value;
NodeeSort nextnode = nodeSort.next;
int val2 = (int) nextnode.value;
if (val1 > val2) {
if (nodeSort.next.next != null) {
NodeeSort CurrentNext = nodeSort.next.next;
nextnode.next = nodeSort;
nextnode.next.next = CurrentNext;
if (j == 0) {
finalval = nextnode;
} else
nodeSort = nextnode;
for (int l = 1; l < j; l++) {
tempNode = tempNode.next;
}
if (j != 0) {
tempNode.next = nextnode;
nodeSort = tempNode;
}
} else if (nodeSort.next.next == null) {
nextnode.next = nodeSort;
nextnode.next.next = null;
for (int l = 1; l < j; l++) {
tempNode = tempNode.next;
}
tempNode.next = nextnode;
nextnode = tempNode;
nodeSort = tempNode;
}
} else
nodeSort = tempNode;
nodeSort = finalval;
tempNode = nodeSort;
for (int k = 0; k <= j && j < i - 1; k++) {
nodeSort = nodeSort.next;
}
}
}
return nodeSort;
}
public static void main(String[] args) {
SortLinkList objsort = new SortLinkList();
NodeeSort nl1 = objsort.add(9);
NodeeSort nl2 = objsort.add(71);
NodeeSort nl3 = objsort.add(6);
NodeeSort nl4 = objsort.add(81);
NodeeSort nl5 = objsort.add(2);
NodeeSort NodeSort = nl5;
NodeeSort finalsort = objsort.sort(NodeSort);
while (finalsort != null) {
System.out.println(finalsort.getValue());
finalsort = finalsort.getNext();
}
}
}
Comments
I wouldn't. I would use an ArrayList or a sorted collection with a Comparator. Sorting a LinkedList is about the most inefficient procedure I can think of.
3 Comments
Paŭlo Ebermann
Collections.sort uses a workaround there: it copies the contents to an array, sorts the array and copies it back. This will not take much longer than for an ArrayList.
nawfal
May be it's true, but that's still an implementation detail. EJP's answer makes sense as it warns of the potential danger of using a wrong data structure. Makes sense, +1.
user207421
@Ilya_Gazman If that's addressed to me, it's not what the question is about.
You can do it by Java 8 lambda expression :
LinkedList<String> list=new LinkedList<String>();
list.add("bgh");
list.add("asd");
list.add("new");
//lambda expression
list.sort((a,b)->a.compareTo(b));
1 Comment
rcgldr
Note that list.sort() is implemented by copying the list to an array, sorting the array, then copying the array back into the list, so it is not a true list sort such as C++ std::list::sort().
//Simple sorting algorithm to sort linked list data structure
public void sortLinkedListDS() {
Node cur = front;
Node prev;
int temp = 0; // to hold prev data
for (; cur != null;) {
prev = cur.next;
for (; prev != null;) {
if (cur.data > prev.data) {
temp = cur.data;
cur.data = prev.data;
prev.data = temp;
}
prev = prev.next;
}
cur = cur.next;
}
}
Comments
If you'd like to know how to sort a linked list without using standard Java libraries, I'd suggest looking at different algorithms yourself. Examples here show how to implement an insertion sort, another StackOverflow post shows a merge sort, and ehow even gives some examples on how to create a custom compare function in case you want to further customize your sort.
