자바 컬렉션 프레임워크

배열이 있고 링크드 리스트 스택 큐 스리 해싱 등이 자료구조의 기본

 

Array - 배열

선형 자료구조의 대표적인 자료구조 중 하나. 일열로 되어있음

논리적인 구조와 물리적인 구조, 위치가 동일하다!

생성을 할 때 몇개짜리라고 확실히하고 들어간다.

고정된 길이를 가지고 들어가기 때문에 인덱스연산을 굉장히 빠르게 할 수 있다.

단점은 배열은 중간에 빌 수가 없다. 배열은 배열의 길이에 종속되어있다. 연산이 길이에 따라 속도?가 다르기 때문에 종속이 되어있다고 말하는 것이다. 그래서 삽입 삭제를 할 경우 길이에 따라 시간이 걸리게 된다. O(n)

요소가 자꾸 변화한다 할때 배열을 쓰는것은 좋지 않다. 만약 더 늘리고 싶다면 다른 배열을 만든담에 옮기는? 복사하는 방법을 사용한다.

자바에 보면 ArrayList가 있는데 얘가 배열을 구현해놓은것이다. 그 전에 vector가 있었는데 지금은 많이 쓰이지 않는다. 차이가 뭐냐면 알고리즘은 ArrayList가 더 최적화 되어있고 벡터는 동기화를 지원한다. 동기화를 지원한다라는 것이 무엇이냐면 두개의 쓰레드가 접근했을 때 순서를 정해서 처리를 한다. 그래서 매번 동시에 접근하는 리소스에 락을 걸어야한다. 그래서 오버헤드가 존재한다. 여튼 결론적으로 ArrayList를 사용하면된다.

ArrayList -> 객체 배열을 구현해 놓은 자료구조

jdk에서 ArrayList와 vector를 구현해 놓은것을 알수있다.

 

Linked List

배열의 단점을 보완한 자료구조로 데이터와 링크로 구성이 되어있다.

배열과 비교를 해보자면 배열같은 경우에는 삽입 삭제하면 요소들이 이동 n-1만큼 이동을 했어야하는데 얘같은 경우는 노드에서 가리키는 것을 끊고 다른 노드를 가리키면 되니까 삽입삭제에 들어가는 비용이 훨씬 더 적다.

십만개의 요소를 두고 맨앞에 있는 놈을 삽입 삭제하는 실험을 했었는데 얼마나 시간이 소요되나 시렇ㅁ을 했는데 얘가 더 빠르다는 것이 결론이 나왔따.

요소가 많이 변한다. 데이터의 개수가 유동적이다 -> LinkedList 사용

데이터의 변화가 없다. 처음부터 데이터 개수가 정해져 있다 -> Array사용

jdk에서는 LinkedList가 구현되어있다.

 

Stcak & Queue

일반적으로 스택과 큐는 뭘로 구현하더라도 상관이 없다. 무슨소리냐면 배열로 할수도 있고 링크드리스트로도 구현할 수 있다. 두개의 자료구조의 특징은 삽입 삭제가 중간에서 일어나지 않는다는 점이다.