Chapter 20 - Lists and iterators. In this and the following chapter we start looking at the implementation details of data structures. This chapter’s objectives are to: Learn to work with ListNode objects and do-it-yourself linked lists; understand singly-linked list, linked list with a tail, circular list, and doubly-linked list; learn to implement iterators. | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Lists and Iterators 20- In this and the following chapter we start looking at the implementation details of data structures. Objectives: Learn to work with ListNode objects and do-it-yourself linked lists Understand singly-linked list, linked list with a tail, circular list, and doubly-linked list Learn to implement iterators 20- The AP CS course description indicates that students must be familiar with the interface and and LinkedList classes, as well as with manipulating “do-it-yourself” linked lists based on the College Board’s ListNode class. Singly-Linked List Each node holds a reference to the next node In the last node, next is null A linked list is defined by a reference to its first node (often named head or front) value 0 value 1 value 2 value . | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Lists and Iterators 20- In this and the following chapter we start looking at the implementation details of data structures. Objectives: Learn to work with ListNode objects and do-it-yourself linked lists Understand singly-linked list, linked list with a tail, circular list, and doubly-linked list Learn to implement iterators 20- The AP CS course description indicates that students must be familiar with the interface and and LinkedList classes, as well as with manipulating “do-it-yourself” linked lists based on the College Board’s ListNode class. Singly-Linked List Each node holds a reference to the next node In the last node, next is null A linked list is defined by a reference to its first node (often named head or front) value 0 value 1 value 2 value . value n-1 head 20- head is a variable that holds a reference to the first node of the linked list. Its type is ListNode. Singly-Linked List (cont’d) public class ListNode { private Object value; private ListNode next; 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 node Represents a node of a singly-linked list 20- It would be reasonable to provide the second constructor to ListNode: ListNode(Object v) { value = v; next = null; } Singly-Linked List — Example 1 Append 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 0 value 1 value 2 value . value n-1 x head 20- This code is terse. Basically it is the same as public ListNode .
