[Java] Collection 과 List

Collection

　　배열을 이용하게 되면 고정크기이기 때문에 비효율적으로 사용할 수 밖에 없었다. 유동 크기의 데이터를 효율적으

　　로 관리하기 위해 Collection 프레임워크를 사용할 수 있다. 

List

　　중복을 허용하고 저장 순서가 유지되는 인터페이스다. 

ArrayList

　　List 인터페이스를 구현하기 때문에 중복을 허용하고 저장 순서가 유지되는 자료구조이다. 배열이 동적으로 늘어

　　나는 것이 아니고 배열이 꽉 차게 되면 더 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열

　　로 복사한다. 

LinkedList

　　LinkedList역시 List 인터페이스를 구현하기 때문에 중복을 허용하고 저장 순서가 유지되는 자료구조이다.

　　하나의 노드는 다음 노드의 주소를 가지고 있어서 요소들이 연속적으로 저장되어있지 않다.

ArrayList 와 LinkedList 시간 복잡도 비교

 

ArrayList와 LinkedList 비교

• 데이터의 위치를 알 때 조회/수정의 시간복잡도 : ArrayList의 데이터 접근 시간복잡도는 위치만 알면 한번에 찾기 때문에 O(1) 이다. LinkedList 는 데이터가 연속적으로 저장되어있지 않기 때문에 모든 노드에 접근해야하기 때문에 시간복잡도는 O(n) 이다. 
• 데이터를 중간 위치에 추가할 경우 : ArrayList는 데이터를 추가할 경우 추가한 뒤 뒤의 데이터를 한칸씩 뒤로 보내야하기 때문에 O(n)의 시간복잡도가 든다. LinkedList는 추가할 위치를 찾아야 하기 때문에 순회를하게 된다. 그렇기 때문에 시간 복잡도는 O(n)이다. 
• 데이터를 삭제할 경우 : ArrayList는 데이터를 삭제할 경우 해당 위치이후부터 한칸씩 복사해와야하기 때문에 O(n) 시간이 걸린다. LinkedList는 데이터를 삭제할 경우 삭제 노드의 위치까지 조회해야하기 때문에 O(n) 시간이 걸린다.

연산	ArrayList	LinkedList
조회 / 수정	O(1)	O(N)
데이터 추가 (중간)	O(N)	O(N)
데이터 추가 (맨앞)	O(N)	O(1)
데이터 추가 (맨뒤)	O(1)	O(1)
데이터 삭제 (중간)	O(N)	O(N)
데이터 삭제 (맨앞)	O(N)	O(1)
데이터 삭제 (맨뒤)	O(1)	O(1)

　　데이터의 개수가 변하지 않는 경우는 ArrayList를 데이터의 갯수가 자주 변하는 경우에는 LinkedList를 사용하는

　　것이 더 좋은 선택이다.