A hierarchical linked list (HL) is a variant of a standard ordered singly linked
ID: 3594945 • Letter: A
Question
A hierarchical linked list (HL) is a variant of a standard ordered singly linked list, containing next and sub-level pointers. The head of the HL points to a top-level list containing only a subset of the n elements. To search the list, we begin by searching the top-level list until the current element is less than desired and the next element is greater than desired. At this point, we traverse the sub-level pointer of the current element and continue the search in a recursive manner. At some point, the appropriate key will be found or we will run out of elements at the particular level.
a. What condition must each of the elements in a sub-level list meet with respect to the elements in the parent list, for searching to be complete?
b. Assuming you can build the hierarchical list in the optimal way (because, for example, you know everything it will contain) what are the worst-case time bounds for Insert, Delete and Search? Defend your answer with an analogy or logical explanation.
Some clarification
One way to think of this is: Start with two lists and let the top-level linked list be an express list or express train line (containing a subset of the n elements or train stops) and the lower level list containing all n elements or all train stops. To get to a train stop fast you might first take an express train to a stop before the one you want and then switch to the slower train (lower level list) that makes every stop. The bottom list should contain all elements. The switch from the top list to the lower list is by a link between the two at the point that allows a switch.
H -> 12_____________43________54________________98_____105
12__20_23__33__43_44_45__54__63_65__76_77__98_100_105
To expand this you could also add a super express line
H -> 12_______________________54_______________________105
12_____________43________54________________98_____105
12__20_23__33__43_44_45__54__63_65__76_77__98_100_105
For part b. you can assume that you have an OPTIMALLY built HL structure to start with – size n nodes (this will have properties similar to a tree - say what that might be). Then consider the operations of Insert, Delete and Search. Search is easiest. In particular, what can you do when you Insert so that this data structure is fast? Then think about Delete, which can also be easy.
Explanation / Answer
Assignment1.txt
clear
add 1 San Francisco
size
is_empty
get 1
set 4 Salt Lake City
add 7 San Francisco
add_last Washington, D.C.
remove 5
rotate
print_list
Assignment1.java
package com.list;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
public class Assignment1 {
public static void main(String[] args) {
BufferedReader br=null;
FileInputStream fstream=null;
try {
fstream=new FileInputStream("assignment1.txt");
CircularLinkedList<String> circularLinkedList= new CircularLinkedList<String>();
//BufferedInputStream bInputStream= new BufferedInputStream(fstream);
//bInputStream.
br = new BufferedReader(new InputStreamReader(fstream));
StringBuilder sb = new StringBuilder();
String line = br.readLine();
int i=1;
while (null!=line) {
sb.append(line);
sb.append(System.lineSeparator());
//System.out.println(line);
executeCommand(line,circularLinkedList);
line = br.readLine();
i++;
}
//String everything = sb.toString();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if(br!=null){
br.close();
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
private static void executeCommand(String line, CircularLinkedList<String> circularLinkedList) {
String result=null;
//System.out.println("=============="+line);
String[] commands=line.split(" ");
if("clear".equals(commands[0])){
System.out.println("The circular linked list is now clear");
}
else if("size".equals(commands[0])){
int size=circularLinkedList.size();
System.out.println("The circular linked list contains "+size+" strings.");
}else if("is_empty".equals(commands[0])){
boolean isEmpty=circularLinkedList.isEmpty();
if(isEmpty){
System.out.println("The circular linked list is empty.");
}else{
System.out.println("The circular linked list is not empty.");
}
}
else if("get".equals(commands[0])){
String isEmpty=circularLinkedList.get(Integer.parseInt(commands[1]));
System.out.println("The string at position "+commands[1]+" in the circular linked list is ""+isEmpty+""");
}
else if("set".equals(commands[0])){
result=circularLinkedList.set(Integer.parseInt(commands[1]),commands[2]);
System.out.println("The string "+commands[2]+" replaces the string "+result+ "st position "+commands[1]+" in the circular linked list.");
}
else if("add".equals(commands[0])){
circularLinkedList.add(Integer.parseInt(commands[1]), commands[2]);
System.out.println("Added the string "+commands[2]+" at position "+commands[1]+" in the circular linked list.");
}
else if("add_last".equals(commands[0])){
boolean isEmpty=circularLinkedList.add(commands[1]);
System.out.println("Added the string "+commands[1]+" in the last");
}
else if("remove".equals(commands[0])){
result=circularLinkedList.remove(Integer.parseInt(commands[1]));
System.out.println("Removed the string "+result+" at position "+commands[1]+" from the cicular linked list");
}
else if("rotate".equals(commands[0])){
circularLinkedList.rotate();
System.out.println("The value at the head of the circular linked list was rotated to the tail of the Circular linked list.");
}
else if("print_list".equals(commands[0])){
if(circularLinkedList!=null){
System.out.println("The circular linked list contains:");
Iterator<String> st=circularLinkedList.iterator();
while(st.hasNext()){
System.out.println(st);
}
}else{
System.out.println("The cicular linked list is empty");
}
}
}
}
CircularLinkedList.java
package com.list;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class CircularLinkedList<E> implements List<E> {
private static class Node<E>{
private E data;
private Node<E> next;
public Node(E d,Node<E>n){
setData(d);
setNext(n);
}
public E getData(){
return data;
}
public void setNext(Node<E> n) {
next=n;
}
public void setData(E d) {
data=d;
}
public Node<E> getNext(){
return next;
}
}
private int theSize;
private int modCount;
private Node<E> tail;
public CircularLinkedList() {
}
@Override
public void clear() {
if(size()!=0){
for(int i=size()-1;i>=0;i--){
Node<E> node=getNode(i);
node.next=null;
node.data=null;
}
}
theSize=0;
modCount++;
}
@Override
public int size() {
return theSize;
}
@Override
public boolean isEmpty() {
if(theSize==0){
return true;
}
return false;
}
@Override
public E get(int arg0) {
return null;
}
@Override
public E set(int arg0, E arg1) {
return null;
}
@Override
public boolean add(E newValue) {
add(size(),newValue);
return true;
//No need to implement
//return false;
}
@Override
public void add(int arg0, E arg1) {
theSize++;
}
@Override
public boolean addAll(Collection<? extends E> arg0) {
return false;
}
@Override
public boolean addAll(int arg0, Collection<? extends E> arg1) {
return false;
}
@Override
public boolean contains(Object arg0) {
return false;
}
@Override
public boolean containsAll(Collection<?> arg0) {
return false;
}
@Override
public int indexOf(Object arg0) {
return 0;
}
@Override
public Iterator<E> iterator() {
return new LinkedListIterator();
}
@Override
public int lastIndexOf(Object arg0) {
return 0;
}
@Override
public ListIterator<E> listIterator() {
return null;
}
@Override
public ListIterator<E> listIterator(int arg0) {
return null;
}
@Override
public boolean remove(Object arg0) {
return false;
}
@Override
public E remove(int arg0) {
return null;
}
private Node<E> getNode(int index){
return (getNode(index,0,size()-1));
}
private Node<E> getNode(int index,int lower,int upper){
return null;
}
public void rotate(){
}
@Override
public boolean removeAll(Collection<?> arg0) {
return false;
}
@Override
public boolean retainAll(Collection<?> arg0) {
return false;
}
@Override
public List<E> subList(int arg0, int arg1) {
return null;
}
@Override
public Object[] toArray() {
return null;
}
@Override
public <T> T[] toArray(T[] arg0) {
return null;
}
private class LinkedListIterator implements Iterator<E>{
private Node<E> previous;
private Node<E> current;
private int expectedModCount;
private boolean okToRemove;
public LinkedListIterator() {
}
@Override
public boolean hasNext() {
return false;
}
@Override
public E next() {
return null;
}
public void remove(){
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.