Lists - Chapter 2 Flashcards
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
list
Inserts x at end of list
Append(list, x)
Inserts x at start of list
Prepend(list, x)
Inserts x after w
InsertAfter(list, w, x)
Removes x
Remove(list, x)
Returns item if found, else returns null
Search(list, x)
Prints list’s items in order
Print(list)
Prints list’s items in reverse order
PrintReverse(list)
Sorts the lists items in ascending order
Sort(list)
Returns true if list has no items
IsEmpty(list)
Returns the number of items in the list
GetLength(list)
common approach for implementing a linked list is using what two data structures
List data structure:
List node data structure:
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.
list data structure
The blank maintains the data for each list element, including the element’s data and pointers to the other list element.
list node data structure
A blank is not required to implement a linked list, but offers a convenient way to store the list’s head and tail.
list data structure
A blank is a data structure for implementing a list ADT, where each node has data and a pointer to the next node.
singly-linked list
A singly-linked list’s first node is called the blank, and the last node the blank.
head
tail
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.
positional list:
Blank is a special value indicating a pointer points to nothing.
null
Given a new node, the blank operation for a singly-linked list inserts the new node after the list’s tail node.
Append
Blank: If the list’s head pointer is null (empty), the algorithm points the list’s head and tail pointers to the new node.
Append to empty list:
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.
Append to non-empty list
Given a new node, the blank operation for a singly-linked list inserts the new node before the list’s head node.
Prepend
Blank: If the list’s head pointer is null (empty), the algorithm points the list’s head and tail pointers to the new node.
Prepend to empty list
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.
Prepend to non-empty list
Given a new node, the blank operation for a singly-linked list inserts the new node after a provided existing list node.
InsertAfter
Blank: If the list’s head pointer is null, the algorithm points the list’s head and tail pointers to the new node.
Insert as list’s first node
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.
Insert after list’s tail node
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.
Insert in middle of list
Given a specified existing node in a singly-linked list, the blank operation removes the node after the specified list node.
RemoveAfter
In RemoveAfter, the existing node is specified with the curNode parameter. If curNode is null, RemoveAfter removes the list’s blank.
first node
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).
Remove list’s head node (special case)
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).
Remove node after curNode
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.
search
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).
simple linked list search
In Python, classes are used for both blank and blank that comprise the list.
the linked list and the nodes
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.
end
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.
doubly-linked list
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.
next and previous nodes
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.
positional list
A blank is a linked list where the tail node’s next pointer points to the head of the list, instead of null.
circular linked list
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.
repeating processes
The head of a circular linked list is often referred to as the blank.
start node
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.
head node
A blank algorithm visits all nodes in the list once and performs an operation on each node.
list traversal
A blank visits all nodes starting with the list’s tail node and ending after visiting the list’s head node.
reverse traversal
A blank also supports a reverse traversal
doubly-linked list
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.
O(N^2)
O(N)
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.
null
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.
O(N^2)
O(N)
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.
quicksort and heapsort
Operates similarly on doubly-linked lists. Requires searching from the head of the list for an element’s insertion position for singly-linked lists.
Insertion sort
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.
Merge sort
Jumping the gap between elements cannot be done on a linked list, as each element between two elements must be traversed.
Shell sort
Partitioning requires backward traversal through the right portion of the array. Singly-linked lists do not support backward traversal.
Quicksort
Indexed access is required to find child nodes in constant time when percolating down.
Heap sort
What aspect of linked lists makes adapting array-based sorting algorithms to linked lists difficult?
Lack of indexed access
Which sorting algorithm uses a gap value to jump between elements, and is difficult to adapt to linked lists for this reason?
Shell sort
Why are sorting algorithms for arrays generally more difficult to adapt to singly-linked lists than to doubly-linked lists?
Several sorting algorithms traverse backward through list elements, which cannot be done with a singly-linked list.
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
Insertion sort algorithm for doubly-linked lists.
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
Insertion sort algorithm for singly-linked lists
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.
dummy node
Using a dummy node simplifies the algorithms for a linked list because the blank and blank are never null.
head and tail pointers
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.
empty list
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.
first list item
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.
null
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.
one at the head and the other at the tail.
Blank through a linked list can be implemented using a recursive function that takes a node as an argument.
Forward traversal
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.
recursive linked list search
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.
reverse order
An blank is a list ADT implemented using an array.
array-based list
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.
resized
Because all existing elements must be copied from 1 array to another, the resize operation has a runtime complexity of blank
O(N)
Because all existing array elements must be moved up by 1, the prepend operation has a runtime complexity of blank.
O(N)
The InsertAfter operation has a best case runtime complexity of blank and a worst case runtime complexity of blank.
O(1)
O(N)
Both the search and remove operations have a worst case runtime complexity of blank
O(N)
