Lists - Chapter 2

Question 1

A blank is a common ADT for holding ordered data, having operations like append a data item, remove a data item, search whether a data item exists, and print the list

Answer 1

list

Question 2

Inserts x at end of list

Answer 2

Append(list, x)

Question 3

Inserts x at start of list

Answer 3

Prepend(list, x)

Question 4

Inserts x after w

Answer 4

InsertAfter(list, w, x)

Question 5

Removes x

Answer 5

Remove(list, x)

Question 6

Returns item if found, else returns null

Answer 6

Search(list, x)

Question 7

Prints list’s items in order

Answer 7

Print(list)

Question 8

Prints list’s items in reverse order

Answer 8

PrintReverse(list)

Question 9

Sorts the lists items in ascending order

Answer 9

Sort(list)

Question 10

Returns true if list has no items

Answer 10

IsEmpty(list)

Question 11

Returns the number of items in the list

Answer 11

GetLength(list)

Question 12

common approach for implementing a linked list is using what two data structures

Answer 12

List data structure:
List node data structure:

Question 13

A blank is a data structure containing the list’s head and tail, and may also include additional information, such as the list’s size.

Answer 13

list data structure

Question 14

The blank maintains the data for each list element, including the element’s data and pointers to the other list element.

Answer 14

list node data structure

Question 15

A blank is not required to implement a linked list, but offers a convenient way to store the list’s head and tail.

Answer 15

list data structure

Question 16

A blank is a data structure for implementing a list ADT, where each node has data and a pointer to the next node.

Answer 16

singly-linked list

Question 17

A singly-linked list’s first node is called the blank, and the last node the blank.

Answer 17

head
tail

Question 18

A singly-linked list is a type of blank A list where elements contain pointers to the next and/or previous elements in the list.

Answer 18

positional list:

Question 19

Blank is a special value indicating a pointer points to nothing.

Answer 19

null

Question 20

Given a new node, the blank operation for a singly-linked list inserts the new node after the list’s tail node.

Answer 20

Append

Question 21

Blank: If the list’s head pointer is null (empty), the algorithm points the list’s head and tail pointers to the new node.

Answer 21

Append to empty list:

Question 22

Blank: If the list’s head pointer is not null (not empty), the algorithm points the tail node’s next pointer and the list’s tail pointer to the new node.

Answer 22

Append to non-empty list

Question 23

Given a new node, the blank operation for a singly-linked list inserts the new node before the list’s head node.

Answer 23

Prepend

Question 24

Blank: If the list’s head pointer is null (empty), the algorithm points the list’s head and tail pointers to the new node.

Answer 24

Prepend to empty list

Question 25

Blank: If the list’s head pointer is not null (not empty), the algorithm points the new node’s next pointer to the head node, and then points the list’s head pointer to the new node.

Answer 25

Prepend to non-empty list

Question 26

Given a new node, the blank operation for a singly-linked list inserts the new node after a provided existing list node.

Answer 26

InsertAfter

Question 27

Blank: If the list’s head pointer is null, the algorithm points the list’s head and tail pointers to the new node.

Answer 27

Insert as list’s first node

Question 28

Blank: If the list’s head pointer is not null (list not empty) and curNode points to the list’s tail node, the algorithm points the tail node’s next pointer and the list’s tail pointer to the new node.

Answer 28

Insert after list’s tail node

Question 29

Blank: If the list’s head pointer is not null (list not empty) and curNode does not point to the list’s tail node, the algorithm points the new node’s next pointer to curNode’s next node, and then points curNode’s next pointer to the new node.

Answer 29

Insert in middle of list

Question 30

Given a specified existing node in a singly-linked list, the blank operation removes the node after the specified list node.

Answer 30

RemoveAfter

Question 31

In RemoveAfter, the existing node is specified with the curNode parameter. If curNode is null, RemoveAfter removes the list’s blank.

Answer 31

first node

Question 32

Blank: If curNode is null, the algorithm points sucNode to the head node’s next node, and points the list’s head pointer to sucNode. If sucNode is null, the only list node was removed, so the list’s tail pointer is pointed to null (indicating the list is now empty).

