Chapter 5: Linked Lists Flashcards

1
Q

What is a link?

A

A link is a reference to the next item, it is an attribute embedded in a list item

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How is the Link class implemented?

A

Each Link is a list item with an attribute “next” which contains a reference to another Link item.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a reference?

A

A reference is an object’s address in a computer’s memory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the major ways links differ from arrays?

A

In arrays, each item occupies a specific position, in linked lists the only way to find an item is to follow each next relation. Maybe think of this like a recipe or an algorithm, or a book, you can’t jump ahead. There is no page 300, only page current page + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the efficiency of insertion and deletion?

A

O(1), only require a change of references

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the efficiency of finding or deleting or insertion next to a specific item?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are abstract data types?

A

Data types that focus on what they do and not how their implemented.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are abstract data types in the realm of OOP?

A

Class considered w/o respect to it’s implementation, as a collection of data fields and methods to be carried out on them (contrast this with primitive data types, same idea but built into the language)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the advantage of a sorted list over a sorted array?

A

In a sorted list, items don’t need to be moved. An array is limited to the space allotted, lists can fill memory.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a doubly-linked list? A double-ended list?

A

A doubly linked list permits backward traversal and deletion from the end of the list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is an iterator?

A

An iterator is a reference, encapsulated in a class object, that points to a link in an associated list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does an iterator method allow?

A

Iterator methods allow the user to move the iterator along the list and access the link currently pointed to.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is an iterator used for?

A

An iterator can be used to traverse through a list, performing some operation on selected links (or all links).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly