LRU Cache ( C Language )(Runtime: 28 ms)


  • 0
    J
    struct List{
    	int key;
    	int value;
    	struct List *pre;
    	struct List *next;
    };
    
    struct Node{
    	struct Node *next;
    	struct List *position;
    }; 
    
    struct HashTable{
    	struct Node *node;
    	int length;
    	int capacity;
    };
    
    struct HashTable *hash;
    struct List *head,*tail;
    
    void insert_item_to_list(int key,int value)
    {
    	if(head==0&&tail==0){
    		head=(struct List *)malloc(sizeof(struct List));
    		head->key=key;
    		head->value=value;
    		head->pre=0;
    		head->next=0;
    		tail=head;
    	}
    	else{
    		struct List* temp_list;
    		temp_list=(struct List *)malloc(sizeof(struct List));
    		temp_list->key=key;
    		temp_list->value=value;
    		temp_list->pre=0;
    		temp_list->next=head;
    		head->pre=temp_list;
    		head=temp_list;
    	}
    }
    
    int delete_item_in_list(struct List *temp_list)
    {
    	if(temp_list==0){return -1;}
    	else{
    		if(temp_list==head&&head==tail){
    			free(temp_list);
    			head=0;
    			tail=0;
    		}
    		else if(temp_list==head&&head!=tail){
    			head=temp_list->next;
    			head->pre=0;
    			free(temp_list);
    		}
    		else if(temp_list==tail&&head!=tail){
    			tail=temp_list->pre;
    			tail->next=0;
    			free(temp_list);
    		}
    		else{
    			temp_list->pre->next=temp_list->next;
    			temp_list->next->pre=temp_list->pre;
    			free(temp_list);
    		}
    		return 0;
    	}
    }
    
    int update_item_in_list(struct List *temp_list,int key,int value){
    	if(temp_list==0){return -1;}
    	else{
    		if(temp_list==head){
    			temp_list->value=value;
    		}
    		else if(temp_list==tail&&head!=tail){
    			temp_list->value=value;
    			tail=temp_list->pre;
    			tail->next=0;
    			temp_list->pre=0;
    			temp_list->next=head;
    			head->pre=temp_list;
    			head=temp_list;
    
    		}
    		else{
    			temp_list->value=value;
    			temp_list->pre->next=temp_list->next;
    			temp_list->next->pre=temp_list->pre;
    			temp_list->pre=0;
    			temp_list->next=head;
    			head->pre=temp_list;
    			head=temp_list;
    		}
    		return 0;
    	}
    }
    
    struct Node * find_element_in_hash(int key){
    	struct Node * temp_node=&(hash->node[key%(hash->capacity)]);
    	if(temp_node->position==0) return 0;
    	else{
    		if(temp_node->position->key==key) return temp_node;
    		else{
    			temp_node=temp_node->next;
    			while(temp_node!=0&&temp_node->position->key!=key){
    				temp_node=temp_node->next;
    			}
    			return temp_node;
    		}
    	} 
    }
    
    void insert_element_to_hash(int key,int value){
    	struct Node * temp_node1=&(hash->node[key%(hash->capacity)]);
    	struct Node * temp_node2;
    	if((hash->length)>=0&&(hash->length)<(hash->capacity))
    	{
    		if(temp_node1->position==0){
    			insert_item_to_list(key,value);
    			temp_node1->position=head;
    			temp_node1->next=0;
    			hash->length++;
    		}
    		else{
    			while(temp_node1->position->key!=key&&temp_node1->next!=0){
    				temp_node1=temp_node1->next;
    			}
    			if(temp_node1->position->key==key){
    				update_item_in_list(temp_node1->position,key,value);
    			}
    			else{
    				insert_item_to_list(key,value);
    				temp_node2=(struct Node *)malloc(sizeof(struct Node));
    				temp_node2->position=head;
    				temp_node2->next=0;
    				temp_node1->next=temp_node2;
    				hash->length++;
    			}
    		
    		}
    	}
    	else if((hash->length)==(hash->capacity)){
    		temp_node2=find_element_in_hash(key);
    		if(temp_node2!=0){
    			update_item_in_list(temp_node2->position,key,value);
    			return;
    		}
    		else{
    			temp_node1=&(hash->node[(tail->key)%(hash->capacity)]);
    			if(temp_node1->position->key==tail->key){
    				delete_item_in_list(temp_node1->position);
    				if(temp_node1->next==0){
    					temp_node1->position=0;
    					temp_node1->next=0;
    				}
    				else{
    					temp_node2=temp_node1->next;
    					temp_node1->position=temp_node2->position;
    					temp_node1->next=temp_node2->next;
    					temp_node2->next=0;
    					temp_node2->position=0;
    					free(temp_node2);
    				}
    				hash->length--;
    				insert_element_to_hash(key,value);
    			}
    			else{
    				temp_node2=temp_node1->next;
    				while(temp_node2!=0&&(temp_node2->position->key)!=(tail->key)){
    					temp_node1=temp_node2;
    					temp_node2=temp_node2->next;
    				}
    				delete_item_in_list(temp_node2->position);
    				temp_node1->next=temp_node2->next;
    				free(temp_node2);
    				hash->length--;
    				insert_element_to_hash(key,value);
    			}
    		}
    			
    	}
    	else {return;}
    }
    
    
    
    void lruCacheInit(int capacity) {
    	hash=(struct HashTable *)malloc(sizeof(struct HashTable));
    	hash->node=(struct Node *)malloc(sizeof(struct Node)*capacity);
    	int i=0;
    	for(i=0;i<capacity;i++)
    	{
    		hash->node[i].next=0;
    		hash->node[i].position=0;
    	}
    	hash->length=0;
    	hash->capacity=capacity;
        
    }
    
    void lruCacheFree() {
    	struct Node *temp_node1,*temp_node2;
    	struct List *temp_list1,*temp_list2;
    	temp_list1=head;
    	while(temp_list1!=0){
    		temp_list2=temp_list1->next;
    		free(temp_list1);
    		temp_list1=temp_list2;
    	}
    	int i=0;
    	for(i=0;i<hash->capacity;i++){
    		temp_node1=hash->node[i].next;
    		while(temp_node1!=0){
    			temp_node2=temp_node1->next;
    			free(temp_node1);
    			temp_node1=temp_node2;
    		}
    	}
    	free(hash->node);
    	free(hash);
    	hash=0;
    	head=0;
    	tail=0;
    	temp_list1=0;
    	temp_list2=0;
    	temp_node1=0;
    	temp_node2=0;
    	return;
    }
    
    int lruCacheGet(int key) {
    	struct Node * temp_node=find_element_in_hash(key);
    	if(temp_node==0) {return -1;}
    	else{
    		update_item_in_list(temp_node->position,key,temp_node->position->value);
    		/*printf("\nactually:%d,get:%d\n",key,temp_node->position->key);
    		struct List *mylist;
    		for(mylist=head;mylist!=0;mylist=mylist->next){
    			printf("->%d",mylist->key);
    		}*/
    		return temp_node->position->value;
    	}
    }
        
    void lruCacheSet(int key, int value) {
    	insert_element_to_hash(key,value);
    	/*printf("\nset:%d\n",key);
    	struct List *mylist;
    	for(mylist=head;mylist!=0;mylist=mylist->next){
    		printf("->%d",mylist->key);
    	}*/
    }
    

Log in to reply
 

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