티스토리 뷰

Algorithm

자료구조 정리

kingsubin 2021. 1. 26. 22:55

https://searchsqlserver.techtarget.com/definition/data-structure

전체적으로 크게 나누자면 단순구조, 선형구조, 비선형 구조로 볼 수 있다.

 

단순구조는 기본형 타입의 구조를 말하며 정수, 실수, 문자, Boolean 타입이 있다.

 

기본형 타입을 제외하면 선형 데이터 구조와 비선형 데이터 구조가 있는데 어떤 점이 다를까 ?

 


선형 데이터 구조와 비선형 데이터 구조의 차이

 

Difference between Linear and Non-linear Data Structures

 

선형 데이터 구조

- 데이터 요소가 이전 및 다음 인접 요소에 연결되어있으며 순차적으로 또는 선형으로 배열되는 구조 

- 단일 실행을 모든 요소를 횡단할 수 있다.

- 구현하기 쉽다.

- 예로는 Array, Stack, Queue, LinkedList 가 있다.

 

비선형 데이터 구조

- 반대로 데이터 요소가 순차적으로 또는 선형으로 배열되지 않은 구조를 비선형 데이터 구조라고 한다.

- 단일 실행으로 모든 요소를 횡단할 수 없다.

- 구현하기 어렵다.

- 선형 데이터 구조에 비해 컴퓨터 메모리를 효율적으로 사용한다.

- 예로는 Graphs, Trees 가 있다.

 

 


자바에서의 자료구조

자바에서는 컬렉션 프레임워크(collection framework)란 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합이 존재한다.

즉, 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것이다.

이러한 컬렉션 프레임워크는 자바의 인터페이스(interface)를 사용하여 구현된다.

 

Collection 인터페이스와 Map 의 계층은 아래와 같다.

 

https://www.geeksforgeeks.org/collections-in-java-2/

 

 

Collection 인터페이스에 대해서 더 자세한 계층을 보자면 아래와 같다.

 

https://dzone.com/articles/java-collections

 

 

- Collection 은 배열과 같은 다른 객체를 저장하고 다루는 것을 목적으로 하는 객체이다.

- 모든 Collection 객체는 궁극적으로 java.util.Collection 인터페이스를 구현한다.

- Collection 은 기본 자료형이 아닌 참조 자료형만 저장이 가능하다. 

- 그러면 어떻게 기본 자료형을 저장할 수 있을까 ? 

- Wrapper Class 를 사용할 수 있다.

- ex) int -> Integer.. 

 


각 자료구조별 특징을 간단히 알아보자.

 

1. List

- 순서가 있다.

- 데이터 중복을 허용한다.

- 구현체로는 ArrayList, LinkedList, Vector, Stack 가 있다.

 

2. Set

- 저장 순서를 유지하지 않는다.

- 같은 요소의 중복을 허용하지 않는다.

 

3. Stack, Queue

- List 인터페이스의 Vector 클래스를 상속받아서 구현한 게 Stack 클래스

- 후입선출 (LIFO) 의 구조

 

- Queue 의 인터페이스를 상속받는 하위 인터페이스는 많은데 그중 Deque 인터페이스를 구현한 LinkedList 클래스가

  Queue 구조를 구현하는데 가장 많이 사용된다.

- 선입선출 (FIFO) 의 구조

 

4. Map

- 키와 값을 하나의 쌍으로 저장하는 (Key-Value) 저장 방식

- 저장 순서를 유지하지 않는다.

- 키는 중복을 허용하지 않지만 값은 중복을 허용한다.

- 구현체로는 HashMap, TreeMap, Hashtable 이 있다.

 


상세한 설명이나 구현은 잘 정리된 글을 보는게 더 도움이 될 것 같다. 

honbabzone.com/java/java-dataStructure-1/

velog.io/@hygoogi/자료구조-정리-8xk66rgt2h

 


※ 참조

www.geeksforgeeks.org/data-structures/

www.tcpschool.com/java/java_collectionFramework_concept

malalanayake.wordpress.com/2014/09/26/selecting-proper-data-structures-for-the-realtime-problems/

www.geeksforgeeks.org/difference-between-linear-and-non-linear-data-structures/

'Algorithm' 카테고리의 다른 글

위상정렬 정리  (0) 2021.06.26
비트마스크 (BitMask)  (0) 2020.12.09
다이나믹 프로그래밍 정리  (0) 2020.09.09
트리 정리  (0) 2020.09.07
그리디&구현, DFS&BFS  (0) 2020.09.01