Unit 3 Chapter 5 Linked Lists Terms & Concepts

Question 1

Each Link object contains references to:

Answer 1

to a data item, to next link in the list. A field in the LinkList class refers to the first link.

Question 2

how is linked-list self-referential?

Answer 2

it contains a field - called next - of the same type object as itself

Question 3

in an array each item occupies a particular position which can be accessed using an index number, what is the process for linked lists?

Answer 3

in a list, the only wat to find a particular element is to follow along the chain of elements.

Question 4

where are new links added in a linked list?

Answer 4

at the beginning of the list.

Question 5

how are links removed in a linked list?

Answer 5

the reference to the preceding link is changed to point to the following link.

Question 6

in the link constructor, what is next automatically set to?

Answer 6

null

Question 7

what is the process for inserting a new link using the insertFirst method of a linked list?

Answer 7

set the next field in the newly created link to point to the old first link, and then change first so it points to the newly created link.

Question 8

what is the process for deleting a link using the deleteFirst method of a linked list?

Answer 8

it disconnects the first link by rerouting first to point to the second link. DeleteFirst assumes the list is not empty, verify using isEmpty.

Question 9

what is the process for displayList method of a linked list?

Answer 9

starts at first and follow chain of references from link to link. The variable current refers to each link in turn.

Question 10

what is the process for finding a link using the delete( ) method of a linked list?

Answer 10

searches for link to be deleted, maintains a reference to the current link and and previous link, deletes the current link, connects the preceding link to the following link. At each cycle through the while loop, just before current is set to current.next, previous is set to current.

Question 11

Double-ended list definition

Answer 11

a double-ended list is similar to an ordinary linked list, but it has an additional reference to the last link as well as the first.

Question 12

What is the purpose of the additional reference to the last link in a double=ended list?

Answer 12

The reference to the last link permits you to insert a new link directly at the end of the list as well as the beginning.

Question 13

what is the process for the method insertLast in a double-ended list?

Answer 13

modify last.next to point to the new link and then change last to point to the new link.

Question 14

what consideration must be made in the special case when the double-ended list is empty prior to insertion?

Answer 14

if isEmpty is true, then insertFirst must set last to the new link and insertLast must set first to the new link.

Question 15

what is linked list efficiency for insertion, deletion and deleting inserting next to a specific item

Answer 15

insert first and delete first takes O(1) time.
requires O(N) comparisons for insert and delete of specific item.

Question 16

Define: Abstraction

Answer 16

considered apart from detailed specifications or implementation.

Question 17

Define: Abstract Data Type

Answer 17

a class considered without regard to its implementation. A description of the data in the class (fields), a list of operations (methods) that can be carried out on the data, and instructions on how to use these operations.

Question 18

Define: interface

Answer 18

An ADT specification. What the class user sees - usually its public methods - such as push and pop.

Question 19

Define: Sorted List

Answer 19

items are arranged by key value.

Question 20

Efficiency of Sorted Linked Lists

Answer 20

insertion/deletion at sorted location: O(N)

insertion/deletion of minimum key value:O(1)

Question 21

Define: Doubly Linked Lists

Answer 21

Capable of traversing backward as well as forward through the list.

Question 22

How is a doubly linked list able to traverse backwards?

Answer 22

Each link has two references to other links instead of just one to the next link, as in ordinary lists, there is a second link to the previous link.

Question 23

What are the three insertion routines of a doubly linked list?

Answer 23

insertFirst( ), insertLast( ), insertAfter( ).

Question 24

What is the process for insertFirst( ) in a doubly linked list?

Answer 24

Unless the list is empty, insertFirst changes the previous field in the old first link to point to the new link and changes the next field in the new link to point to the old first link. Finally, it sets first to point to the new link.