ArrayList vs LinkedList

	ArrayList	LinkedList
장점	- 빠른 탐색 시간 (->index)	- 삽입과 삭제 용이  - 적은 메모리 사용
단점	- 가비지 (메모리)	- 느린 탐색 시간

---

ArrayList

public class ArrayList<E> {

	private static final int DEFAULT_CAPACITY = 10;
	Object[] elementData;
	private int size;

	/* 생성자  */
	public ArrayList() {
		this.elementData = new Object[DEFAULT_CAPACITY];
	}

	public ArrayList(int initialCapacity) {
		if(initialCapacity < DEFAULT_CAPACITY) {
			this.elementData = new Object[DEFAULT_CAPACITY];
		} else {
			this.elementData = new Object[initialCapacity];
		}
	}

	public void add(E e) {
		if(this.size == this.elementData.length) {
			int oldSize = this.elementData.length;
			int newSize = oldSize + (oldSize >> 1);
			this.elementData = Arrays.copyOf(this.elementData, newSize);
		}
		this.elementData[this.size++] = e;
	}

	public void add(int index, E value) {
		if (index < 0 || index >= this.size)
			return;

		if (this.size == this.elementData.length) {
			this.elementData = Arrays.copyOf(this.elementData, newCapacity());
		}

		for (int i = size - 1; i >= index; i--)
			this.elementData[i + 1] = this.elementData[i];

		this.elementData[index] = value;
		this.size++;
	}

	@SuppressWarnings("unchecked")
	public E get(int index) {
		if (index < 0 || index >= this.size) {
			//System.out.println("유효한 인덱스가 아닙니다.");
			return null;
		}
		return (E)this.elementData[index];
	}

	@SuppressWarnings("unchecked")
	public E set(int index, E e) {
		E old = (E)this.elementData[index];
		if (index < 0 || index >= this.size) {
			return null;
		}
		this.elementData[index] = e;
		return old;
	}

	@SuppressWarnings("unchecked")
	public E remove(int index) {
		E old = (E)this.elementData[index];
		if (index < 0 || index >= this.size) {
			return null;
		}
		System.arraycopy(this.elementData, index + 1, this.elementData, index, this.size - (index + 1));
		this.size--;
		return old;
	}

	public int size() {
		return this.size;
	}

	@SuppressWarnings("unchecked")
	public E[] toArray() {
		return (E[])Arrays.copyOf(this.elementData, this.size);
	}

	@SuppressWarnings("unchecked")
	public E[] toArray(E[] arr) {
		if(arr.length < this.size) {
			// 파라미터로 받은 배열이 작을 때, 새 배열을 만들어 리턴
			return (E[]) Arrays.copyOf(this.elementData, this.size, arr.getClass());
		}
		// 넉넉할 때 파라미터로 받은 배열 그대로 리턴
		System.arraycopy(this.elementData, 0, arr, 0, size);
		return arr;
	}

	private Object[] grow() {
		return this.elementData = Arrays.copyOf(this.elementData, 
				newCapacity());
	}

	private int newCapacity() {
		int oldSize = this.elementData.length;
		return oldSize + (oldSize >> 1);
	}
}

	public void add(E e) {
		if(this.size == this.elementData.length) {
			int oldSize = this.elementData.length;
			int newSize = oldSize + (oldSize >> 1);
			this.elementData = Arrays.copyOf(this.elementData, newSize);
		}
		this.elementData[this.size++] = e;
	}

	public void add(int index, E value) {
		if (index < 0 || index >= this.size)
			return;

		if (this.size == this.elementData.length) {
			this.elementData = Arrays.copyOf(this.elementData, newCapacity());
		}

		for (int i = size - 1; i >= index; i--)
			this.elementData[i + 1] = this.elementData[i];

		this.elementData[index] = value;
		this.size++;
	}

 

	public E remove(int index) {
		E old = (E)this.elementData[index];
		if (index < 0 || index >= this.size) {
			return null;
		}
		System.arraycopy(this.elementData, index + 1, this.elementData, index, this.size - (index + 1));
		this.size--;
		return old;
	}

