CS310 Sorted Linked Array List

You are tasked to implement a linear data structure that is essenetially a linked list of arrays. Each node of the linked list has at most k elements and at least floor(k/2) elements unless the linked list has only one node. In that case, the node can have 0 to k elements stored in the node.

This data structure stores numbers in ascending sorted order (from small to large) and supports the operations to find, insert and delete numbers.

Introduction and Definitions

The follow code is provided to you. There are three java files: PA01.java, SLAL.java and Node.java.

PA01.java handles I/O and is responsible for creating the linked list. SLAL.java defines the linked list.

public class SLAL {

//data
private int K;
private Node head, tail;

//methods
public SLAL(int _K);
public Node find(double value);
public void insert(double value);
public void remove(double value);

//... additional methods for acessing data & IO ....
}

Node.java defines the node that contains an array of at most K data.

public class Node {

//data
private int K;
private int size;
private double data[];
private Node prev, next;

//methods
public Node(int _K);
public int find(double value);
public Node split();
public boolean merge();

//... additional methods for acessing data & IO ....
}

Tasks

Implement Find Methods

Given a number, implement methods to (1) find the node that may contain the number, and (2) find the location of the number in the node, or (3) report that the number is not in the list.

class SLAL {
Node find(double value) //10 points
{
//find the node that contains the value or return null if no node contains the given value
}
}


class Node {
int find(double value) //15 points
{
//find the position of the value inside the array or return -1 when the value is not found
//MUST take O(log K) time where K is the max size of the array.
}
}

Implement Insert Methods

Given a number, implement methods to (1) insert the number to SLAL and ensure that the constraints are not violated or (2) report that the number is already in the list.

class SLAL {
void insert(double value) //10 points
{
//1. find the FIRST node N that this value can be inserted. If the list is empty create a new node.
//2. call insert method of the node N
//3. if a new node is created, insert the new node after the node N
}
}

class Node {
Node insert(double value) //10 points
{
//(1) check if value is already in this node. If so, report duplication and return null.
//(2) find the location to insert the value into the array
//(3) if the array size is larger than K, then call split(); insert the value
// to this Node or the new Node and return the new Node
}

Node split() //10 points
{
//(1) split the array into two arrays with floor(K/2) and K-floor(K/2) elements each.
//(2) Create a new Node that contains data in the second array
//(3) return this new Node
}
}

Implement Delete Methods

Given a number, implement methods to (1) remove the number from SLAL and ensure that the constraints are not violated or (2) report that the number is not in the list.

class SLAL {
void remove(double value) //10 points
{
//1. find the node N that may contain this value
//2. call remove method of the node N
//3. if N returns true, remove N from the list
}
}

class Node {
boolean remove(double value) //10 points
{
//(1) check if value is in this node. If not, report "value not found" and return false.
//(2) delete the value from the array in this node
//(3) if the array size in this node becomes less than floor(K/2), return merge(),
// with the only exception that this is the only node in the list.
}

boolean merge() //20 points
{
//(1) Let M be one of the neighboring nodes that has the smaller array size.
// If both neighbors have the same size, pick the prev node.
//(2) If M has more than or euqal to floor(K/2)+1 elements, borrow one value from M
// and add it to this node. Return false
// (meaning that this node will NOT be removed from the list).
//(3) If M has exactly floor(K/2) elements, add all values in this node to M.
// Return true. (meaning that this node should be removed from the list).
}
}

Complete README.txt

You should complete the provided README.txt and submit it with the rest of the code.