linkedlist.java

java 简单模拟DBMS功能

class LinkedList {
  private transient LinkList header = new LinkList(null, null, null);

  private transient int size = 0;

  private transient int modCount = 0;

  public LinkedList() {
    header.next = header.previous = header;
  }

  public Object getFirst() {
    if (size == 0) {
      throw new NoSuchElementException();
    }

    return header.next.element;
  }

  public Object getLast() {
    if (size == 0) {
      throw new NoSuchElementException();
    }

    return header.previous.element;
  }

  public Object removeFirst() {
    Object first = header.next.element;
    remove(header.next);
    return first;
  }

  public Object removeLast() {
    Object last = header.previous.element;
    remove(header.previous);
    return last;
  }

  public boolean contains(Object o) {
    return indexOf(o) != -1;
  }

  public int size() {
    return size;
  }

  public boolean add(Object o) {
    LinkList newLinkList = new LinkList(o, header, header.previous);
    newLinkList.previous.next = newLinkList;
    newLinkList.next.previous = newLinkList;
    size++;
    modCount++;
    return true;
  }

  public boolean remove(Object o) {
    if (o == null) {
      for (LinkList e = header.next; e != header; e = e.next) {
        if (e.element == null) {
          if (e == header) {
            throw new NoSuchElementException();
          }
          e.previous.next = e.next;
          e.next.previous = e.previous;
          size--;
          modCount++;
          return true;
        }
      }
    }
    else {
      for (LinkList e = header.next; e != header; e = e.next) {
        if (o.equals(e.element)) {
          if (e == header) {
            throw new NoSuchElementException();
          }
          e.previous.next = e.next;
          e.next.previous = e.previous;
          size--;
          modCount++;
          return true;
        }
      }
    }
    return false;
  }

  public void clear() {
    modCount++;
    header.next = header.previous = header;
    size = 0;
  }

  public Object get(int index) {
    return LinkList(index).element;
  }

  public Object set(int index, Object element) {
    LinkList e = LinkList(index);
    Object oldVal = e.element;
    e.element = element;
    return oldVal;
  }

  public void add(int index, Object element) {
    LinkList newLinkList = new LinkList(element, (index == size ? header
                                                  : LinkList(index)),
                                        (index == size ? header :
                                         LinkList(index)).previous);
    newLinkList.previous.next = newLinkList;
    newLinkList.next.previous = newLinkList;
    size++;
    modCount++;
  }

  public Object remove(int index) {
    LinkList e = LinkList(index);
    if (e == header) {
      throw new NoSuchElementException();
    }

    e.previous.next = e.next;
    e.next.previous = e.previous;
    size--;
    modCount++;
    return e.element;
  }

  private LinkList LinkList(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    LinkList e = header;
    if (index < (size >> 1)) {
      for (int i = 0; i <= index; i++) {
        e = e.next;
      }
    }
    else {
      for (int i = size; i > index; i--) {
        e = e.previous;
      }
    }
    return e;
  }

  public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
      for (LinkList e = header.next; e != header; e = e.next) {
        if (e.element == null) {
          return index;
        }
        index++;
      }
    }
    else {
      for (LinkList e = header.next; e != header; e = e.next) {
        if (o.equals(e.element)) {
          return index;
        }
        index++;
      }
    }
    return -1;
  }

  public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
      for (LinkList e = header.previous; e != header; e = e.previous) {
        index--;
        if (e.element == null) {
          return index;
        }
      }
    }
    else {
      for (LinkList e = header.previous; e != header; e = e.previous) {
        index--;
        if (o.equals(e.element)) {
          return index;
        }
      }
    }
    return -1;
  }

  private static class LinkList {
    Object element;

    LinkList next;

    LinkList previous;

    LinkList(Object element, LinkList next, LinkList previous) {
      this.element = element;
      this.next = next;
      this.previous = previous;
    }
  }

  public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (LinkList e = header.next; e != header; e = e.next) {
      result[i++] = e.element;
    }
    return result;
  }
}