Inserting and getting the position in a Linked List class using python

Question

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.

Answer 1

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.
• The loop never advances current to the next node. So this represents an infinite loop.
• The 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