it takes somewhat more than twice as much memorythe array and linked list must be in memory at the same time howeverif you have sorted linked list class handythe list insertion sort is convenient way to sort arrays that aren' too large doubly linked lists let' examine another variation on the linked listthe doubly linked list (not to be confused with the double-ended listwhat' the advantage of doubly linked lista potential problem with ordinary linked lists is that it' difficult to traverse backward along the list statement like current=current next steps conveniently to the next linkbut there' no corresponding way to go to the previous link depending on the applicationthis could pose problems for exampleimagine text editor in which linked list is used to store the text each text line on the screen is stored as string object embedded in link when the editor' user moves the cursor downward on the screenthe program steps to the next link to manipulate or display the new line but what happens if the user moves the cursor upwardin an ordinary linked listyou' need to return current (or its equivalentto the start of the list and then step all the way down again to the new current link this isn' very efficient you want to make single step upward the doubly linked list provides this capability it allows you to traverse backward as well as forward through the list the secret is that each link has two references to other links instead of one the first is to the next linkas in ordinary lists the second is to the previous link this is shown in figure the beginning of the specification for the link class in doubly linked list looks like thisclass link public double ddatapublic link nextpublic link previous/data item /next link in list /previous link in list figure doubly linked list the downside of doubly linked lists is that every time you insert or delete link you must deal with four links instead of twotwo attachments to the previous link and two attachments to the following one alsoof courseeach link is little bigger because of the extra reference doubly linked list doesn' necessarily need to be double-ended list (keeping