CODEWITHSUNDEEP
java
raay
raay

Reputation: 1

How to sum two double linked lists in one list efficiently?

For example listA = [3,6,7,4] and listB = [2,3,1] and the output has to be listC=[5,9,8,6]. This is what I have so far but it is not very efficient.

`public void sum(doublelist aList) {`
for (int i = 0; i < size(); i++) {
     set(i, this.get(i) + other.get(i % other.size()));
}
}

Upvotes: 0

Views: 192

Answers (2)

Erwan Daniel
Erwan Daniel

Reputation: 1537

The answer is totally dependent of what kind of List you are using.

But anyway, the best complexity you can get is O(n), you will have to iterate at least one time over each element of the lists.

The easiest is to use a ListIterator, that allow to set a value while iterating over the list.

    void sum(List<Integer> l1, List<Integer> l2) {
        final ListIterator<Integer> it1 = l1.listIterator();
        final Iterator<Integer> it2 = l2.iterator();
        
        while (it1.hasNext() && it2.hasNext()) {
            it1.set(it1.next() + it2.next());
        }
    }

Upvotes: 0

dan1st
dan1st

Reputation: 16348

As you said you are using linked lists, you could navigate from element to element:

public void sum(DoubleList aList){
    DoubleNode cur=this.head;
    DoubleNode other=aList.head;
    while(cur!=null){
        cur.setValue(cur.getValue()+other.getValue());
        other=other.getNext();
        if(other==null){
            other=aList.head;
        }
        cur=cur.getNext();
    }
}

This code assumes that your DoubleList contains a head node attribute named head from the type DoubleNode and DoubleNode has the methods double getValue()/void setValue(double value) for accessing the value and DoubleNode getNext() for retrieving the next element.

This should be more efficient as you don't have to query the list every time (O(n) instead of O(n^2)).

Upvotes: 2

Related Questions