I'm in a need to create a data-structure based on Linked list, Array, And constant memory usage.As an input i get two numbers: N and M.N represents maximum capacity of a disk-on-key, M represents maximum capacity of a computer hard-drive, So that M>N.So i need to create a program that 'moves' information from the hard-drive to the disk-on-key, That program needs to implements the following methods:[*]Insert(data) - Inserts the data into the disk-on-key, If its full it removes the data least important(*): worst case run-time O(1).[*]delete(data) - deletes the given data from the disk-on-key - O(1)(*) the user can change the file importance.Maximum amount of memory usage is O(M)What i did so far:I've created an array [1...M] which will 'hold' the computer data, I've created a doubly linked list which will hold the disk-on-key data. [The idea is: each time a data is added to the disk-on-key it will be added to the linked list, and i can go directly to the data using the array as a index(/key) storage.]My computer data fields:\[code\]node firstNode;node currentNode; node[] dataCollection; // Will hold computer hard-drive data\[/code\]So i wanted to create method replacing the least important data with data i want to add [so i'll be able to use in Insert], My code for replace:\[code\]public void replace(int leastImportantdata, int insertData){ node leastImportant = dataCollection[leastImportantdata]; if (leastImportant.prev!=null) leastImportant.prev.next=dataCollection[insertData-1]; if (leastImportant.next!=null) leastImportant.next.prev=dataCollection[insertData-1]; numOfReplacements++;\[/code\]So, my main problem is finding the least important data given those two 'combined' data structures and still keeping a run-time of O(1), Especially when the user decides to change the files importance.
- Say that we start with {4,3,2,1} (numbers represents importance) the least important data would be 1.Suddenly, the user decided to change the last file importance to 5, we get {4,3,2,5} and least important data is 2.