An adjacency list as you can see is nothing more than an array of linked lists.
ID: 3838729 • Letter: A
Question
An adjacency list as you can see is nothing more than an array of linked lists. One of the problems faced when creating such a list is to decide where each city belongs in the array. The obvious choice here is to use a hash function to place the initial cities. Your assignment is to create a graph using an adjacency list and use the above example to populate the list. What this means is that you should be able to create the list by hasing the initial city to determine the location within the arry it will be located.Explanation / Answer
PROGRAM CODE:
LList.java
package adjacencylist;
public class LList<T> {
public class Node
{
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
} // end constructor
public Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor
public T getData()
{
return data;
} // end getData
public void setData(T newData)
{
data = newData;
} // end setData
public Node getNextNode()
{
return next;
} // end getNextNode
public void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
public Node firstNode; // Reference to first node of chain
private int numberOfEntries;
public LList() {
firstNode = null;
numberOfEntries = 0;
}
public void add(T newEntry) // OutOfMemoryError possible
{
Node newNode = new Node(newEntry);
if (isEmpty())
{
firstNode = new Node(null, newNode); // this line would add an empty dummy node at the beginning of the list
}
else // Add to end of non-empty list
{
Node lastNode = getNodeAt(numberOfEntries);
lastNode.setNextNode(newNode); // Make last node reference new node
} // end if
numberOfEntries++;
} // end add
public void add(int newPosition, T newEntry)
{
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1))
{
Node newNode = new Node(newEntry);
if (newPosition == 1) // Case 1
{
newNode.setNextNode(firstNode);
firstNode = newNode;
}
else // Case 2: list is not empty
{ // and newPosition > 1
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);
} // end if
numberOfEntries++;
}
else
throw new IndexOutOfBoundsException("Illegal position given to add operation.");
} // end add
public int getLength()
{
return numberOfEntries;
} // end getLength
public boolean isEmpty()
{
boolean result;
if (numberOfEntries == 0) // Or getLength() == 0
{
assert firstNode == null;
result = true;
}
else
{
assert firstNode != null;
result = false;
} // end if
return result;
} // end isEmpty
public Node getNodeAt(int givenPosition)
{
assert !isEmpty() && (1 <= givenPosition) && (givenPosition <= numberOfEntries);
Node currentNode = firstNode;
// Traverse the chain to locate the desired node
// (skipped if givenPosition is 1)
for (int counter = 1; counter < givenPosition; counter++)
currentNode = currentNode.getNextNode();
assert currentNode != null;
return currentNode;
} // end getNodeAt
@Override
public String toString() {
String result = "[ ";
Node temp = firstNode;
while(temp != null)
{
result += temp.getData() + " ";
temp = temp.getNextNode();
}
result += "]";
return result;
}
}
AdjacencyList.java
package adjacencylist;
import java.util.ArrayList;
public class AdjacencyList<T> {
ArrayList<LList<T>> list;
int capacity;
double loadFactor;
int threshold;
int size;
public AdjacencyList(int capacity, double loadFactor) {
list = new ArrayList<>(capacity);
for(int i=0; i<capacity; i++)
list.add(new LList<>());
this.capacity = capacity;
this.loadFactor = loadFactor;
threshold = (int) (loadFactor*capacity);
size = 0;
}
void insert(T data)
{
int hashcode = hashCode(data);
list.get(hashcode).add(data);
size++;
if(threshold == size)
rehash();
}
private void rehash()
{
int newCapacity = capacity*2 + 1;
threshold = (int)(loadFactor*newCapacity);
capacity = newCapacity;
ArrayList<LList<T>> newList = new ArrayList<>(capacity);
for(int i=0; i<capacity; i++)
newList.add(new LList<>());
for(int i=0; i<size; i++)
{
LList<T> nodeList = list.get(i);
if(nodeList.getNodeAt(0)!= null && nodeList.getNodeAt(0).getData()!= null)
{
int hashCode = hashCode(nodeList.getNodeAt(0).getData());
newList.set(hashCode, nodeList);
}
}
list = newList;
}
@Override
public String toString() {
return list.toString();
}
private int hashCode(T key)
{
int hash = Math.abs(key.hashCode())%capacity;
//System.out.println(hash);
return hash;
}
public static void main(String args[])
{
AdjacencyList<String> lakes = new AdjacencyList<String>(5, 0.75);
lakes.insert("Canyon Lake");
lakes.insert("Lake Elsinore");
lakes.insert("Sun City");
lakes.insert("Menifee");
System.out.println(lakes);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.