JAVA

• 자바 자료구조 구현하기 위해서는 Generic, InnerClass 에 대한 이해가 필요

LinkedList

• Java Generic 에 대한 이해
• 자바는 연산자 오버로딩이 안되므로 Iterator 구현

public class LinkedList<E> implements List<E>{
  transient int size = 0;

  transient Node<E> first;
  transient Node<E> last;

  public LinkedList() {
  }
  public E get(int index) {
      return node(index).item;
  }
  //@TODO BASE로
  public ListIterator<E> listIterator() {
      return listIterator(0);
  }
  public ListIterator<E> listIterator(int index) {
      return new ListItr(index);
  }
  public int size(){
    return size;
  }
  public boolean isEmpty(){
    return size == 0;
  }
  public boolean add(E e){
    linkLast(e);
    return true;
  }
  public boolean remove(Object o){
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
  }
  private void linkFirst(E e) {
      final Node<E> f = first;
      final Node<E> newNode = new Node<>(null, e, f);
      first = newNode;
      if (f == null)
          last = newNode;
      else
          f.prev = newNode;
      size++;
  }
  void linkLast(E e){
      final Node<E> l = last;
      final Node<E> newNode = new Node<>(l, e, null);
      last = newNode;
      if (l == null)
          first = newNode;
      else
          l.next = newNode;
      size++;
  }
  E unlink(Node<E> x) {
      // assert x != null;
      final E element = x.item;
      final Node<E> next = x.next;
      final Node<E> prev = x.prev;

      if (prev == null) {
          first = next;
      } else {
          prev.next = next;
          x.prev = null;
      }

      if (next == null) {
          last = prev;
      } else {
          next.prev = prev;
          x.next = null;
      }

      x.item = null;
      size--;
      return element;
  }

  Node<E> node(int index) {
      if (index < (size >> 1)) {
          Node<E> x = first;
          for (int i = 0; i < index; i++)
              x = x.next;
          return x;
      } else {
          Node<E> x = last;
          for (int i = size - 1; i > index; i--)
              x = x.prev;
          return x;
      }
  }

  //@TODO BASE로 변경
  public Iterator<E> iterator() {
      return new ListItr(0);
  }
  // 외부에서는 접근 불가능한 InnerClass
  // static Inner class 안에는 static variable 선언 가능함
  private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next){
      this.prev = prev;
      this.item = element;
      this.next = next;
    }
  }

  private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null;
    private Node<E> next;
    private int nextIndex;
    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
    public boolean hasNext() {
        return nextIndex < size;
    }
    public E next() {
        if (!hasNext())
        {

        }
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    public void remove() {
        if (lastReturned == null)
        {

        }

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
    }
  }
}

public interface List<E> extends Collection<E> {
  int size();
  boolean isEmpty();
  boolean add(E e);
  boolean remove(Object o);

  Iterator<E> iterator();
}

ArrayList

• Array 를 이용한 구현
• 크기 부족할때 2배로 늘리는게 중요함! amortized O(1) 을 이해하자

public class ArrayList<E> implements List<E>{

  private static final int DEFAULT_CAPACITY = 10;

  private static final Object[] EMPTY_ELEMENTDATA = {};

  private transient Object[] elementData;
  private int size;

  public ArrayList(int initialCapacity){
    super();
    this.elementData = new Object[initialCapacity];
  }
  public ArrayList(){
    super();
    this.elementData = EMPTY_ELEMENTDATA;
  }
  public void ensureCapacity(int minCapacity) {
      int minExpand = (elementData != EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

      if (minCapacity > minExpand) {
          ensureExplicitCapacity(minCapacity);
      }
  }
  private void ensureCapacityInternal(int minCapacity) {
      if (elementData == EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
  }
  private void ensureExplicitCapacity(int minCapacity) {
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }
  // 최대 array 크기
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  private void grow(int minCapacity){
    int oldCapacity = elementData.length;
    // 얼레 크기에 2배를 늘려줌
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if(newCapacity-minCapacity < 0){
      newCapacity = minCapacity;
    }
    // 최대 ARRAY 크기를 넘음
    if(newCapacity-MAX_ARRAY_SIZE > 0){
      newCapacity = MAX_ARRAY_SIZE;
    }
    // 크기를 늘려서 Array copy
    // 그냥 java.util 에 Arrays 클래스 사용
    elementData = java.util.Arrays.copyOf(elementData,newCapacity);
  }
  public int size(){
    return size;
  }
  public boolean isEmpty(){
    return size == 0;
  }
  @SuppressWarnings("unchecked")
  E elementData(int index) {
      return (E) elementData[index];
  }
  public E get(int index) {
      return elementData(index);
  }
  public boolean add(E e){
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
  }
  public E remove(int index) {
      E oldValue = elementData(index);

      int numMoved = size - index - 1;
      if (numMoved > 0)
          System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
      elementData[--size] = null; // clear to let GC do its work

      return oldValue;
  }
  public boolean remove(Object o){
    if (o == null){
      for(int i=0; i < size; i++){
        if(elementData[i] == null){
          fastRemove(i);
          return true;
        }
      }
    }else{
      for(int i=0; i < size; i++){
        // LinkedList 에서는 hashCode비교(==) 하지만
        // ArrayList 에서는 내용이 같은지(equals) 를 한다.
        if(o.equals(elementData[i])){
          fastRemove(i);
          return true;
        }
      }
    }
    return false;
  }
  private void fastRemove(int index) {
      int numMoved = size - index - 1;

      if (numMoved > 0){
        // 원본,읽어올부분,복사할대상,카피할 위치,얼마만큼 읽어올지
        // elementData를 index+1 부터 numMoved 만큼 읽어서 index 로 elementData 에 카피
        System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
      elementData[--size] = null; // clear to let GC do its work
    }
  }
  public Iterator<E> iterator(){
    return new ListItr(0);
  }

  private class ListItr implements ListIterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    public ListItr(int index){
      cursor = index;
    }
    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        int i = cursor;
        if (i >= size)
        {

        }
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
        {

        }
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
        {

        }

        ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
    }
  }
}

Reference

• 전체구현