tailieunhanh - Lecture Data structures and algorithms in Java (6th edition): Chapter 3.3 - Goodrich, Tamassia, Goldwasser

In this section, we introduce a data structure known as a linked list, which provides an alternative to an array-based structure. A linked list, in its simplest form, is a collection of nodes that collectively form a linear sequence. In a singly linked list, each node stores a reference to an object that is an element of the sequence, as well as a reference to the next node of the list. | Singly 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 Singly Linked Lists © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 1 Singly Linked List ! A singly linked list is a concrete data structure consisting of a sequence of nodes, starting from a head pointer ! Each node stores n   head n   next element node element link to the next node ∅ A B © 2014 Goodrich, Tamassia, Goldwasser C Singly Linked Lists D 2 1 Singly Linked Lists 3/18/14 A Nested Node Class © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 3 Accessor Methods © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 4 2 Singly Linked Lists 3/18/14 Inserting at the Head •  Allocate new node •  Insert new element •  Have new node point to old head •  Update head to point to new node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 5 Inserting at the Tail •  Allocate a new node •  Insert new element •  Have new node point to null •  Have old last node point to new node •  Update tail to point to new node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 6 3 Singly Linked Lists 3/18/14 Java Methods © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 7 Removing at the Head •  Update head to point to next node in the list •  Allow garbage collector to reclaim the former first node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 8 4 Singly Linked Lists 3/18/14 Java Method © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 9 Removing at the Tail •  Removing at the tail of a singly linked list is not efficient! •  There is no constant-time way to update the tail to point to the previous node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked .