CODEWITHSUNDEEP
javaalgorithmsortinglinked-list
kaann45
kaann45

Reputation: 31

How to order string data of LinkedList

How can I order a LinkedList that includes string type {a,c,d,b,b,d,c,a,c}. After ordering the output should be like this {c,c,c,a,a,d,d,b,b}. Also the complexity should be O(1*n).

Upvotes: 0

Views: 119

Answers (3)

Anonymous
Anonymous

Reputation: 86272

I am assuming that the groups/names/items are always four and always c, a, d and b. Under this assumption it is easy: Create four lists, one for the c items, one for the a items, etc. Traverse your linked list; for each item append it to the appropriate new list. You may use switch on the strings. Finally append the four new lists in the right order.

This will take O(n) time and O(n) space.

If for some reason (I don’t know what it could be) you don’t want to create four lists, just keep four references to the four places in the sorted list where the c, a, d and b items should be inserted. This will require a decision about where to point as long as not all four names are in the list yet, though.

Upvotes: 1

mpiatek
mpiatek

Reputation: 13

If you are using Java 8, you can use stream(). Look the following code:

Sorting your data with this:

linkedList.stream().sorted().collect(Collectors.toList())

or you can reverse sorted collection with this:

linkedList.stream().sorted(Collections.reverseOrder()).collect(Collectors.toList())

Upvotes: 0

nice_dev
nice_dev

Reputation: 17805

This is for inventory managemant system. There are 4 type dataname a,b,c and d

So, you need to add that in your post(also explain the scenario if possible).

Algorithm

  • Since you said there are only 4 types of data, maintain 8 variables - 2 per type of data for nodes a,b,c,d as shown below. 
Node head_c = null,tail_c = null;
Node head_a = null,tail_a = null;
Node head_d = null,tail_d = null;
Node head_b = null,tail_b = null;
  • Now, iterate over the linked list and whenever you get a c, do like below.
if(head_c == null){
   head_c = current_node;
}else{
   tail_c.next = current_node;
}
tail_c = current_node;

  • Do the same as above for other nodes a,d,b too. What we are trying to do here is basically creating 4 individual lists c,a,d,b separately using the same(same hashCode) nodes of the linked list.

  • Now, as you might have understood, all have to do is assigning one's tail to another list's head for each of the lists. See below. 

main_head = head_c;
tail_c.next = head_a;
tail_a.next = head_d;
tail_d.next = head_b;
tail_b.next = null;
  • So, you got the grouping of c,a,d,b you need.
  • Time Complexity- O(n) , Space Complexity is O(1).

Upvotes: 1

Related Questions