CODEWITHSUNDEEP
python-3.xdoubly-linked-list
runnergirl9
runnergirl9

Reputation: 45

insert at arbitrary position in doubly linked sentinel list

I know how to append an item into a doubly linked sentinel list and have successfully implemented it in the past. However, I'm not sure how I would insert at a particular position. For example, I have two nodes and want to insert a value in between. Since there's no numeric indexing in a linked list (the entire reason why we're using a linked list...), how could I fix this code so that it can insert item at a particular location (index here is a descriptive term, not a numeric index):

def insert_element_at(self, val, index):
 new_node = Linked_List.__Node(val) 
 if index >= self.size or index < 0:
      raise IndexError
 elif self.size == 0:
     raise 'To add first value, please use append method.'
 else:
    self.current = self.header.next
    count = 0
    while count != index:
      self.current = self.current.next
      count += 1
    self.current.next = new_node
    new_node.next = self.current.next.next
    new_node.prev = self.current
    self.size += 1

I used the 'count' as a way to keep track of position in this case with each iteration. This doesn't seem to work and Does anyone have any ideas as to how I can improve this code? The main problem that I think I'm running into is when it encounters my string method:

def __str__(self):  
  if self.size == 0:
    return '[ ]'
  self.current = self.header.next
  s = '[ '
  while self.current is not self.trailer:
    s += str(self.current.val)
    s += ', '
    self.current = self.current.next
  s += ' ]'
  return s

Any ideas or help on how I can improve this would be great!

Upvotes: 2

Views: 728

Answers (1)

Blckknght
Blckknght

Reputation: 104722

I think the issue is with the order of your operations linking the new node into the existing ones. When you do self.current.next = new_node as the first step, you lose access to the original value of self.current.next (which should become the node after the new one).

Here's how I'd do it:

while count != index:
  self.current = self.current.next
  count += 1
new_node.prev = self.current
new_node.next = self.current.next
self.current.next.prev = new_node
self.current.next = new_node

While I didn't do it above, I'd also suggest that you make current a local variable instead of an attribute of self, since local variables in functions are faster to access than globals or attributes.

Upvotes: 1

Related Questions