(Collection) List

1. Arraylist

배열 + 리스트. 배열의 크기가 가변적이고 인덱스를 사용한다. (get()메서드 이용)

가변적이지만 배열의 확장과 같은 방식으로 배열의 길이를 늘린다. (복사->이동)

그래서 배열의 길이를 늘리는데 드는 시간은 배열과 같다.

배열의 타입은 Object[]이다. 그래서 요소들은 모두 객체다.

1-1. Array와 Arraylist의 차이

- 길이 불변 vs 가변

- List 인터페이스 메서드 사용 가능여부

1-2. ArrayList의 추가 & 삭제

중간에 값을 제거하거나 추가하면 한칸씩 밀리므로 최대 시간복잡도는 O(N)이다.

 

2. LinkedList

LinkedList는 Array와 ArrayList와 달리 데이터가 메모리에 비연속적으로 저장된다. 

LinkedList

각 요소들은 다음 자신과 연결된 요소에 대한 참조값과 데이터를 담고있다.

class Node{
    Noide next;
    Object obj;
}

이렇게 노드로 연결되어있기 때문에 값을 변경하기 용이하다.

값을 제거하고 그 위치의 앞,뒤 노드만 변경한 데이터랑 연결하면 되기 때문에 추가/삭제가 편하다.

하지만 인덱스가 없기 때문에 특정한 값을 찾는데는 오랜 시간이 소요된다. (앞에서부터 하나씩 찾아감.)

 

	Array	ArrayList	LinkedList
저장공간	고정	가변	가변
메모리 공간 연속	O	O	X
특정 값 접근 (위치o)	O(1)	O(1)	O(N)
맨 앞 추가/제거	O(N)	O(N)	O(1)
맨 뒤 추가/제거	O(1)	O(1)	O(1)
중간에 추가/제거	O(N)	O(N)	O(N)
장/단점		읽기가 빠르고 추가/삭제 느림	읽기가 느리고 추가/삭제 빠름

3. Stack과 Queue

Stack : 마지막에 저장한 값을 가장 먼저 꺼내는 구조. LIFO (Last In First Out)

Queue : 처음 저장한 값이 가장 먼저 나오는 구조. FIFO (First In First Out)

Stack은 항상 마지막 값을 꺼내므로 ArrayList로 구현하기 좋고 항상 첫번째 값을 꺼내는 Queue는 LinkedList 방식이 적합하다.

Stack은 클래스로 구현되어 있지만 Queue는 인터페이스만 있어서 구현한 클래스를 사용해야한다. (ex. LinkedList)