Doubly Linked list to a Singly Linked list
  • timecomplexity
  • doublylinkedlist
  • stackqueuelinkedlist
  • singlylinkedlist
  •   
  • Posted: 7 years ago
  • Edit
  • answers (1)
  • views (2753)

Write a function that takes a doubly linked list and creates an equivalent singly linked list.


Posted Answers



  • Create a new singly linked list.
  • Remove the last element of the doubly linked list and add it at the beginning of the singly linked list.
  • Repeat the last step until the doubly linked list is empty.


SinglyLinkedList doubleToSingle(DoublyLinkedList DL){
SinglyLinkedList SL = new SinglyLinkedList();
while(!DL == isEmpty())
SL.addFirst(DL.removeLast());
return SL;
}


The while loop executes \( n \) times as \( removeLast() \) takes \( O(1) \) time on a doubly linkedlist, but \( O(n) \) time on a singly linkedlist.
\( \therefore \) Running time = \( O(n) \).

You need to Sign In to post your solution.