---

LinkedList 

public class LinkedList<E> {
	
	Node<E> first;
	Node<E> last;
	int size;
	
	static class Node<T> {
		T value;
		Node<T> next; 
	}
	
	public void add(E value) {
		Node<E> newNode = new Node<>();
		newNode.value = value;
		if(this.size == 0) {
			first = last = newNode;
		} else {
			last.next =  newNode;
			last = newNode;
		}
		this.size++;
	}
	
	public void add(int index, E value) {
		if (index < 0 || index >= this.size) {
			return;
		}
		
		Node<E> newNode = new Node<>();
		newNode.value = value;
		
		Node<E> cursor = first;
		for(int i = 0 ; i < index - 1 ; i++) {
			cursor = cursor.next;
		}
		
		if (index == 0) {
			newNode.next = first;
			first = newNode;
		} else {
			newNode.next = cursor.next;
			cursor.next = newNode;
		}
		this.size++;
	}
	
	public E get(int index) {
		if (index < 0 || index >= this.size) {
			return null;
		}
		Node<E> cursor = first;
		for(int i = 0 ; i < index-1 ; i++) {
			cursor = cursor.next;
		}
		return cursor.value;
	}
	
	public E remove(int index) {
		if (index < 0 || index >= this.size) {
			return null;
		}
		Node<E> cursor = first;
		for(int i = 0 ; i < index - 1 ; i++) {
			cursor = cursor.next;
		}
		Node<E> deletedNode = null;
		if(index == 0) {
			deletedNode = first;
			first = deletedNode.next;
		} else {
			deletedNode = cursor.next;
			cursor.next = deletedNode.next;
		}
		deletedNode.next = null;
		this.size--;
		return deletedNode.value;
	}
	
	public E set(int index, E value) {
		if (index < 0 || index >= this.size) {
			return null;
		}
		Node<E> cursor = first;
		for(int i = 0 ; i < index ; i++) {
			cursor = cursor.next;
		}
		E oldValue = cursor.value;
		cursor.value = value;
		return oldValue;
	}
	
	public Object[] toArray() {
		Object[] arr = new Object[size];
		Node<E> cursor = first;
		for(int i = 0 ; i < this.size ; i++) {
			arr[i] = cursor.value;
			cursor = cursor.next;
		}
		return arr;
	}
	
	@SuppressWarnings("unchecked")
	public E[] toArray(E[] arr) {
		if (arr.length < size) {
			arr = (E[]) Array.newInstance(arr.getClass().getComponentType(), size);
		}
		Node<E> cursor = first;
		for(int i = 0 ; i < this.size ; i++) {
			arr[i] = cursor.value;
			cursor = cursor.next;
		}
		return arr;
	}
	
	public int getSize() {
		return this.size;
	}

}

 

	public void add(E value) {
		Node<E> newNode = new Node<>();
		newNode.value = value;
		if(this.size == 0) {
			first = last = newNode;
		} else {
			last.next =  newNode;
			last = newNode;
		}
		this.size++;
	}
	
	public void add(int index, E value) {
		if (index < 0 || index >= this.size) {
			return;
		}
		
		Node<E> newNode = new Node<>();
		newNode.value = value;
		
		Node<E> cursor = first;
		for(int i = 0 ; i < this.index - 1 ; i++) {
			cursor = cursor.next;
		}
		
		if (index == 0) {
			newNode.next = first;
			first = newNode;
		} else {
			newNode.next = cursor.next;
			cursor.next = newNode;
		}
		this.size++;
	}
	

	public E remove(int index) {
		if (index < 0 || index >= this.size) {
			return null;
		}
		Node<E> cursor = first;
		for(int i = 0 ; i < index - 1 ; i++) {
			cursor = cursor.next;
		}
		Node<E> deletedNode = null;
		if(index == 0) {
			deletedNode = first;
			first = deletedNode.next;
		} else {
			deletedNode = cursor.next;
			cursor.next = deletedNode.next;
		}
		deletedNode.next = null;
		this.size--;
		return deletedNode.value;
	}