Java程序辅导

  
 
CPSC 225: Intermediate Programming  •  Spring 2022 20
Lab 6
• pattern for moving through a linked list
– finger starts at the head and repeatedly moves to the next node
for ( ListNode current = head ; current != null ; 
      current = current.getNext() ) {
  …
}
“keep going” condition 
may vary
CPSC 225: Intermediate Programming  •  Spring 2022 21
Lab 6 – removeAtHead
• any node is the head of the list from that node on
– nodes don't know what links to them, or whether or not they are 
the first node
• removing often means just forgetting about / not looking 
at again
– Java doesn't require deallocation of old objects – no longer 
accessible objects are automatically cleaned up by the garbage 
collector
newhead
CPSC 225: Intermediate Programming  •  Spring 2022 22
Variations on Linked Lists
• tail pointers
– speed up access/insert at end by maintaining both head and tail 
pointers
CPSC 225: Intermediate Programming  •  Spring 2022 23
Variations on Linked Lists
• doubly-linked list
– speed up insert, remove, remove at tail – anything that involves 
a node before – by having node store next and previous 
pointers
  
 
CPSC 225: Intermediate Programming  •  Spring 2022 24
Variations on Linked Lists
• circular list
– tail's next points back to the head instead of being null
– can reduce special cases for handling first and last nodes
• get the benefits of a tail pointer with only a single pointer
– convenient for round-robin scheduling