Reputation: 13
I am new to Data Structure and algorithms. I'm a self-taught Python programmer. I am doing a course on it and I wanted to make a linked list, get a specific position in the linked list, insert, and delete an element in the list. So I wrote my code, and to me, it seems fine. It's not giving me any errors, but it's not executing as well.
This is the code that I wrote,
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def append(self, new_element):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def get_position(self, position):
"""Get an element from a particular position.
Assume the first position is "1".
Return "None" if position is not in the list."""
current = self.head
if self.head:
while current.next:
if current == position:
return current
else:
continue
else:
return None
def insert(self, new_element, position):
"""Insert a new node at the given position.
Assume the first position is "1".
Inserting at position 3 means between
the 2nd and 3rd elements."""
current = self.head
if self.head:
while current.next:
if current.next == position:
current.next = new_element
break
else:
continue
else:
self.head = new_element
The error is in get position function and insert function
can anyone tell me what is it that I'm doing wrong? Is there an issue with the loop or something? Please help me, I'll be grateful!! Thanks.
Upvotes: 1
Views: 2475
Reputation: 351403
Some issues in get_position
:
current == position
is not the condition you need to verify. position
is a number and current
is an Element, so they don't really compare. You need to verify whether the position
is 1 or 2, ... depending on how far you are in your list.current
to the next node. So this represents an infinite loop.while
condition should not check current.next
, but current
. Otherwise you will never do a check for the last node in the list.Here is your code corrected:
def get_position(self, position):
if position < 1: # Just in case the position is too small
return
current = self.head
while current and position > 1:
position -= 1
current = current.next
return current
So the loop ends whenever position gets to be decreased to 1, or there is no more node. In the latter case the return value will be None
.
Although your question is about the get_position
function, your insert
also has the same problems. On top of that it also treats the head
case wrong. It should also change the head
when the provided position is 1.
The insert
method can in fact make use of the above function to find the node that should precede the node to be inserted:
def insert(self, new_element, position):
if position == 1:
new_element.next = self.head
self.head = new_element
else:
before = self.get_position(position-1)
if before is None:
raise ValueError("invalid position")
new_element.next = before.next
before.next = new_element
Upvotes: 3