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

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]`? — Naman, Jun 13 '19 at 02:17
output must be `2->3->1->0->1->3->4->4->5->8->7->6` compare right element and add new element in left — Srikar Karthik, Jun 13 '19 at 03:22
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, Jun 13 '19 at 03:52
A relevant link for a warning related to the above code about the object allocation within a loop via lambdas -https://stackoverflow.com/questions/27524445/does-a-lambda-expression-create-an-object-on-the-heap-every-time-its-executed — Naman, Jun 13 '19 at 03:56
Thank you @Naman ,That's the exact solution what i have been looking for. — Srikar Karthik, Jun 14 '19 at 21:03

Holger · Answer 1 · 2019-06-13T11:50:40.243

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.

score 0 · Answer 2 · answered Jun 13 '19 at 09:54

0

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]

answered Jun 13 '19 at 09:54

Rowi

545
3
9

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);` – Holger Jun 13 '19 at 11:42

score 0 · Answer 3 · answered Jun 13 '19 at 10:59

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]

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`. — Holger, Jun 13 '19 at 11:24

score 0 · Answer 4 · answered Jun 13 '19 at 11:10

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.

Srikar Karthik · Accepted Answer · 2019-06-16T01:37:09.053

0

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

edited Jun 16 '19 at 01:37

answered Jun 14 '19 at 21:04

Srikar Karthik

23
4

I posted code snippet for the same code implementation but using Java 8 syntax. – Srikar Karthik Jun 16 '19 at 01:38

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

5 Answers5