To provide greater symmetry, we define a linked list in which each node keeps an explicit reference to the node before it and a reference to the node after it. Such a structure is known as a doubly linked list. These lists allow a greater variety of O(1)-time update operations, including insertions and deletions at arbitrary positions within the list. | Doubly Linked Lists 3/18/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Doubly Linked Lists © 2014 Goodrich, Tamassia, Goldwasser Doubly Linked Lists 1 Doubly Linked List q q A doubly linked list can be traversed forward and backward Nodes store: n n n q element link to the previous node link to the next node prev next element node Special trailer and header nodes nodes/positions header trailer elements © 2014 Goodrich, Tamassia, Goldwasser Doubly Linked Lists 2 1 Doubly Linked Lists 3/18/14 Insertion q Insert a new node, q, between p and its successor. p A B C p A q B C X p A © 2014 Goodrich, Tamassia, Goldwasser q B X C Doubly Linked Lists 3 Deletion q Remove a node, p, from a doubly linked list. A B C A B C p D p D A © 2014 Goodrich, Tamassia, Goldwasser B Doubly Linked Lists C 4 2 Doubly Linked Lists 3/18/14 Doubly-Linked List in Java © 2014 Goodrich, Tamassia, Goldwasser Doubly Linked Lists 5 Doubly-Linked List in Java, 2 © 2014 Goodrich, Tamassia, Goldwasser Doubly Linked Lists 6 3 Doubly Linked Lists 3/18/14 Doubly-Linked List in Java, 3 © 2014 Goodrich, Tamassia, Goldwasser Doubly Linked Lists 7 Doubly-Linked List in Java, 4 © 2014 Goodrich, Tamassia, Goldwasser Doubly Linked .
