Python list can pass; I create a linked list but TLE, what's wrong with it?


  • 0
    S
    class ListNode:
        def __init__(self, val):
            self.val = val
            self.next = None
            self.prev = None
    
    class LRUCache:
    
        # @param capacity, an integer
        def __init__(self, capacity):
            self.capacity = capacity
            self.dic = {}
            self.head = None
            self.length = 0
            
    
        # @return an integer
        def get(self, key):
            if key in self.dic:
                cur = self.head
                while cur.val != key:
                    cur = cur.next
                if cur != self.head:
                    prev = cur.prev
                    next = cur.next
                    prev.next = next
                    if next:
                        next.prev = prev
                    self.head.prev = cur
                    cur.next = self.head
                    cur.prev = None
                    self.head = cur
                return self.dic[key]
            return -1
            
    
        # @param key, an integer
        # @param value, an integer
        # @return nothing
        def set(self, key, value):
            if key in self.dic:
                self.dic[key] = value
                cur = self.head
                while cur.val != key:
                    cur = cur.next
                if cur != self.head:
                    prev = cur.prev
                    next = cur.next
                    prev.next = next
                    if next:
                        next.prev = prev
                    self.head.prev = cur
                    cur.next = self.head
                    cur.prev = None
                    self.head = cur
            else:
                self.dic[key] = value
                if self.length < self.capacity:
                    self.length += 1
                    cur = ListNode(key)
                    if self.head:
                        cur.next = self.head
                        self.head.prev = cur
                    self.head = cur
                else:
                    if self.capacity == 1:
                        del self.dic[self.head.val]
                        self.head.val = key
                    else:
                        cur = self.head
                        while cur.next:
                            cur = cur.next
                        del self.dic[cur.val]
                        cur.prev.next = None
                        cur.val = key
                        cur.next = self.head
                        self.head.prev = cur
                        cur.prev = None
                        self.head = cur
    

    If I use Python list, it works; However, I create a double linked list (this version) and single linked list and they cannot pass, TLE.

    What's wrong with it?


  • 0
    B

    Check if there's circular reference in your list. These often cause subtle problems.


  • 0
    S

    This code can work locally, just the time limit error on leetcode.


  • 0
    B

    You're not using the dict in a right way. The most time-consuming part of your program is to find the right node and get/delete it, in which you use a linear search. When LRU is large, that's not acceptable.

    The correct way of using dict is, instead of store values, you store the reference to linked list node. And that's why we use doubly linked list, because even with a single reference, you can still delete a node.

    Then when you search in the linked list, the time complexity will be O(1) instead of O(N), given the underlying implementation of Python dict is hash table.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.