public class DLList<T>
{
// Define private inner class Node.
private class Node
{
T data;
Node next;
Node(T data, Node next)
{
this.data = data;
this.next = next;
}
Node(T data)
{ this(data, null); }
}
// Declare instance fields/variables.
private Node head;
private int count;
// Define default constructor.
public DLList()
{ this.clear(); }
// Define private helper methods.
/*
* Precondition: 0 <= index < this.count.
*/
private Node getNodeAt(int index)
{
Node curr = this.head;
for (int i = 0; i < index; i++)
curr = curr.next;
return curr;
}
// Define methods declared in interface IList<T>.
public int size()
{ return this.count; }
public void clear()
{
this.head = null;
this.count = 0;
}
public T get(int index)
{
T result = null;
if (0 <= index && index < this.count)
result = this.getNodeAt(index).data;
return result;
}
public T set(int index, T data)
{
T result = null;
if (0 <= index && index < this.count) {
Node curr = this.getNodeAt(index);
result = curr.data;
curr.data = data;
}
return result;
}
public boolean add(T data)
{
Node newNode = new Node(data);
if (this.count == 0)
this.head = newNode;
else {
Node prev = this.getNodeAt(this.count - 1);
prev.next = newNode;
}
this.count++;
return true;
}
public boolean add(int index, T data)
{
boolean result = false;
if (0 <= index && index <= this.count) {
if (index == 0) {
Node newNode = new Node(data, this.head);
this.head = newNode;
}
else {
Node prev = this.getNodeAt(index - 1);
Node next = prev.next;
Node newNode = new Node(data, next);
prev.next = newNode;
}
this.count++;
result = true;
}
return result;
}
public T remove(int index)
{
T result = null;
if (0 <= index && index < this.count) {
Node curr = null;
if (index == 0) {
curr = this.head;
this.head = curr.next;
}
else {
Node prev = this.getNodeAt(index - 1);
curr = prev.next;
prev.next = curr.next;
}
this.count--;
result = curr.data;
}
return result;
}
public int indexOf(T that)
{
int result = -1;
Node curr = this.head;
for (int i = 0; result == -1 && i < this.count; i++) {
if (that.equals(curr.data)) result = i;
curr = curr.next;
}
return result;
}
public boolean contains(T that)
{
return this.indexOf(that) >= 0;
}
// Override methods defined in Object.
@Override
public String toString()
{
StringBuilder sb = new StringBuilder("[");
Node curr = this.head;
for (int i = 0; i < this.count; i++) {
if (i > 0) sb.append(", ");
sb.append(curr.data);
curr = curr.next;
}
sb.append(']');
return sb.toString();
}
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object other)
{
boolean result = false;
if (other != null) {
if (this.getClass() == other.getClass()) {
DLList<T> that = (DLList<T>)other;
if (this.size() == that.size()) {
Node thisCurr = this.head;
Node thatCurr = that.head;
for (int i = 0; i < this.count; i++) {
if ( ! thisCurr.data.equals(thatCurr.data)) break;
thisCurr = thisCurr.next;
thatCurr = thatCurr.next;
}
if (thisCurr == null) result = true;
}
}
}
return result;
}
// Define main() method to unit test this class.
public static void main(String[] args)
{
IList<String> list = new DLList<String>();
String s;
int i;
System.out.printf("%d: %s%n", list.size(), list);
list.add("Hello");
System.out.printf("%d: %s%n", list.size(), list);
list.add("World");
System.out.printf("%d: %s%n", list.size(), list);
list.add(0, "Well");
System.out.printf("%d: %s%n", list.size(), list);
list.add(2, "New");
System.out.printf("%d: %s%n", list.size(), list);
list.add(list.size(), ".");
System.out.printf("%d: %s%n", list.size(), list);
s = list.get(2);
System.out.printf("retrieved at %d: %s%n", 2, s);
s = list.set(2, "new");
System.out.printf("replaced at %d: %s%n", 2, s);
System.out.printf("%d: %s%n", list.size(), list);
s = list.get(5);
System.out.printf("retrieved at %d: %s%n", 5, s);
i = list.indexOf("new");
System.out.printf("String /%s/ found at: %d%n", "new", i);
i = list.indexOf("old");
System.out.printf("String /%s/ found at: %d%n", "old", i);
s = list.remove(0);
System.out.printf("removed at %d: %s%n", 0, s);
System.out.printf("%d: %s%n", list.size(), list);
s = list.remove(list.size() - 1);
System.out.printf("removed at %d: %s%n", list.size(), s);
System.out.printf("%d: %s%n", list.size(), list);
s = list.remove(0);
System.out.printf("removed at %d: %s%n", 0, s);
System.out.printf("%d: %s%n", list.size(), list);
s = list.remove(0);
System.out.printf("removed at %d: %s%n", 0, s);
System.out.printf("%d: %s%n", list.size(), list);
s = list.remove(0);
System.out.printf("removed at %d: %s%n", 0, s);
System.out.printf("%d: %s%n", list.size(), list);
IList<String> la = new DLList<String>();
IList<String> lb = new DLList<String>();
for (char c = 'a'; c <= 'e'; c++) {
s = String.format("%c", c);
la.add(s);
lb.add(s);
}
System.out.println();
System.out.printf("%d: %s%n", la.size(), la);
System.out.printf("%d: %s%n", lb.size(), lb);
System.out.printf("la.equals(lb): %b%n", la.equals(lb));
lb.set(3, "D");
System.out.printf("%d: %s%n", lb.size(), lb);
System.out.printf("la.equals(lb): %b%n", la.equals(lb));
}
}