Chapter 3, Problem 26C

Algorithm to concatenate two doubly linked list:

The algorithm to concatenate two doubly linked list “L” and “M” into single list “L^'” is given below:

Algorithm:

Input: Two doubly linked list “L” and “M”.

Output: Concatenate the two doubly linked lists into single list “L^'”.

Concatenate(L, M):

  //Create new nodes

  Create a new node "n" and "v"

/*Get previous node for trailer of list "L" using getPrev() method and assign into "n". */

  n = (L.getTrailer()).getPrev()

/*Get next node for header of list "M" using getNext() method and assign into "v" */

  v = (M.getHeader()).getNext()

// Set next node for header of list "M" as "null"

  (M.getHeader()).setNext(null)

//Set previous node for trailer of list "L" as "null"

  (L.getTrailer()).setPrev(null)

/*Call setNext() method by passing the "v" node to set the next node as "v". */

  n.setNext(v)

/*Call setPrev() method by passing the "n" node to set the previous node as "n". */

  v.setPrev(n)

  //Assign the concatenated list into single list "L^'"

  L^' = L

/*Set trailer for list "L^'" by calling setTrailer() method by passing parameter as "trailer of list "M"...