A singly linked list is a linked list in which each node contains a single link field and allows for a complete traversal from a distinctive first node to the last. The linked list from the previous section is an example of a singly linked list.
There are several operations that are commonly performed on a singly linked list, which we explore in this section. To illustrate the implementation of these operations, our code assumes the existence of a head reference and uses the ListNode class defined earlier. The data fields of the ListNode class will be accessed directly but this class should not be used outside the module in which it is defined as it is only intended for use by the linked list implementation.
Traversing the Nodes
In the earlier example, we accessed the second and third nodes of our sample list by stringing together the next field name off the external reference variable a. This may be sufficient for lists with few nodes, but it's impractical for large lists. Instead, we can use a temporary external reference to traverse through the list, moving the reference along as we access the individual nodes. The implementation is provided below:
def traversal(head) :
curNode = head
while curNode : # equivalent to - while curNode is not None
print(curNode.data)
curNode = curNode.next
The process starts by assigning a temporary external reference curNode
to point to the first node of the list as illustrated below. The value of the second
After entering the loop, the value stored in the first node (2) is printed by accessing the data component stored in the node using the temporary external reference
The external reference is then advanced to the next node by assigning it the value of the current node's link field
The loop iteration continues until every node in the list has been accessed. The value in the second node (52) is printed and curNode is advanced
Value 18 is printed and the external reference is again advanced to the next node
As the loop continues, the value in the fourth node (36) is printed and curNode is advanced to the last node
The completion of the traversal is determined when curNode becomes null (i.e. the reference is None) or "falls off the end of the list." After value 13 is printed, curNode is advanced to the next node, but there being no next node, curNode is assigned None from the next field of the last node
This condition will be utilized by most of the linked list operations to determine when the end of the list has been reached.
A correct implementation of the linked list traversal must also handle the case where the list is empty. Remember, an empty list is indicated by a null head reference.
linked list traversal
If the list were empty, the curNode reference would be set to None by the first statement in the traversal function and the loop would not execute producing the correct result. A complete list traversal requires time since each node must be accessed and each access only requires
constant time.
Searching for a Node
A linear search operation can be performed on a linked list. It is
very similar to the traversal demonstrated earlier. The only difference
is that the loop can terminate early if we find the target value within
the list. Our implementation of the linear search follows:
def unorderedSearch(head, target) :
curNode = head
while curNode and curNode.data != target :
curNode= curNode.next
return curNode is not None
Note the order of the two conditions in the while loop. It is important that we test for a null curNode reference before trying to examine the contents of the node. If the item is not found in the list, curNode will be null when the end of the list is reached. If we try to evaluate the data field of the null reference, an exception will be raised, resulting in a run-time error. Remember, a null reference does not point to an object and thus there are no fields or methods to be referenced.
NOTE
|
|
|
Short-Circuit Evaluation
Most programming languages use short-circuit evaluation when testing compound logical expressions. If the result of the compound expression is known after evaluating the first component, the evaluation ends and returns the result. For example, in evaluating the logical expression a > b and a < c, if a > b is false, then there is no need to continue the evaluation of the second component since the overall expression must be false.
|
linked list search
When implementing the search operation for the linked list, we must make sure it works with both empty and non-empty lists. In this case, we do not need a separate test to determine if the list is empty. This is done automatically by checking the traversal reference variable as the loop condition. If the list were empty, curNode would be set to None initially and the loop would never be entered. The linked list search operation requires in the worst case, which occurs when the target item is not in the list.
Question 7.3.1
Does the searchList function have a best case? If so, when does the best case occur and when does the worst case occur?
The search operation does have a best case, which occurs if the target is stored in the first node in the linked list. The worst case occurs when the target is not in the list, since the loop must iterate through the entire list.
Question 7.3.2
What is the best case time-complexity for the searchList function?
Select the correct answer below by clicking on the appropriate box.
- O(1)
- O(log n)
- O(n)
- O(n2)
If the target is in the first node, the loop only performs a single iteration and then returns True.
Question 7.3.3
Consider the following code segment which searches a linked list for target values from a Python list to determine how many of those values are contained in the linked list. Assume the linked list and the Python list each contain n items.
def countInstances(theValues, head) :
count = 0
for value in theValues :
if searchList(head, value) :
count = count + 1
return count
Select the correct answer below by clicking on the appropriate box.
- O(1)
- O(log n)
- O(n)
- O(n2)
Searching a linked list requires time for each search in the worst case. This search is performed n times, which results in a quadratic time.
