You must implement a BlockedList class that implements the List
interface. You
may use any of the classes in JCF or in the textbook code. The
constructor for this class takes an
integer block size b and the implementation should have the
following performance characteristics:
a) get(i) and set(i,x) should run in O(1) time per operation
b) add(i,x) and remove(i) should run in O(b+ min{i, n-i}/b)
amortized time per operation.
Any solution matching this specification is acceptable. However,
the runtime would suggest a data
structure that contains other data structures, or “blocks” of size
at most b. For one possible solution,
recall that an array backed Deque (an ArrayDeque in the textbook,
or a Deque in the JCF)
implements add(i,x) and remove(i) in O(min{i, n-i}) amortized time
per operation. We want a data
structure with performance characteristics similar to an ArrayDeque
(within a factor of b). We
might therefore consider an ArrayDeque of data structures. It is
then left to you to determine the
inner data structure. Also note, if we choose a block size of b=1,
then we simply have an ArrayDeque
running in O(b+ min{i, n-i}/b) = O(min{i, n-i}) amortized time per
operation, as required,
regardless of the inner data structure chosen.
Java
For this question, I have used the java list interface itself. (I have not implemented all the methods, just the required methods are implemented by me)
First of all, we need to understand that to archive get(i) and set(i,x) in O(1), we need a data structure in which we can access data elements in O(1). Such a data structure is Arrays in Java. So we'll use the Integer array for our task.
-------------------------------------------------------
public Object get(int i) { if(i>data.length) return null; else return data[i]; }
---------------------------------------------------------
---------------------------------------------------------
public Object set(int i, Object o) { data[i] = (Integer)o; return data[i]; }
---------------------------------------------------------
Code for it is -------------------------------------------
public void add(int i, Object o) { int max = i>data.length?i:data.length; int min = i<data.length?i:data.length Integer temp[] = new Integer[max]; for(int a=0;a<min;++a) temp[a]=data[a]; temp[i] = (Integer) o; for(int a=i+1;a<max;++a) temp[a] = data[a]; data = temp; } @Override public Object remove(int i) { Integer temp[] = new Integer[data.length-1]; for(int k=0;k<i;++k) temp[k]=data[k]; for(int k=i+1;k<data.length;++k) temp[k] = data[k]; int removed = data[i]; data = temp; return removed; }
-----------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Entire Code
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.ListIterator; public class BlockedList implements List { private Integer data[]; BlockedList(int b){ data = new Integer[b]; } @Override public int size() { return data.length; } @Override public boolean isEmpty() { return data.length==0?true:false; } @Override public boolean contains(Object o) { Integer val = (Integer)o; for( Integer i : data){ if(i.intValue() == val.intValue()) return true; } return false; } @Override public Iterator iterator() { return null; } @Override public Object[] toArray() { return data; } @Override public boolean add(Object o) { return false; } @Override public boolean remove(Object o) { return false; } @Override public boolean addAll(Collection collection) { return false; } @Override public boolean addAll(int i, Collection collection) { return false; } @Override public void clear() { } @Override public Object get(int i) { if(i>data.length) return null; else return data[i]; } @Override public Object set(int i, Object o) { data[i] = (Integer)o; return data[i]; } @Override public void add(int i, Object o) { int max = i>data.length?i:data.length; int min = i<data.length?i:data.length Integer temp[] = new Integer[max]; for(int a=0;a<min;++a) temp[a]=data[a]; temp[i] = (Integer) o; for(int a=i+1;a<max;++a) temp[a] = data[a]; data = temp; } @Override public Object remove(int i) { Integer temp[] = new Integer[data.length-1]; for(int k=0;k<i;++k) temp[k]=data[k]; for(int k=i+1;k<data.length;++k) temp[k] = data[k]; int removed = data[i]; data = temp; return removed; } @Override public int indexOf(Object o) { return 0; } @Override public int lastIndexOf(Object o) { return 0; } @Override public ListIterator listIterator() { return null; } @Override public ListIterator listIterator(int i) { return null; } @Override public List subList(int i, int i1) { return null; } @Override public boolean retainAll(Collection collection) { return false; } @Override public boolean removeAll(Collection collection) { return false; } @Override public boolean containsAll(Collection collection) { return false; } @Override public Object[] toArray(Object[] objects) { return new Object[0]; } }
You must implement a BlockedList class that implements the List interface. You may use any of...
(Deque) A deque is a data structure consisting of a list of items on which the following operations are possible: a. push (x) : Insert item x on the front end of the deque. b. pop ): Remove the front item from the deque and return it. c. inject(x): Insert item x on the rear end of the deque. d. eject ): Remove the rear item from the deque and return it. Write routines to support the deque that take...
Given a singly-linked list interface and linked list node class, implement the singly-linked list which has the following methods in Java: 1. Implement 3 add() methods. One will add to the front (must be O(1)), one will add to the back (must be O(1)), and one will add anywhere in the list according to given index (must be O(1) for index 0 and O(n) for all other indices). They are: void addAtIndex(int index, T data), void addToFront(T data), void addToBack(T...
Implement the EasyStack interface with the MyStack class. You can use either a linked list or a dynamic array to implement the data structure. A stack is a specialised form of list in which you can only get and remove the element most recently added to the stack. The class should be able to work with the following code: EasyStack stack = new MyStack(); NB: You cannot import anything from the standard library for this task. The data structure must...
package model; import java.util.Iterator; /** * This class implements interface PriorityList<E> to represent a generic * collection to store elements where indexes represent priorities and the * priorities can change in several ways. * * This collection class uses an Object[] data structure to store elements. * * @param <E> The type of all elements stored in this collection */ // You will have an error until you have have all methods // specified in interface PriorityList included inside this...
Interfaces 1. What is inside an interface definition? What does a class do to an interface and what keyword is involved? How does a class do this to an interface (what should we find in the class)? Can an interface have a generic parameter? How do you instantiate an interface as an object? What methods can’t you use on an interface type? Abstract Data Types 2. What does an ADT define? Does an ADT specify programming language and/or data structures...
Template Deque Class (C++) In this assignment, we will use a given test menu for the template Deque Class (a Linked List based Double Ended Queue, Deque) that you have put together. Recommended Steps testDeque.cpp : // C++ implementation of doubly linked list Deque doubly linked list #include <bits/stdc++.h> using namespace std; class Timer { // To replace with the full timer class definition // inside this folder: LearnCpp9_18_timeSortArray.cpp }; // Node of a doubly linked list template<class T> class...
Template Dequeue Class (C++ ) In this assignment, we will use a given test menu for the template Deque Class (a Linked List based Double Ended Queue, Deque) that you have put together. Starter testDeque.cpp which contains: Timer class holder (you need to go through the LearnCpp Ch15 and import it in) Node class Deque class specification (you need to fill out the definition) here is the testDeque.cpp code: // C++ implementation of doubly linked list Deque doubly linked list...
Create a linked list with given code Given code: import java.util.Iterator; public interface Set { /** Removes all of the elements from this set */ void clear(); /** Returns true if this set contains no elements @return true if this set contains no elements */ boolean isEmpty(); /** Returns the number of elements in this set (its cardinality) @return the number of elements in this set */ int size(); /** Returns an iterator over the elements in this set @return...
Comparing the insertion and removing performance between ALPQueue with HeapPQueue. Requirements: 1/ Task1: implement a concrete ALPQueue class (an ArrayList based priority queue) that extends the AbstractPQueue discussed in the class, along with PQueue.java, ArrayList.java, List.java, PQEntry.java , EntryComparitor.java, and OutOfRangeException.java given in the class (any other implementation of above classes that are not compatible with List interface and AbstractPQueue class will not receive any credit). 2/ Task2: implement a concrete HeapPQueue class (a Heap based priority queue) that extends...
Problem: Implement an interface that manipulates a list of strings. You will be provided with the following files (see below): • StringList.h containing a class declaration, set up for a linked list representation. • Driver.cpp containing a main function you can use to test your implementation. You will be responsible for providing the StringList.cpp file, including the implementation of the StringList member functions (described below): StringList and ~StringList: creates an empty list, and deallocates all the nodes in the list,...