Differences implementing Singly vs Doubly linked list for the Multiplication of two polynomials

Whats the differences implementing Singly linked list or Doubly linked list for the Multiplication of two polynomials.

And Especially I am trying for implementing program to multiply two polynomials using doubly linked list.

An algorithm or a workable program using any of these c, c++, java, c#, vb.net languages would be very nice of you.

I think this is wh开发者_StackOverflowat would it could be SO question, but this is only in Singly Linked List..

---

Here's a JavaScript for multiplying using SLL.

var x0 = {rank: 0, value: 11};
var x1 = {rank: 1, value: 5};
var x2 = {rank: 2, value: 7};
/* 11 + 5x + 7x^2 */

var SLL = {data: x0, next: {data: x1, next: {data: x2, next: null}}};

var DLL = {data: x0, prev: null, next: null};
 DLL.next = {data: x1, prev: DLL, next: null};
 DLL.next.next = {data: x2, prev: DLL.next, next: null};

function mulSLL(a, b) {
 var result = null;
 var m1 = a;
 while(m1 != null) {
  var m2 = b;
  var mr = result; //re-use pointer into result
  while(m2 != null) {
   var val = {rank: m1.data.rank + m2.data.rank, value: m1.data.value * m2.data.value};
   if(result == null) { //initial create
    result = {data: val, next: null};
   } else {
    var mrold = null;
    while(mr != null && mr.data.rank < val.rank) {
     mrold = mr;
     mr = mr.next;
    }
    if(mr != null) {
     if(mr.data.rank == val.rank) { //merge
      mr.data.value += val.value;
     } else { // insert
      var mrnext = mr.next;
      mr.next = {data: val, next: mrnext};
     }
    } else { // add
     mrold.next = {data: val, next: null};
    }
   }
   m2 = m2.next; 
  }
  m1 = m1.next;
 }
 // output result
 mr = result;
 while(mr != null) {
  console.log(' + ' + mr.data.value + 'x^' + mr.data.rank);
  mr = mr.next;
 } 
 return result;
}

mulSSL(SLL,SLL);

• Edit * cleaned up the code a bit

You'll notice that most of the logic happens building the result. Since my inputs are sorted from lowest rank to highest we really wouldn't gain much using a DLL approach instead of SLL. I think the major difference is the amount of memory (DLL would take up an extra pointer worth of space 'prev' for each node. Now if the inputs were NOT sorted by 'rank' (read: power) then using a DLL result would allow us to start at the last inserted node and move to 'prev' or 'next' based on the 'rank' comparison.

---

If you have specified a polynomial using a linked list. It shouldn't make any difference whether its singly or doubly linked. If you are building another polynomial like this there may be a small advantage using a doubly linked list.

However, if performance were an issue, you wouldn't use a linked list at all, you would use a vector or an array.