Write a new method named count(E o) that returns the number of elements in the list that are equivalent to
the specified object.
Write a new method named reverse() that reverses the order of the nodes in the list. Can you figure out a
way of doing this non-recursively in O(n) time?
These method above is the method I am having a problem with.
Below is my code.
import java.util.NoSuchElementException;
public class LinkedList<E> implements List<E>
{
// Nested class, since only LinkedList ever uses LLNode
private static class LLNode<E>
{
private E data; // data stored in this node
private LLNode<E> next; // a reference to the next node in the list
public LLNode(E data, LLNode<E> next)
{
this.data = data;
this.next = next;
}
}
// The only node a linked list needs to keep track of is the head node.
// From there, you can reach any other node in the list!
private LLNode<E> head = null;
// tracks how many items have been added to the list
private int size = 0;
//remove all elements in the list
public void clear()
{
head =null;
size=0;
}
public int count(E o)
{
}
//Returns the data at the specified index
// Big-O: O(n)
public E get(int index)
{
return nodeAt(index).data;
}
// Replaces the data at the specified index
// Big-O: O(n)
public void set(int index, E newData)
{
nodeAt(index).data = newData;
}
// Inserts a new node containing the specified data to the end of the list
// Big-O: O(1) if the list is empty, and O(n) otherwise
public void add(E newData)
{
if (head == null) // if the list is empty...
addToHead(newData);
else
addAfter(newData, nodeAt(size-1));
}
// Removes the node at the specified index from the list
// Big-O: O(1) if removing from the head, and O(n) otherwise
public void remove(int index)
{
if (index == 0) // to remove from the head of the list...
removeFromHead();
else
removeAfter(nodeAt(index-1));
}
// These methods are declared as private because they aren't meant to be
// called from other classes. We'll be calling them from within
// LinkedList when implementing the get, set, add, and remove methods.
// Removes the head node from the list.
private void removeFromHead()
{
if (head != null) {
head = head.next;
size--;
} else {
throw new NoSuchElementException();
}
}
// Removes the node after "where" from the list.
private void removeAfter(LLNode<E> where)
{
if (where != null && where.next != null) {
where.next = where.next.next;
size--;
} else {
throw new NoSuchElementException();
}
}
// Adds a new node with the specified data to the front of the list.
private void addToHead(E data)
{
LLNode<E> newNode = new LLNode<E>(data, head);
head = newNode;
size++;
}
// Adds a new node with the specified data after "where" on the list.
private void addAfter(E data, LLNode<E> where)
{
if (where != null) {
LLNode<E> newNode = new LLNode<E>(data, where.next);
where.next = newNode;
size++;
} else {
throw new NoSuchElementException();
}
}
// Returns a reference to the node at the specified index.
private LLNode<E> nodeAt(int index)
{
if (index >= 0 && index < size) {
LLNode<E> temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
} else {
throw new NoSuchElementException();
}
}
public String toString()
{
String s = "head -> ";
// traverse the list from head to tail
LLNode<E> temp = head;
while (temp != null) {
s += temp.data + " -> ";
temp = temp.next;
}
s += "null";
return s;
}
public static void main(String[] args)
{
List<Integer> myList = new LinkedList<Integer>();
for (int i = 0; i < 25; i++)
myList.add(i);
System.out.println(myList);
myList.remove(7);
System.out.println(myList);
myList.remove(25);
}
}
