List

■List 인터페이스

- 순서가 있고 중복을 허용.

- 구현 클래스 : ArrayList, Vector, LinkedList

■ArrayList 클래스

- 내부 구현 : Object[] elementData;

- 배열과 다르게 크기가 유동적이라는 것이 특징.

- 내부 배열을 새로운 크기의 배열로 대체해 가며 유동적으로 관리.

- ArrayList.add 과정

1. Object[index] = element;

2. 인덱스가 가득 찼을 경우, Arrays.copyOf메소드를 통해 

Object[oldCapacity + (oldCapacity >> 1)]를 새로 생성해 복사함.

- ArrayList.remove

1. System.arraycopy(elementData, index+1, elementData, index,numMoved);

2. elementData[--size] = null;

3. 맨 처음 인덱스를 삭제할 경우 (맨 처음+1 ~ 맨 마지막) 데이터들을 왼쪽으로 

한칸씩 전부 옮기고 맨 마지막 인덱스를 null로 채운다.

- 이처럼 추가/삭제 로직에 약간의 복잡함이 있고 배열 전체를 새로 생성하는 등의 

과정이 있기 때문에 LinkedList보다 추가/삭제 성능이 후짐. 

따라서 추가/삭제가 빈번하게 일어나는 경우에는 ArrayList를 초기화 할 때, 

크기를 크게 지정하는것이 좋음

- 하지만 배열이라는 연속적인 구조로 저장하기 때문에 인덱스에 대한 순차, 무작위 

접근이 가능하고 검색속도가 LinkedList보다 빠르다.

- 동기화를 지원하지 않기 때문에 때에 따라 

명시적 동기화(Collections.synchronizedSet)가 필요하다. (Not Thread Safe)

■Vector 클래스

- 내부 구현 : Object[] elementData;

- Java 1에서 선보인 자료구조 클래스로, 기능과 구현이 ArrayList와 동일.

- 동기화를 지원. 따라서 ArrayList보다 성능이 후짐

- ArrayList를 쓰지 Vector를 쓸 일은 거의 없다고 한다.

■LinkedList 클래스

- 내부 구현 : Node 클래스 생성하여 사용

- 데이터를 체인으로 묶어놓은 리스트. 따릉이가 연결 거치된 모습과 비슷

- 다만 한방향 체인으로 묶인 따릉이와는 다르게 LinkedList는 양방향 체인으로 묶여있다.

- LinkedList.add 과정

Node<E> newNode = new Node<>(lastNode, newData, null);

- LinkedList.remove 과정

prevNode.next = nextNode; nextNode.prev = prevNode;

- 순차 접근 가능, 무작위(인덱스) 접근 불가능

- ArrayList에 비해 삽입,삭제가 빠름. 왜냐하면 ArrayList처럼 인덱스 관리를 할 필요 없이 

new Node를 알맞은 위치에 끼워주기만 하면 되기 때문.

- 하지만 메모리에 산재된 데이터들을 불연속적인 구조로 저장하기 때문에 검색속도 느림

- 다시말해 특정 위치의 데이터를 검색하고 싶으면 매번 처음부터 특정 위치까지 쭉 

읽어야 함.

- 그리고 데이터들을 체인할 때, 포인터를 사용하기 때문에 작은 자료형(primitive type)을 

데이터로 사용할 경우 메모리 낭비가 심할 수 있음

- 동기화를 지원하지 않기 때문에 때에 따라 

명시적 동기화(Collections.synchronizedSet)가 필요하다. (Not Thread Safe)