🔒 Optimise Indexing for Doubly Linked List

[glad karma]

Can I make the logic for indexing elements more efficient?

class ListNode:
    def __init__(self, data):
        self.data = data
        self.prev = self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def __getitem__(self, index):
        if index < 0:
            index += len(self)
        current = self.head
        for _ in range(index):
            current = current.next
        return current.data

    def append(self, data):
        new_node = ListNode(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = self.tail = new_node
        self.size += 1

    def appendleft(self, data):
        new_node = ListNode(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = self.head = new_node
        self.size += 1

    def insert(self, index, data):
        if index < 0:
            index += len(self)
        if index == 0:
            self.appendleft(data)
        elif index == len(self):
            self.append(data)
        else:
            current = self.head
            for _ in range(index):
                current = current.next
            new_node = ListNode(data)
            new_node.prev, new_node.next = current.prev, current
            if current.prev:
                current.prev.next = new_node
            current.prev = new_node
            self.size += 1

    def pop(self):
        if self.tail:
            data = self.tail.data
            if self.head == self.tail:
                self.head = self.tail = None
            else:
                self.tail, self.tail.next = self.tail.prev, None
            self.size -= 1
            return data```

[misty crypt]

@glad karma

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[glad karma]

def popleft(self):
    if self.head:
        data = self.head.data
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.head, self.head.prev = self.head.next, None
        self.size -= 1
        return data

def remove(self, data):
    current = self.head
    found = False
    while current and not found:
        if current.data == data:
            if current.prev:
                current.prev.next = current.next
            else:
                self.head = current.next
            if current.next:
                current.next.prev = current.prev
            else:
                self.tail = current.prev
            self.size -= 1
            found = True
        current = current.next```

[grave wraith]

what you wrote is the standard way to index into a DLL

if you had to get improvements I would look into https://en.wikipedia.org/wiki/Unrolled_linked_list

(or some variant on the same idea, like storing the nodes for every N indices, although that would really increase costs of insertion and removal and is probably a bad idea now that I think about it)

but really if you want fast indexing then a DLL is the wrong data structure

[misty crypt]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.