Linear Data Structure: Iteration

Question 1

What is a cursor?

Answer 1

An abstraction that represents a position with a collection; a property of a collection that records a specific position

Question 2

Operations on a cursor interface

Answer 2

itemExists (check)

item (getter)

goFirst (mover in list)

goForth (mover in list)

goLast (mover in list)

goBefore (mover outside of list)

goAfter (mover outside of list)

before (test)

after (test)

Question 3

Are all operations necessary?

Answer 3

No, different data structures/ADTs will have different types of operations

Question 4

How to represent: between 2nd and last element in a list

Answer 4

• position value: non-null
• prevPosition value: non-null
• # elements in list: > 1

Question 5

How to represent: first element in a list

Answer 5

• position value: non-null
• prevPosition value: null
• # elements in list: > 0

Question 6

How to represent: after in a list

Answer 6

• position value: null
• prevPosition value: non-null
• # elements in list: > 0

Question 7

How to represent: before in a list

Answer 7

• position value: null
• prevPosition value: null
• # elements in list: > 0

Question 8

How to represent: before and after in a list

Answer 8

• position value: null
• prevPosition value: null
• # elements in list: 0

Question 9

What are the external differences between the cursor interface of the ArrayedList and LinkedList classes

Answer 9

None, they are the same, which is an advantage of cursors; cursors have the same outward functionality regardless of the different list structure

Question 10

Are there internal differences between the cursor interface of the ArrayedList and LinkedList classes

Answer 10

Yes, different data structures have different internal implementations, even though they externally work the same

Question 11

What is an iterator? How is it different from a cursor

Answer 11

A distinct object that represents a position in an instance of a collection and always has public methods for iteration.

Cursors are just an abstraction of a position and may not have public methods

Question 12

What is the idea behind iterators?

Answer 12

1. An instance method of a list (or any collection) is called that returns an iterator object.
2. The iterator object implements the cursor interface.
3. The iterator object can be used to “loop” over the elements of the list instance which generated it.

Question 13

What’s the purpose of iterators?

Answer 13

Cursors can be used for something else in the moment, while we are iterating with an iterator.

Otherwise, it would be up to the user to save and restore the collection’s cursor before and after using the cursor to iterate