Such as for __getitem__,
def __getitem__(self, index):
''' (LinkedList, int|slice) -> object
Return the value at position index.
# don't fuss about slices yet.
if index > self.size - 1:
raise Exception('out of range')
else:
current_node = self.front
for i in range(0, index):
current_node = current_node.nxt
return current_node.value
But there are also some operations quiet complicate which require more than one flag pointers to keep track of the process, such as
def insert_before(lnk, v1, v2):
''' (LinkedList, object) -> NoneType
Insert a new node with value v1 before the first occurrence
of a node with value v2. Do nothing if no node has value
v2.'''
if v2 == lnk.front.value:
new_node = LLNode(v1)
new_node.nxt = lnk.front
lnk.front = new_node
lnk.size += 1
else:
pre = lnk.front
cur = lnk.front.nxt
while cur and cur.value != v2:
pre = cur
cur = cur.nxt
if cur:
new_node = LLNode(v1)
new_node.nxt = cur
pre.nxt = new_node
lnk.size += 1
The additional node 'pre' is added because in one directional oriented linked list, there is no way for us to know the pre-node of current node. In that case, we need a node to keep track of the pre-node of current node, when current node meets the requirement, we can operate on the pre-node which is pointed by pre.
No comments:
Post a Comment