List Collection
List 컬렉션은 객체를 일렬로 늘어놓은 구조이다. 객체를 인덱스로 관리하며, 객체 자체를 저장하는 것이 아니라 객체의 주소(번지)를 참조한다.
동일한 객체를 저장할 경우 동일한 주소가 참조되며, null을 저장할 경우 해당 인덱스는 객체를 참조하지 않는다.
List Collection의 구현 클래스 : ArrayList, Vector, LinkedList
<List 컬렉션이 공통적으로 사용할 수 있는 List인터페이스의 메소드>
E : 타입 파라미터로 List 인터페이스가 제네릭 타입이기 때문에 구체적 타입이 구현 객체 생성시 결정됨
1) 객체 추가
- boolean add(E e) : 객체를 맨 마지막에 추가
- void add(int index, E element) : 해당 인덱스에 객체 추가
- set(int index, E element) : 해당 인덱스에 저장된 객체를 파라미터로 주어진 객체로 변경
2) 객체 검색
- boolean contains(Object o) : 해당 객체가 저장되어있는지 확인
- E get(int index) : 해당 인덱스에 저장되어있는 객체 리턴
- isEmpty() : 컬렉션이 비어있는지 검사
- int size() : 저장된 모든 객체의 수를 리턴
3) 객체 삭제
- void clear() : 저장된 모든 객체 삭제
- E remove(int index) : 해당 인덱스에 저장된 객체 삭제
- boolean remove(Object o) : 주어진 객체를 삭제
ArrayList
1) 일반 배열과의 차이점
: ArrayList는 배열과 달리 저장 용량을 초과한 객체가 들어오면 자동적으로 저장 용량이 늘어난다.
2) 생성 방법
//Integer객체로 ArrayList생성. 기본 생성자로 생성할 경우 초기 용량(capacity)은 10이다.
ArrayList<Integer> arrayList = new ArrayList<Integer>();
//생성시 용량을 정할 수 있다
ArrayList<String> arrayList = new ArrayList<String>(30);
//2차원 ArrayList 생성
ArrayList<ArrayList<Integer>> arrayList = new ArrayList<ArrayList<Integer>>();3) 사용 예시
DFS 탐색의 일부코드를 통해 2차원 ArrayList활용 방법을 살펴보자
public class ALExample {
static int[] visited; //visited[i] 가 0이면 i는 방문하지 않은 정점임을 의미. (1:방문)
static ArrayList<ArrayList<Integer>> graph; //2차원 ArrayList 선언
/**
* v의 인접 정점들에 대하여 DFS탐색
* @param v DFS 방문 정점 번호
*/
public static void dfs_func(int v) {
visited[v] = 1;
//정점 v의 인접정점들에 대해 방문하지 않은 인접정점 DFS 탐색
for(int i=0; i<graph.get(v).size(); i++) {
if(visited[(graph.get(v).get(i))] == 0) { //2차원 ArrayList정보를 읽어와서 방문 여부 확인
int nextN = graph.get(v).get(i);
dfs_func(nextN);
}
}
}
public static void main(String[] args) {
...
//초기화
visited = new int[1010];
graph = new ArrayList<ArrayList<Integer>>(1010); //1010개의 ArrayList만들기
for(int i=0; i<1010; i++) { //2차원 ArrayList 만들기
graph.add(new ArraList<Integer>());
}
//그래프 정보 입력받기
for(int i=0; i<M; i++) { //M : 간선수
u = scanner.nextInt(); v = scanner.nextInt();
//무방향 그래프
graph.get(u).add(v); //C의 2차원 배열로 간단하게 생각해보자면 graph[u][끝인덱스] = v; 라 보면된다.
graph.get(v).add(u);
}
dfs_func(V);
}
}Vector
1) ArrayList와 차이점
: Vector는 synchronized(동기화된) 메소드로 구성되어있기 때문에 멀티스레드가 동시에 해당 메소드를 실행할 수 없어서 멀티스레드 환경에서 안전히 객체를 추가/삭제 할 수 있다. -> Thread Safe하다 라고 말함
따라서 멀티 스레드 환경이 아니라면 동기화되지 않은 ArrayList를 사용하는것이 빠르다.
2) 생성 방법
//Vector<E> vector = new Vector<E>();
Vector<Integer> v = new Vector<Integer>();LinkedList
자료구조의 Linked list 개념을 그대로 따른다. C에서 연결 리스트를 구현할 때 포인터로 노드를 연결하는 것을 생각하면된다.
ArrayList에서 중간에 위치한 객체를 삭제할 경우 해당 인덱스를 기점으로 이후 모든 객체들을 하나씩 앞으로 이동시켜야 하지만, LinkedList는 삭제할 객체의 앞/뒤 객체의 링크만 변경하면 된다. (삽입도 이와 동일한 개념)
1) 생성 방법
//LinkedList<E> list = new LinkedList<E>();
LinkedList<Integer> list = new LinkedList<Integer>();정리
1) 주로 실행하는 것이 검색 연산이며, 객체 삽입이 인덱스 맨 마지막에 이뤄질 경우(순차적으로 추가/삭제할 경우)
- plus) 싱글스레드 환경에서 빠르게 연산하고 싶을 경우 : ArrayList
- plus) 멀티스레드 환경에서 Thread safe하게 메소드를 실행해야 할 경우 : Vector
2) 빈번한 객체 삭제와 삽입이 일어날 경우 : LinkedList
