Section 3.24 Implementing an Ordered List as a Linked List
In this section, we will implement an ordered list as a linked list. (We leave the exercise of implementing it with an array to the reader.) In order to implement the ordered list, we must remember that the relative positions of the items are based on some underlying characteristic. The ordered list of integers given above (17, 26, 31, 54, 77, and 93) can be represented by a linked structure as shown in Figure 3.24.1. Again, the node and link structure is ideal for representing the relative positioning of the items.
To implement the
LinkedOrderedList class, we will use the same technique as seen previously with unordered lists. Once again, an empty list will be denoted by a head reference initialized to null (see Listing 3.24.2):
LinkedOrderedList.class LinkedOrderedList<T: Comparable<T>> {
private var head: Node<T>? = null
...
}
The first line of the header has
T: Comparable<T>, which we should discuss. We are going to be implementing this as an ordered list, which means that we will regularly need to compare one item in the list with another. We will regularly be writing code that does ordering comparisons like a < b, or a > b, where a and b are of type T. This means that this class won’t work for any type T; it can only work for types where such ordering comparisons are legitimate. Most of the types we have used (e.g. strings, integers, doubles, etc) all allow ordering comparisons. On the other hand, there are types that do not. It would be meaningless to ask if one list was greater than another, for example. (We could compare the list sizes to see which was bigger, but it isn’t defined to compare ordering on the lists themselves. Kotlin has an built-in interface named Comparable<T> which is used to mean "comparisons to type <T> are allowed." So when we define our LinkedOrderedList class, we need to indicate that it is a class which takes a type as a parameter, but that type needs to implement the interface for Comparable<T>. In other words, our new class is only defined for types that allow ordering comparisons.
As we consider the operations for the ordered list, we should note that the
isEmpty and size member functions can be implemented the same as with unordered lists since they deal only with the number of nodes in the list without regard to the actual item values. Likewise, the remove member function will work just fine since we still need to find the item and then link around the node to remove it. The functions for searching and adding will require some modification.
The search of an unordered linked list required that we traverse the nodes one at a time until we either find the item we are looking for or run out of nodes (
null). As we said before, the same approach would work with the ordered list and no changes are necessary if the item is in the list. However, in the case where the item is not in the list, we can take advantage of the ordering to stop the search as soon as possible.
For example, Figure 3.24.3 shows the ordered linked list as a search is looking for the value 45. As we traverse, starting at the head of the list, we first compare against 17. Since 17 is not the item we are looking for, we move to the next node, in this case 26. Again, this is not what we want, so we move on to 31 and then on to 54. Now, at this point, something is different. Since 54 is not the item we are looking for, our former strategy would be to move forward. However, due to the fact that this is an ordered list, that will not be necessary. Once the value in the node becomes greater than the item we are searching for, the search can stop and return
false. There is no way the item could exist further out in the linked list.
Listing 3.24.4 shows the complete
search method. We can incorporate the new condition discussed above by adding another check (line 6). We continue to look forward in the list (line 3). If any node is ever discovered that contains data greater than the item we are looking for, we will immediately return false. The remaining lines are identical to the unordered list search.
indexOf function for a LinkedOrderedListfun indexOf(item: T): Int {
var current = head
var location = 0
while (current != null) {
if (current.data == item) {
return location
}
if (current.data > item) {
return -1
}
current = current.next
location++
}
return -1
}
The functions to add items need to change. Rather than add items at the head of the list, as we did with
addFirst in the unordered case, we must find the correct position for the insertion so that elements don’t get out of order.
Assume we have the ordered list consisting of 17, 26, 54, 77, and 93 and we want to add the value 31. The
add method must decide that the new item belongs between 26 and 54. Figure 3.24.5 shows the setup that we need. As we explained earlier, we need to traverse the linked list looking for the place where the new node will be added. We know we have found that place when either we run out of nodes (current becomes null) or the value of the current node becomes greater than the item we wish to add. In our example, seeing the value 54 causes us to stop.
As we saw with unordered lists, it is necessary to have an additional reference, again called
previous, since current will not provide access to the node that must be modified. Listing 3.24.6 shows the complete add method. Lines 2–3 set up the two references, and lines 6–7 again allow previous to follow one node behind current every time through the iteration. The condition (line 5) allows the iteration to continue as long as there are more nodes and the value in the current node is less the item. In either case, when the iteration fails, we have found the location for the new node.
The remainder of the function completes the two-step process shown in Figure 3.24.5. Once a new node has been created for the item in line 9, the only remaining question is whether the new node will be added at the beginning of the linked list or some place in the middle. Again,
previous == null (line 11) can be used to provide the answer.
add function for a LinkedOrderedListfun add(item: T) {
var current = head
var previous: Node<T>? = null
while (current != null && current.data < item) {
previous = current
current = current.next
}
val itemNode = Node(item)
if (previous == null) {
itemNode.next = head
head = itemNode
} else {
itemNode.next = current
previous.next = itemNode
}
}
The
LinkedOrderedList class with functions discussed thus far is in Listing 3.24.7 along with documentation of its functions. We leave the remaining functions as exercises. You should carefully consider whether the unordered implementations will work given that the list is now ordered.
OrderedList Classclass LinkedOrderedList<T: Comparable<T>> {
private var head: Node<T>? = null
// Adds (insert) a new item at the appropriate location.
fun add(item: T) {
var current = head
var previous: Node<T>? = null
while (current != null && current.data < item) {
previous = current
current = current.next
}
val itemNode = Node(item)
if (previous == null) {
itemNode.next = head
head = itemNode
} else {
itemNode.next = current
previous.next = itemNode
}
}
// Find index of first occurrence of item in list.
fun indexOf(item: T): Int {
var current = head
var location = 0
while (current != null) {
if (current.data == item) {
return location
}
if (current.data > item) {
return -1
}
current = current.next
location++
}
return -1
}
override fun toString(): String {
var current: Node<T>? = head
var result = "[ "
while (current != null) {
result = result + current.data.toString() + " "
current = current.next
}
result = result + "]"
return result
}
}
Subsection 3.24.1 Analysis of Linked Lists
To analyze the complexity of the linked list operations, we need to consider whether they require traversal. Consider a linked list that has \(n\) nodes. The
isEmpty function is \(O(1)\) since it requires one step to check the head reference for null. size, on the other hand, will always require \(n\) steps since there is no way to know how many nodes are in the linked list without traversing from head to end. Therefore, size is \(O(n)\text{.}\) Adding an item to an unordered list will always be \(O(1)\) since we simply place the new node at the head of the linked list. However, indexOf and remove, as well as add for an ordered list, all require the traversal process. Although on average they may need to traverse only half of the nodes, these functions are all \(O(n)\) since in the worst case each will process every node in the list.
You have attempted of activities on this page.
