- Implement Insert and Delete for a Singly Linked List.
public interface Link<E> {
public Link<E> getNext();
public void setNext(Link<E> link);
public Link<E> getPrev();
public void setPrev(Link<E> link);
public E getValue();
public void setValue(E value);
}
public class SingleLink<E> implements Link<E> {
public SingleLink(E value) { this.value = value; }
private Link<E> next;
private E value;
public Link<E> getNext() { return next; }
public void setNext(Link<E> next) { this.next = next;}
public Link<E> getPrev() { throw new UnsupportedOperationException(); }
public void setPrev(Link<E> prev) { throw new UnsupportedOperationException(); }
public E getValue() { return value; }
public void setValue(E value) { this.value = value;}
@Override
public boolean equals(Object obj) { return this.value.equals(obj); }
@Override
public String toString() { return getValue().toString(); }
}
public abstract class LinkedList<E> {
protected abstract Link<E> createHead(E value);
protected abstract Link<E> removeHead();
protected abstract Link<E> append(Link<E> tail, E value);
protected abstract void chain(Link<E> from, Link<E> to);
protected abstract void deleteAfterHead(E value);
protected abstract boolean isInsert(Link<E> link);
protected abstract boolean isEnd(Link<E> link);
public void insert(E value) {
if (head == null) {
createHead(value);
return;
}
Link<E> tmp = head;
while (!isInsert(tmp))
tmp = tmp.getNext();
append(tmp, value);
}
public void delete(E value) {
if (head == null)
return;
if (head.equals(value)) {
removeHead();
return;
}
deleteAfterHead(value);
}
Link<E> head;
}
public class SinglyLinkedList<E> extends LinkedList<E> {
@Override
protected Link<E> createHead(E value) {
if (value != null) {
head = new SingleLink<E>(value);
} else {
head = null;
}
return head;
}
@Override
protected Link<E> removeHead() {
if (isEnd(head.getNext())) {
head = null;
return null;
}
head = head.getNext();
return head;
}
@Override
protected Link<E> append(Link<E> tail, E value) {
Link<E> link = new SingleLink<E>(value);
tail.setNext(link);
return link;
}
@Override
protected void chain(Link<E> from, Link<E> to) {
from.setNext(to);
}
@Override
protected void deleteAfterHead(E value) {
Link<E> tmp = head.getNext();
Link<E> prev = head;
while (!isEnd(tmp)) {
if (tmp.equals(value)) {
chain(prev, tmp.getNext());
break;
}
prev = tmp;
tmp = tmp.getNext();
}
}
@Override
protected boolean isInsert(Link<E> link) {
return isEnd(link.getNext());
}
@Override
protected boolean isEnd(Link<E> link) {
return link == null;
}
}
- Implement Insert and Delete for a Doubly Linked List.
public class DoubleLink<E> extends SingleLink<E> {
public DoubleLink(E value) { super(value); }
private Link<E> prev;
@Override
public Link<E> getPrev() { return prev; }
@Override
public void setPrev(Link<E> prev) { this.prev = prev; }
}
public class DoublyLinkedList<E> extends SinglyLinkedList<E> {
@Override
protected Link<E> createHead(E value) {
if (value != null) {
head = new DoubleLink<E>(value);
} else {
head = null;
}
return head;
}
@Override
protected Link<E> removeHead() {
head = super.removeHead();
if (head != null) {
head.setPrev(null);
}
return head;
}
@Override
protected Link<E> append(Link<E> tail, E value) {
Link<E> link = new DoubleLink<E>(value);
tail.setNext(link);
link.setPrev(tail);
return link;
}
@Override
protected void chain(Link<E> from, Link<E> to) {
from.setNext(to);
if (to != null) {
to.setPrev(from);
}
}
@Override
protected void deleteAfterHead(E value) {
Link<E> tmp = head.getNext();
while (!isEnd(tmp)) {
if (tmp.equals(value)) {
chain(tmp.getPrev(), tmp.getNext());
break;
}
tmp = tmp.getNext();
}
}
}
- Implement Insert and Delete for a Sorted Linked List.
public class SortedLinkedList<E> extends SinglyLinkedList<E> {
@Override
public void insert(E value) {
if (head == null) {
createHead(value);
return;
}
Link<E> tmp = head;
Link<E> prev = null;
// XXX: yuck, dynamic casting to Comparable
while (!isEnd(tmp) &&
Comparable<E>) tmp.getValue()).compareTo(value) < 0) {
prev = tmp;
tmp = tmp.getNext();
}
Link<E> link = new SingleLink<E>(value);
if (prev == null) {
link.setNext(head);
head = link;
} else {
prev.setNext(link);
link.setNext(tmp);
}
}
}
- Implement Insert and Delete for a Circular Linked List.
public class CircularLinkedList<E> extends DoublyLinkedList<E> {
@Override
protected Link<E> createHead(E value) {
head = super.createHead(value);
if (head != null) {
head.setNext(head);
head.setPrev(head);
}
return head;
}
@Override
protected Link<E> removeHead() {
if (head.getNext() == head) {
head = null;
return null;
}
Link<E> prev = head.getPrev();
head = head.getNext();
head.setPrev(prev);
prev.setNext(head);
return head;
}
@Override
protected Link<E> append(Link<E> tail, E value) {
Link<E> link = new DoubleLink<E>(value);
tail.setNext(link);
link.setPrev(tail);
link.setNext(head);
head.setPrev(link);
return link;
}
@Override
protected boolean isEnd(Link link) {
return link == head;
}
@Override
protected boolean isInsert(Link link) {
return link.getNext() == head;
}
}
