Kĩ thuật lập trình - Lists and Iterators

Lists and IteratorsCopyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Learn to work with ListNode objects and do-it-yourself linked listsUnderstand singly-linked list, linked list with a tail, circular list, and doubly-linked listLearn to implement iterators2Singly-Linked ListEach node holds a reference to the next nodeIn the last node, next is nullA linked list is defined by a reference to its first node (often named head or front)value 0value 1value 2value ...value n-1head3Singly-Linked List (cont’d)public class ListNode{ private Object value; private ListNode next; public ListNode (Object v) { value = v; next = null; } public ListNode (Object v, ListNode nx) { value = v; next = nx; } public Object getValue ( ) { return value; } public ListNode getNext ( ) { return next; } public void setValue (Object v) { value = v; } public void setNext (ListNode nx) { next = nx; }}A reference to the next nodeRepresents a node of a singly-linked list4Singly-Linked List — Example 1Append x at the head of a linked list and return the head of the new list. public ListNode append (ListNode head, Object x) { return new ListNode (value, head); }value 0value 1value 2value ...value n-1 xhead5Singly-Linked List — Example 2 Assuming the list has at least two nodes, remove the last node. public void removeLast (ListNode head) { ListNode node = head; while (node.getNext ().getNext () != null) node = node.getNext ( ); node.setNext (null); }nullnullABCDnodehead6Singly-Linked List — Traversal public void printList (ListNode head) { for (ListNode node = head; node != null; node = node.getNext ( )) System.out.println (node.getValue ()); }7Do-it-Yourself Iterator public class SinglyLinkedList implements Iterable{ private ListNode head; ... public Iterator iterator () { return new SinglyLinkedListIterator (head); } ...}8Do-it-Yourself Iterator (cont’d)public class SinglyLinkedListIterator implements Iterator{ private ListNode nextNode; public SinglyLinkedListIterator (ListNode head) { nextNode = head; } public boolean hasNext ( ) { return nextNode != null; } public Object next ( ) { if (nextNode == null) throw new NoSuchElementException ( ); Object obj = nextNode.getValue ( ); nextNode = nextNode.getNext ( ); return obj; } ...} public void remove ( ) { throw new UnsupportedOperationException( ); }9Singly-Linked List with a TailKeeps a reference to the last nodeSuitable for implementing a queuevalue 0value 1value 2value ...value n-1headtail10Doubly-Linked ListEach node has references to the next and previous nodesIn the last node, next is null; in the first node, previous is null.Can be traversed backwardsa0a1a2an-1...headtail11Doubly-Linked Circular Listnext in the last node points to the first nodeprevious in the first node points to the last nodea0a1a2an-1...head12Doubly-Linked Circular List with a Header NodeThat’s how java.util.LinkedList is implementeda0a1a2an-1... private ListNode2 header; a field in the DoublyLinkedList class13Review:What does an object of the ListNode class represent?Which fields and methods have to be added to ListNode to make it suitable for doubly-linked lists?What is a circular list?In an empty circular list with a header node, what are the values of next and previous in header?14