자료구조 정리(작성중)
자료구조란?
- 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리 저장을 의미한다. 더 정확히 말해, 자료구조는 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 말한다. 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.
배열(Array)
자료구조의 가장 기본이다. 데이터를 순차적으로 저장해 0번 인덱스부터 인덱스를 통해 접근할 수 있다.
- 데이터를 순차적으로만 접근할 수 있어 위치를 모르는 경우 효율이 떨어짐.
- 배열을 선언할 때 지정된 크기로 크기가 고정됨.
- 배열에 들어갈 수 있는 데이터는 선언된 자료형으로 고정됨.
보통 크기가 고정되어 있거나 데이터 위치의 변경이 필요하지 않은 경우 사용한다.
ArrayList
배열과 유사하지만 배열의 부족한 효율성을 보안하여 구현한 자료구조이다. 데이터 접근을 인덱스를 이용하는 건 같지만 배열의 문제점을 해결함.
- 데이터의 양의 따라 크기를 동적으로 크기를 조절함.
- 데이터들의 타입은 다를 수 있음.(제네릭 설정 시 제한 가능)
- 리스트 중간에 값의 추가나 삭제가 간편함.
단점으로는 배열 중간에 값 추가/삭제를 간편하게 할 수 있지만 시간 복잡도는 O(n) 임.
ArrayList
ArrayList와 같이 Array의 불편함을 보안하여 사용 가능한 자료구조로 ArrayList와는 다르게 배열이 아닌 Node를 이용하여 List를 관리함. 자바에서는 Double Linked로 구현되어 있으며 처음 노드와 끝 노드가 바로 연결되어 있지는 않다.
- 배열이 아닌 노드로 List를 관리하여 앞 뒤 노드와 연결되어 있는 방식
- 노드의 중간에서 자료의 추가/삭제가 O(1)의 시간에 가능하다는 장점을 갖지만 데이터를 검색하는 건 O(n)의 시간이 걸림
Vector
JDK 1.0에 추가된 자료구조로 ArrayList와 동일한 구조를 가지고 배열의 크기를 동적으로 관리 가능하다.
- ArrayList와 다르게 멀티 스레드 환경에서 Thread-safe 하여 안정성은 높지만 속도가 느림.
ArrayList의 비해 속도가 느려 보통 ArrayList를 권장함.
Stack
Vector를 상속받은 자료구조로 LIFO구조(Last in First Out) 선입후출 구조를 갖는다. 데이터를 쌓는 형식으로 저장하는데 따라서 조회, 추가, 삭제 모두 가장 위에 있는 즉 가장 최근 값에서 이루어진다.
Queue
Queue는 인터페이스로 PriorityQueue, LinkedList, ArrayDeque와 함께 사용 가능하다. Stack 과는 다르게 FIFO(First In First Out) 구조로 선입선출의 구조를 갖고 있다.
Set,Map은 추가 예정