List 개념 및 예제#1

List 인터페이스는 컬렉션 프레임워크의 한 종류로 배열이라고 생각하면 간단하다. 주로 순서가 있는 자료 관리에 유용하게 사용되고 중복을 허용한다. 크게 arrayList, LinkedList, Vector로 구분되고 Stack과 Queue도 List 인터페이스에 속한다.

ArrayList : 객체 배열 클래스, List<Integer> = new ArrayList<Integer>();와 같은 문법으로 주로 사용

 

Vector : 멀티 스레드에서 주로 사용하고, 동기화를 제공한다. 동기화 구현시 작업이 이루어지는 자원에 대해 잠금

을 수행하므로 ArrayList보다 수행속도가 느리다.

 

LinkedList : ArrayList보다 중간에 자료를 추가, 제거하는데 시간이 적게 걸린다. LinkedList는 자료의 추가, 제거

시 각 요소가 가리키는 주소값만 변경해 주면되어서 자료의 이동이 배열보다 적다는 장점이 있다.

-> 자료의 변동이 많은 경우 : LinkedList, 자료 변동이 거의 없는 경우 : ArrayList를 사용하자.

​

ArrayList를 사용한 문제를 보자.

​

#1.

백준 1158 요세푸스 문제이다. 문제를 처음 보면 이해조차 잘 가지 않는다. 천천히 문제를 쓰면서 풀어보니

N = 7, K = 3일 때 1~7까지의 숫자 중 3번째 숫자가 뽑아지고, 앞의 두 숫자는 맨 뒤로 적힌다는 것을 알 수 있었다. 선입선출의 개념을 생각하고 Queue를 사용하기로 했다.

​

poll() : Queue의 맨 앞 숫자를 추출하고 리스트에서 해당 값을 제거

add() : List에 추가

isEmpty() : 해당 리스트가 비었다는 것을 뜻함

​

해당 메소드들을 사용하여, n개수만큼 i를 add해준 Queue에서 리스트가 빌 때까지 빼고 다른 리스트에 담아주는 방식으로 k번째 값을 계속 뽑아주었다.

​