[APS] 01 : 자료구조 개론

자료구조

---

자료구조

자료구조(data structure) : 효율적인 관리를 위해 특성이나 상호 관계 등에 따라 구조화시킨 데이터, 혹은 그의 집합체

대부분의 프로그래밍 언어는 자료형(data type) 을 통해 자료구조를 정의

• 원시 자료형
  • 자료를 특성에 따라 효율적으로 메모리에 저장하기 위해 분류한 기준
  • 프로그래밍 언어 차원에서 지원되는 기본적이고 독립적인 자료구조 
• 추상 자료형(ADT : Abstract Data Type)
  • 다수의 원시 자료형들을 효율적으로 관리하기 위해 정의된 자료구조
  • 구성하는 원시 자료형과 필요한 연산 등을 수학적/논리적으로 정의해놓은 집합체

※ 자료구조가 논리적으로 정의 및 설계된 용어라면, 자료형은 각 프로그래밍 언어에서 정의된 실제적 형식이다. 예를 들어 Java 는 인터페이스(혹은 추상클래스)를 통해 특정 자료구조에 대응되는 자료형을 정의하고, 구체적인 대입을 통해 실체화된 자료구조인 클래스(객체) 를 만든다. 다만 두 단어는 혼용되는 경우가 많다.

---

자료구조의 분류

데이터 간 관계에 따라 단순 구조, 선형 구조, 비선형 구조, 파일 구조 와 그 외로 분류

출처 : 네이버 지식백과

1. 단순구조: 각 구조를 이루는 기본이 되며, 독립적이고 추가적인 관계를 갖지 않는 자료구조 ≒ 원시 자료형
2. 선형(linear)구조 : 원소간의 관계가 선형적이며, 1:1 배치됨 : 배열, 리스트, 스택, 큐, 덱 등...
3. 비선형(non-linear)구조 : 원소간의 관계가 비선형적으로 배치됨 : 트리, 그래프 등...
4. 파일구조 : 파일의 데이터 저장방식에 대한 자료구조
5. 그 외 :딕셔너리, 집합, 구조체, 클래스 등 ...

※ 자료구조는 정의에 따라 수없이 많고, 분류에 대한 관점도 다양하며, 프로그래밍 언어마다 관점이나 구현방식이 상이하여 위의 분류법에 명확히 합치하지 않는 경우도 있다. 따라서 이러한 분류법이 있다는 정도만 염두에 두고, 자료구조의 분류에 너무 얽매이지 않도록 하자.

---

자료구조 별 복잡도

 

공간 복잡도는 기본적으로 자료의 갯수(N)과 비례하지만, 일부 자료구조는 그 이상(overhead)을 필요로 하기도 함

---

Java 자료구조

---

컬렉션 프레임워크

Java는 가장 기본적인 자료구조인 배열을 제외한 자료구조들을 통틀어 컬렉션 프레임워크(Collection Framework)로 칭함

Iterable 을 상속했기 때문에 반복(Iteration)이 가능함 : for-each 구문 사용 가능

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (String s : list) {
	System.out.println(s);
}

 

컬렉션

컬렉션(Collection) Java의 리스트, 큐, 셋의 최상위 인터페이스

 

공통 메서드

메서드	설명
boolean add(E e)	요소 추가
boolean remove(Object o)	특정 요소 삭제
boolean contains(Object o)	특정 요소 포함 여부
int size()	컬렉션의 크기 반환
boolean isEmpty()	컬렉션이 비어있는지 확인
void clear()	모든 요소 삭제
Object[] toArray()	컬렉션을 배열로 변환
<T> T[] toArray(T[] a)	특정 타입의 배열로 변환
Iterator<E> iterator()	순회할 Iterator 객체 반환
boolean containsAll(Collection<?> c)	다른 컬렉션의 모든 요소가 포함되어 있는지 확인
boolean addAll(Collection<? extends E> c)	다른 컬렉션의 모든 요소 추가
boolean removeAll(Collection<?> c)	특정 컬렉션에 포함된 모든 요소 삭제
boolean retainAll(Collection<?> c)	특정 컬렉션에 포함된 요소만 유지

 

자세한 이야기는, 각 글에서 설명

---

- 최종 수정일 : 25-03-20

- 이 글은 지속적으로 수정되고 있으며, 오타나 잘못된 정보에 대한 사항은 댓글로 남겨주시면 감사하겠습니다.