tailieunhanh - Lecture Java methods: Object-oriented programming and data structures (3rd AP edition): Chapter 21 - Maria Litvin, Gary Litvin

Chapter 21 - 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. | Lists and Iterators Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition 21- 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 21- The ListNode class used to be tested in now defunct AP Computer Science AB exams. 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 21- 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 | Lists and Iterators Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition 21- 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 21- The ListNode class used to be tested in now defunct AP Computer Science AB exams. 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 21- 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) { 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 node Represents a node of a singly-linked list 21- Adapted from the class that used to be tested in now defunct AP Computer Science AB exams. 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 21- This code is terse. Basically it is the same as public ListNode append(ListNode head, Object x) { ListNode newNode = new ListNode(x, null); (head); head = newNode; return head; } Singly-Linked List