Runtime error in a linked list implementation


  • 0
    K

    A naive implementation using array to represent linked list, probably too slow, but I got Runtime error when the test size goes to 512, meaning there is a bug?

    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    class LRUCache{
        int* val;
        int* ky;
        int* nxt; // next recently used
        int* pre; // previously used
        int cap; 
        int size;
        int LRU; // least recently used
        int MRU; // most recently used
        
    public:
        LRUCache(int capacity) {
            val = new int [capacity];
            ky = new int [capacity];
            nxt = new int [capacity];
            pre = new int [capacity];
            memset(nxt, 0, sizeof(nxt));
            memset(pre, 0, sizeof(pre));
            cap = capacity;
            size = 0;
            LRU = 0;
            MRU = 0;
        }
        
        void reset(int i){	
            if (i == LRU) {
                LRU = nxt[i];
                pre[i] = MRU;
                MRU = i;
            }
            else if (i != MRU) {
                nxt[pre[i]] = nxt[i];
                pre[nxt[i]] = pre[i];
                pre[i] = MRU;
                nxt[MRU] = i;
                MRU = i;
            }
        }
        
        int get(int key) {
            for (int i = 0; i < size; i++){
                if (key == ky[i]){ 
                    reset(i);
                    return val[i];
                }
            }
            return -1;
        }
        
        void set(int key, int value) {
    	    // key in cache
    	    for (int i = 0; i < size; ++i){
    	        if (ky[i] == key){
    		    val[i] = value;
        		reset(i);
    	    	return;
    	        }
    	    }
    	    // key not in cache
        	if (size < cap){
                    ky[size] = key;
                    val[size] = value;
                    nxt[MRU] = size;
                    pre[size] = MRU;
                    MRU = size;
                    size += 1;
                }
            else {
                ky[LRU] = key;
                val[LRU] = value;
                reset(LRU);
            }
        }
    };

Log in to reply
 

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