CP104 Lecture Notes - Lecture 21: Data Element, Nth Metal, Binary Search Algorithm
2
CP104 Full Course Notes
Verified Note
2 documents
Document Summary
__updated__ = 2017-02-10 from copy import deepcopy class _slnode: def __init__(self, value, next_): Preconditions: value - data value for node (?) next_ - another sorted list node (_listnode) Initializes a list node that contains a copy of value and a link to the next node in the list. self. _data = deepcopy(value) self. _next = next_ return class sortedlist: def __init__(self): Initializes an empty sorted list. self. _front = none self. _count = 0 self. _next = none self. _rear = none return def is_empty(self): Returns true if the list is empty, false otherwise. return self. _front is none def __len__(self): Returns the number of values in the list. return self. _count #we"re keeping the count already def insert(self, value): Inserts value at the proper place in the sorted list. Must be a stable insertion, i. e. consecutive insertions of the same value must keep their order preserved. Cannot do a (simple) binary search on a linked structure. Searches for the first occurrence of key in the sorted list.
