Practice English Speaking&Listening with: Lists, Iterators, and Abstract Data Types

This is a really quick introduction to lists and iterators

specifically, and abstract data types in general. This video will

link to a playlist with two implementation strategies, and then a comparison

of them to see how they are best used but often abused.

So a list is some stuff. In some order.

I know what you're thinking, you're like "How can I keep track of such a deep,

technical definition?". Well, actually, if you are new to data structures, there really is

something important hidden in this definition, which is that the list

is an abstract data type. What's that? It's the

formal name of "stuff". You can have a list of integers,

or strings, or records, or whatever you like. Although a few details might change,

the basic logic of how the list works stays the same no matter

what it is that's in the list. What types of things might change?

Maybe for integers, you want to store the integers, but for larger

objects, you might want to store object references instead.

Some of that might be language specific, but for the underlying

algorithmic logic, it doesn't make too much difference. What is an iterator?

It's basically a list bookmark. If you are making a

list data structure for somebody else to use, you should give that user a way to

access the items in your list, one at a time. It's probably fine

for them to ask for the first item in the list, but it is less natural

for them to ask for the second or third. Instead of having the user

track where they are, which might cause some efficiency issues, it

makes more sense to allow the user to just ask for the next item,

and the next, and to give them items that way. Your iterator

might also allow other operations, but it's code is written as a

partner of the list code, which keeps control of the list and its

internal implementation away from the outside user.

So what functionality do you expect from a list? Obviously, there needs

to be some way to create the list, and after that, you need some way to retrieve items,

unless it's like New Year's Resolutions. Assuming the list can change,

you can add to the list, remove from the list, and know its size.

To traverse the list and iterate over its items, you want an iterator that,

at the very least, can give you the next item in the list, starting

at the beginning. Maybe you can do some other stuff too, but I

won't really be too precise here, because a list is very abstract.

Depending on which implementation strategy you use to build your

list, you get different natural functionality.

The two most standard techniques for building a list are to use what is called

a linked list, or to use an array based list.

In Java, these are called LinkedList and ArrayList, but you can use the same strategy in lots

of languages. Instead of making one really long video on lists

that nobody watches all the way through, I will break this into a several shorter

videos that nobody watches at all. The playlist will

at least cover linked lists variants, Array Lists

or Dynamic Arrays, and a comparison of the two. Anyway,

right now, I should probably get this looked at. I am sorry

that every slide was just a list.