Why when I use LinkedList, it will TLE, but when I use ArrayList, it accepts?


  • 1
    Y
    private int capacity;
    private Map<Integer,Integer> map;
    private List<Integer> list;
    public LRUCache(int capacity) {
        this.capacity=capacity;
        map=new HashMap<>();
        list=new LinkedList<>(); //here I use LinkedList
    }
    
    public int get(int key) {
        Integer val=map.get(key);
        if(val==null)
            return -1;
        Iterator<Integer> ite=list.iterator();
        while(ite.hasNext()){
            int tmp=ite.next();
            if(tmp==key){
                ite.remove();
                break;
            }
        }
        list.add(key);
        return val;
    }
    
    public void set(int key, int value) {
        int val=get(key);
        map.put(key,value);
        if(val==-1){
            list.add(key);
            if(list.size()>capacity){
                int tmp=list.get(0);
                list.remove(0);
                map.remove(tmp);
            }
        }
    }
    
    //here I use ArrayList
    private int capacity;
    private Map<Integer,Integer> map;
    private List<Integer> list;
    public LRUCache(int capacity) {
        this.capacity=capacity;
        map=new HashMap<>();
        list=new ArrayList<>();
    }
    
    public int get(int key) {
        Integer val=map.get(key);
        if(val==null)
            return -1;
        list.remove(list.indexOf(key));
        list.add(key);
        return val;
    }
    
    public void set(int key, int value) {
        int val=get(key);
        map.put(key,value);
        if(val==-1){
            list.add(key);
            if(list.size()>capacity){
                int tmp=list.get(0);
                list.remove(0);
                map.remove(tmp);
            }
        }
    }
    

    I think when frequently remove, LinkedList is better than ArrayList and their time complexity of find is same. So why LinkedList TLE?


  • 0
    H

    I had this issue too, TLE on LinkedList and simply replace it with ArrayList, got it accepted. ArrayList has better performance on searching than LinkedList, cause it stores data in sequence in memory. I think in this case searching is a little more important than deleting.


  • 0
    J

    That's because you are using linked list in a wrong way.
    Actually an node in a linked list can be found in O(1) time.


  • 0
    M

    Both ArrayList.remove(Object o) and LinkedList.remove(Object o) are scanning element one by one, and return the 1st element equals to o. The former use continuous memory space, the latter doesn't, which cause that the former is faster than the latter.


  • 0
    W

    actually, when remove an element in arraylist, the elements after the o will be moved forward. here it costs more time than linkedList. So I don't why arraylist is better than linkedlist. Or in this question, find is more frequent than delete and find needs more concern than delete?
    Thanks


Log in to reply
 

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