Answer 32

Remove list’s head node (special case)

Question 33

Blank: If curNode’s next pointer is not null (a node after curNode exists), the algorithm points sucNode to the node after curNode’s next node. Then curNode’s next pointer is pointed to sucNode. If sucNode is null, the list’s tail node was removed, so the algorithm points the list’s tail pointer to curNode (the new tail node).

Answer 33

Remove node after curNode

Question 34

Given a key, a blank algorithm returns the first node whose data matches that key, or returns null if a matching node was not found.

Answer 34

search

Question 35

A blank algorithm checks the current node (initially the list’s head node), returning that node if a match, else pointing the current node to the next node and repeating. If the pointer to the current node is null, the algorithm returns null (matching node was not found).

Answer 35

simple linked list search

Question 36

In Python, classes are used for both blank and blank that comprise the list.

Answer 36

the linked list and the nodes

Question 37

The append() method adds a node to the blank of a linked list, making the node the tail of the list. The append() method has two parameters, the second of which is the new node to be appended to the list.

Answer 37

end

Question 38

A blank is a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node. The list structure typically points to the first node and the last node.

Answer 38

doubly-linked list

Question 39

A doubly-linked list is similar to a singly-linked list, but instead of using a single pointer to the next node in the list, each node has a pointer to the blank and blank.

Answer 39

next and previous nodes

Question 40

A doubly-linked list is a type of blank: A list where elements contain pointers to the next and/or previous elements in the list.

Answer 40

positional list

Question 41

A blank is a linked list where the tail node’s next pointer points to the head of the list, instead of null.

Answer 41

circular linked list

Question 42

A circular linked list can be used to represent blank. Ex: Ocean water evaporates, forms clouds, rains down on land, and flows through rivers back into the ocean.

Answer 42

repeating processes

Question 43

The head of a circular linked list is often referred to as the blank.

Answer 43

start node

Question 44

A traversal through a circular linked list is similar to traversal through a standard linked list, but must terminate after reaching the a second time, as opposed to terminating when reaching null.

Answer 44

head node

Question 45

A blank algorithm visits all nodes in the list once and performs an operation on each node.

Answer 45

list traversal

Question 46

A blank visits all nodes starting with the list’s tail node and ending after visiting the list’s head node.

Answer 46

reverse traversal

Question 47

A blank also supports a reverse traversal

Answer 47

doubly-linked list

Question 48

Insertion sort’s typical runtime is blank. If a list has N elements, the outer loop executes N - 1 times. In the best case scenario, the list is already sorted, and the runtime complexity is blank.

Answer 48

O(N^2)
O(N)

Question 49

Since a singly-linked list only supports inserting a node after an existing list node, the ListFindInsertionPosition algorithm searches the list for the insertion position and returns the list node after which the current node should be inserted. If the current node should be inserted at the head, ListFindInsertionPosition returns blank.

Answer 49

null

Question 50

The average and worst case runtime of ListInsertionSortSinglyLinked is blank. The best case runtime is blank which occurs when the list is sorted in descending order.

Answer 50

O(N^2)
O(N)

Question 51

Sorting algorithms for arrays, such as blank and blank, require constant-time access to arbitrary, indexed locations to operate efficiently. Linked lists do not allow indexed access, making for difficult adaptation of such sorting algorithms to operate on linked lists.

Answer 51

quicksort and heapsort

Question 52

Operates similarly on doubly-linked lists. Requires searching from the head of the list for an element’s insertion position for singly-linked lists.

Answer 52

Insertion sort

Question 53

Finding the middle of the list requires searching linearly from the head of the list. The merge algorithm can also merge lists without additional storage.

Answer 53

Merge sort

Question 54

Jumping the gap between elements cannot be done on a linked list, as each element between two elements must be traversed.

Answer 54

Shell sort

Question 55

Partitioning requires backward traversal through the right portion of the array. Singly-linked lists do not support backward traversal.

Answer 55

Quicksort

Question 56

Indexed access is required to find child nodes in constant time when percolating down.

Answer 56

Heap sort

Question 57

