자료구조 정리(작성중)

자료구조란?

- 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리 저장을 의미한다. 더 정확히 말해, 자료구조는 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 말한다. 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

 

배열(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은 추가 예정