Chapter 5: Linked Lists Flashcards
What is a link?
A link is a reference to the next item, it is an attribute embedded in a list item
How is the Link class implemented?
Each Link is a list item with an attribute “next” which contains a reference to another Link item.
What is a reference?
A reference is an object’s address in a computer’s memory
What are the major ways links differ from arrays?
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
What is the efficiency of insertion and deletion?
O(1), only require a change of references
What is the efficiency of finding or deleting or insertion next to a specific item?
O(n)
What are abstract data types?
Data types that focus on what they do and not how their implemented.
What are abstract data types in the realm of OOP?
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)
What is the advantage of a sorted list over a sorted array?
In a sorted list, items don’t need to be moved. An array is limited to the space allotted, lists can fill memory.
What is a doubly-linked list? A double-ended list?
A doubly linked list permits backward traversal and deletion from the end of the list.
What is an iterator?
An iterator is a reference, encapsulated in a class object, that points to a link in an associated list.
What does an iterator method allow?
Iterator methods allow the user to move the iterator along the list and access the link currently pointed to.
What is an iterator used for?
An iterator can be used to traverse through a list, performing some operation on selected links (or all links).