What aspect of linked lists makes adapting array-based sorting algorithms to linked lists difficult?

Answer 57

Lack of indexed access

Question 58

Which sorting algorithm uses a gap value to jump between elements, and is difficult to adapt to linked lists for this reason?

Answer 58

Shell sort

Question 59

Why are sorting algorithms for arrays generally more difficult to adapt to singly-linked lists than to doubly-linked lists?

Answer 59

Several sorting algorithms traverse backward through list elements, which cannot be done with a singly-linked list.

Question 60

current_node = self.head.next
while current_node != None:
next_node = current_node.next
search_node = current_node.prev

    while ((search_node != None) and 
           (search_node.data > current_node.data)):
        search_node = search_node.prev
  
    # Remove and re-insert curNode
    self.remove(current_node)
        
    if search_node == None:
        current_node.prev = None
        self.prepend(current_node)      
    else:
        self.insert_after(search_node, current_node)

    # Advance to next node
    current_node = next_node

Answer 60

Insertion sort algorithm for doubly-linked lists.

Question 61

before_current = self.head
current_node = self.head.next
while current_node != None:
next_node = current_node.next
position = self.find_insertion_position(current_node.data)
if position == before_current:
before_current = current_node
else:
self.remove_after(before_current)
if position == None:
self.prepend(current_node)
else:
self.insert_after(position, current_node)
current_node = next_node

def find_insertion_position(self, data_value):
position_a = None
position_b = self.head
while (position_b != None) and (data_value > position_b.data):
position_a = position_b
position_b = position_b.next
return position_a

Answer 61

Insertion sort algorithm for singly-linked lists

Question 62

A linked list implementation may use a blank (or header node): A node with an unused data member that always resides at the head of the list and cannot be removed.

Answer 62

dummy node

Question 63

Using a dummy node simplifies the algorithms for a linked list because the blank and blank are never null.

Answer 63

head and tail pointers

Question 64

An blank consists of the dummy node, which has the next pointer set to null, and the list’s head and tail pointers both point to the dummy node.

Answer 64

empty list

Question 65

ListAppend, ListPrepend, and ListInsertAfter do not need to check if the list’s head is null, since the list’s head will always point to the dummy node. ListRemoveAfter does not need a special case to allow removal of the blank, since the blank is after the dummy node.

Answer 65

first list item

Question 66

A dummy node can also be used in a doubly-linked list implementation. The dummy node in a doubly-linked list always has the prev pointer set to blank.

Answer 66

null

Question 67

A doubly-linked list implementation can also use 2 dummy nodes: blank and blank Doing so removes additional conditionals and further simplifies the implementation of most methods.

Answer 67

one at the head and the other at the tail.

Question 68

Blank through a linked list can be implemented using a recursive function that takes a node as an argument.

Answer 68

Forward traversal

Question 69

A blank is implemented similar to forward traversal. Each call examines 1 node. If the node is null, then null is returned. Otherwise, the node’s data is compared to the search key. If a match occurs, the node is returned, otherwise the remainder of the list is searched recursively.

Answer 69

recursive linked list search

Question 70

Forward traversal visits a node first, then recursively traverses the remainder of the list. If the order is swapped, such that the recursive call is made first, the list is traversed in blank.

Answer 70

reverse order

Question 71

An blank is a list ADT implemented using an array.

Answer 71

array-based list

Question 72

An array-based list must be blank if an item is added when the allocation size equals the list length. A new array is allocated with a length greater than the existing array. Allocating the new array with twice the current length is a common approach. The existing array elements are then copied to the new array, which becomes the list’s storage array.

Answer 72

resized

Question 73

Because all existing elements must be copied from 1 array to another, the resize operation has a runtime complexity of blank

Answer 73

O(N)

Question 74

Because all existing array elements must be moved up by 1, the prepend operation has a runtime complexity of blank.

Answer 74

O(N)

Question 75

The InsertAfter operation has a best case runtime complexity of blank and a worst case runtime complexity of blank.

Answer 75

O(1)
O(N)

Question 76

Both the search and remove operations have a worst case runtime complexity of blank

Answer 76

O(N)