Compare Array List with Linked List by adding element into linked list using Java 8

Question

I am comparing the ArrayList and LinkedList. For eg:

ArrayList => {2,4,5}
LinkedList => 1->3->8->7->6
Final Output => 1->2->3->4->5->8->7->6

I need elements from array list to be compared with elements in linked list and need to insert such that the final linked list is inserted in sorted order using JAVA 8 Streams/Filter/Map/Collections... (I have no idea)
Do not change the order of already existing elements ( in above example 8->7->6 did not change order)

I tried using simple Core java by using two for loops to compare and insert into linked list

 for(int i=0;i<arrayList.size();i++){
 for(int j=0;j<linkedList.size();j++){
 if(linkedList.get(j)>arrayList.get(i)){
 linkedList.add(j,arrayList.get(i));
 break;
 }
 }
 }

I need code replacement in Java 8 using streams, maps, filters, collections.. etc

• Naman: What happens to the merge(result) that you're performing if let's say the inputs are LinkedList [3,1,0,1,3,4,8,7,6] and ArrayList [2,4,5]?
• Srikar Karthik: output must be 2->3->1->0->1->3->4->4->5->8->7->6 compare right element and add new element in left
• Naman: So duplicate the elements even if they exist and add before the first element which is greater than the current element. Interesting, closest I could cut it short to was for (Integer integer : arrayList) { IntStream.range(0, linkedList.size()) .filter(j -> linkedList.get(j) > integer) .findFirst() .ifPresent(j -> linkedList.add(j, integer)); }, but I doubt the improvement both in terms of readability or performance here.
• Naman: A relevant link for a warning related to the above code about the object allocation within a loop via lambdas -stackoverflow.com/questions/27524445/…
• Srikar Karthik: Thank you @Naman ,That's the exact solution what i have been looking for.

Answer 1

There are some weird requirements in your task. First, the logic can be entirely described in terms of lists, there is no need to mandate that one list must be an ArrayList and the other a LinkedList.

It’s also not useful to require the use of the Stream API for a task, especially for a task that unsuitable for the Stream API.

It would make more sense, if the LinkedList was mandated with the intention of utilizing its capability of cheap insertions at arbitrary positions. This advantage can only be played when using an iterator for that, with LinkedList, all index based access methods are actually downgrading the performance.

Such a solution could look like

// prerequisites
List<Integer> arrayList = new ArrayList<>(Arrays.asList(2,4,5));
List<Integer> linkedList = new LinkedList<>(Arrays.asList(1,3,8,7,6));
// changing linkedList
ListIterator<Integer> iterator = linkedList.listIterator();
for(Integer i: arrayList) {
 while(iterator.hasNext()) {
 if(iterator.next() > i) {
 iterator.previous();
 break;
 }
 }
 iterator.add(i);
}
// 1->2->3->4->5->8->7->6
System.out.println(linkedList.stream()
 .map(Object::toString).collect(Collectors.joining("->")));

This is tailored to the LinkedList as it avoids iterating it multiple times while inserting at positions already linked by the iterator.

This logic can not be expressed with the Stream API, at least not without violating some of its rules. Read Non-interference and Stateless behaviors for more details.

Answer 2

You can try this..

List<Integer> arrayList = new ArrayList<>(Arrays.asList(1,3,8,7,6));
List<Integer> linkedList = new LinkedList<>(Arrays.asList(2,4,5)); 
arrayList.stream().forEach(linkedList::add); 
Collections.sort(linkedList);
System.out.println(linkedList);

Out Put would be like>> [1, 2, 3, 4, 5, 6, 7, 8]

• Holger: But the output is supposed to be [1, 2, 3, 4, 5, 8, 7, 6] Further, arrayList.stream().forEach(linkedList::add); is just a complicated way to do the same as linkedList.addAll(arrayList);

Answer 3

Below code is just to achieve the requirement. This may not be the good way of stream usage. But achieves the result. Hope It helps.

 public static void main(String[] args) {
 List<Integer> arrayList = new ArrayList<>();
 List<Integer> linkedList = new LinkedList<>();
 arrayList.add(2);
 arrayList.add(4);
 arrayList.add(5);
 linkedList.add(1);
 linkedList.add(3);
 linkedList.add(8);
 linkedList.add(7);
 linkedList.add(6);
 arrayList.stream().forEach((l) -> {
 final ReadOnlyBooleanWrapper br = new ReadOnlyBooleanWrapper(true);
 IntStream.range(0, linkedList.size()).forEach(jIdx -> {
 if (linkedList.get(jIdx) > l && br.get()) {
 linkedList.add(jIdx, l);
 br.set(false);
 }
 });
 }
 );
 System.out.println(linkedList);
 }

O/P : [1, 2, 3, 4, 5, 8, 7, 6]

• Holger: When you use a non-standard class like ReadOnlyBooleanWrapper, you should include it in your answer. Apparently, that class contradicts its name as you are modifying the "read only" wrapper. Besides that, it’s a horribly kludge. If you want to act on the first occurrence of a match, just use findFirst instead of forEach.

Answer 4

ArrayList => {2,4,5}
LinkedList => 1->3->8->7->6

It makes sense to work using "decreasing / not-increasing / ..." sublists:

ArrayList => [[2],[4],[5]]
LinkedList => [[1],[3],[8,7,6]]

Now the merging is straight-forward.

Indeed no actual sublists are needed, arriving at AL 5, LL 8 one continues 8,7,6 until the next larger than 8 element is found: 8,7,4,6,9] would be [[8,7,4,6],[9]].

The rest of the home work is your job.

Answer 5

As described in my question post, all I need was the same implementation of specified problem using Java 8 syntax (ie., using streams, filters, etc.,)

for (Integer integer : arrayList) { 
 IntStream.range(0, linkedList.size()) 
 .filter(j -> linkedList.get(j) > integer) 
 .findFirst() 
 .ifPresent(j -> linkedList.add(j, integer)); 
}

• Srikar Karthik: I posted code snippet for the same code implementation but using Java 8 syntax.