자료구조(Data Structure)
자료구조란?
프로그램을 작성하는 과정에는 여러 데이터가 필요 합니다. 예를들어 100명의 학생 성적을 처리한다고 할때 각각의 성적 값을 변수에 할당한다면 100개의 변수가 필요합니다. 이런경우 배열을 이용하면 하나의 변수명으로 100개의 데이터를 처리할 수 있게 됩니다.
자료구조는 컴퓨터 프로그램에서 데이터를 처리하기 위해 만든 구조로 Array, List, Map이 대표적인 형태 입니다. 이 외에 프로그램 언어에 따라 Tuple, Dictionary 등을 사용하기도 합니다
배열(Array)
배열은 가장 전통적이고 기본이 되는 자료 구조 입니다. 데이터를 순차적으로 저장해 0부터 시작하는 인덱스를 통해 접근할 수 있습니다.
- 일반적으로 배열은 선언할때 크기가 고정됨.
- 데이터를 순차적으로만 접근할 수 있어 위치를 모르는 경우 효율이 떨어짐.
- 배열에 들어가는 데이터는 모두 동일한 자료형 이어야 함.
- 배열 중간에 값을 추가하려면 기존 데이터를 모두 이동시켜야 함.
가장 기본적인 자료형으로 프로그램 개발에 빼놓을수 없는 필수 요소 입니다. 그러나 구조에 따른 제약과 사용의 불편함등으로 인해 List를 더 많이 사용합니다. 그러나 순차적으로 사용하는 단순한 숫자나 문자등으로 이루어진 집합형 데이터의 처리에 있어 배열만큼 간단하고 빠른 자료구조는 없습니다.
리스트(List)
배열과 유사한 순차적인 자료구조를 제공 합니다. 객체지향 프로그램언어에는 보통 List 자료구조가 기본적으로 제공되며 그렇지 않을 경우 직접 자료구조를 구현하거나 구현된 라이브러리를 사용해야 합니다.
데이터 접근을 위해 인덱스를 사용해야 하는 점은 배열과 같지만 배열의 모든 문제점을 해결하고 있습니다.
- 데이터 크기가 고정되지 않음.
- 데이터를 다루기 위한 여러 방법이 제공됨.
- 리스트의 데이터는 서로 다른 타입일 수 있음. -> 일관된 처리가 어려워 보통은 동일하게 처리함.
- 배열 중간에 값을 추가하거나 삭제하기 쉬움.
- 특정 데이터가 포함되어 있는지 확인은 가능하나 검색을 위해서는 별도 구현이 필요.
Linked List는 현재 데이터에 다음 데이터를 읽을 수 있는 정보를 추가한 것으로 불연속적으로 존재하는 데이터를 서로 연결할 수 있는 방법을 제공 합니다. Double Linked List는 이전과 다음 데이터 정보를 모두 가지고 있는 형태이며 자바의 경우 LinkedList 클래스가 제공되는데 실제로는 Double Circular Linked List(순환구조가 추가된 Double Linked List) 형태를 구현해 둔 것입니다.
맵(Map)
데이터를 Key:Value(키:값)의 쌍으로 저장하는 방식입니다. 실제 데이터가 저장되는 형태는 내부구조에 따르며 사용하는 쪽에서는 내부구조에 대해 신경쓸 필요가 없는 형태 입니다.
맵을 사용했을때 얻을 수 있는 가장 큰 장점은 원하는 데이터를 손쉽게 찾을 수 있다는 점입니다.
- 데이터를 저장할 때 해당 데이터를 찾기 위한 Key를 부여.
- Key값을 알면 언제든 쉽게 데이터를 찾을 수 있음.
- Value 에 객체형이 들어갈 수 있어 복잡한 데이터 처리가 가능.
이터레이터(Iterator)
이터레이터는 서로다른 자료구조(Vector, ArrayList, LinkedList)의 데이터를 동일한 방법으로 다음 데이터에 접근하는 방법을 제공하는 인터페이스로 자바 컬렉션 프레임워크의 일부 입니다.
컬렉션 프레임워크(Collection Framework)
컬렉션 프레임워크는 자바에서 데이터를 저장하는 클래스들을 표준화한 설계 구조를 말합니다. 이러한 구조를 바탕으로 자바의 기본 자료구조 클래스들이 구성되어 있으며 체계화되고 일관된 구조를 가지게 되었습니다.
Collection, Map, List, Set 인터페이스를 중심으로 다음과 같은 클래스 계층구조를 형성하고 있습니다.
List : 순서가 있는 데이터의 집합. 데이터의 중복을 허용 ArrayList, LinkedList
Set : 순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않음 HashSet, LinkedHashSet
Map : 키(key)와 값(value)의 쌍으로 이루어진 데이터 집합. 순서 유지 X, 키 중복 X, 값 중복 O HashMap, LinkedHashMap, Properties
Collection 인터페이스
List 와 Set 의 상위 인터페이스 입니다. 즉, List 와 Set 를 구현한 모든 클래스들은 Collection 인터페이스의 메서드를 사용할 수 있으므로 구현클래스와 상관없이 동일한 방법으로 데이터를 다룰 수 있습니다.
컬렉션안에 들어가는 데이터들은 모든 타입이 가능하지만 타입이 다른 경우 일관된 처리가 어렵기 때문에 타입 파라미터를 사용합니다.
Collection<String> c = new HashSet<>();- 순서가 없고 데이터 중복을 허용하지 않는 자료구조인 HashSet 객체 생성.
- 저장되는 데이터는 문자열로 한정.
- 원래는 new HashSet(); 이지만 타입추론을 통해 생략 가능.
컬렉션 객체의 생성
모든 컬렉션 클래스들은 java.util 패키지에 들어 있습니다. 컬렉션 객체를 생성하는 방법은 참조변수 선언시 상위 인터페이스 타입을 사용하고 객체 생성은 필요에 따라 구체적인 클래스들을 사용하는 형식 입니다.
ArrayList<String> list = new ArrayList<>(); // 권장안됨
List<String> list = new ArrayList<>(); // 권장됨컬렉션 객체를 생성하는 방법은 다양하며 상황에 따라 적절한 방법을 사용하면 됩니다.
Collection<String> c1 = new HashSet<>();
Collection<String> c2 = Arrays.asList("three", "four");
Collection<String> c3 = Collections.singleton("five");- c1: 빈 HashSet 객체를 생성. 데이터는 직접 add() 메서드를 통해 넣어야 함.
- c2: 두개의 데이터를 가지는 List 객체를 생성.
- c3: 데이터가 하나인 유일한 인스턴스를 보장하는 Set 객체를 생성.
컬렉션에 데이터 추가, 삭제
데이터 추가는 add(), addAll() 메서드를 사용 합니다. 지정된 타입의 데이터를 하나씩 추가할때는 add(), 컬렉션 타입을 추가할때는 addAll() 을 이용해 개별 원소를 꺼내어 추가하는 형식입니다.
c1.add("one");
c1.addAll(c2);데이터의 삭제는 remove(), removeAll(), retainAll(), clear() 등의 메서드를 사용 합니다. retailAll()의 경우 인자의 데이터를 제외한 나머지 데이터를 모두 삭제하는 메서드이고 clear() 는 모든 데이터를 삭제 합니다.
c1.remove("one");
c1.remove("c2");
c1.retainAll("four");
c1.clear();컬렉션 데이터 확인 및 변환
특정 데이터가 컬렉션 안에 존재 하는지 혹은 비어 있는지를 확인할 수 있으며 크기를 구할 수 있습니다.
c1.isEmpty();
c1.contains("zero");
c1.containsAll(c2);컬렉션 데이터의 크기는 size() 메서드를 통해 구할 수 있으며 데이터 변환은 toArray() 메서드를 이용해 배열형태로 변경할 수 있습니다. 다만 Object 타입으로 리턴 되므로 특정 타입을 원한다면 해당 객체 생성 코드를 넣어주어야 합니다.
int size = c1.size();
Object[] converted1 = c1.toArray();
String[] converted2 = c1.toArray(new String[c1.size()]);컬렉션 데이터의 사용
컬렉션에 들어있는 데이터를 사용하기 위해서는 다소 복잡한 과정을 거쳐야 합니다. 컬렉션 자체는 구체적인 구현이 아니므로 직접적으로 데이터에 접근하는 방법은 포함되어 있지 않습니다.
List 나 Set 인터페이스를 이용해 처리하거나 Collection 인터페이스 타입으로 처리하려면 다음의 방법중 하나를 사용할 수 있습니다.
a) 배열로 변환해서 for문과 사용
특정 위치의 데이터를 직접 선택할 필요없이 순차적으로 모든 데이터를 사용하는 경우 단순하게 for 문만 사용해도 됩니다.
for(String s : c1) {
System.out.println(s);
}그러나 특정 위치의 데이터를 직접 다루고자 한다면 앞에서 다룬 toArray() 메서드를 이용해 배열로 변환해 사용하는 방법을 사용해야 합니다. 배열 데이터는 인덱스로 접근할 수 있으므로 각각의 데이터를 차례로 접근하거나 특정 위치 데이터를 직접 접근해 사용할 수 있습니다.
String[] converted2 = c1.toArray(new String[c1.size()]);
for(int i=0; i < converted2.length; i++) {
System.out.println(converted2[i]);
}b) Iterator를 사용
Iterator는 다음 데이터에 접근하는 방법을 제공하는 인터페이스 입니다. Collection 인터페이스는 Iterable 인터페이스를 상속받고 있으며 iterator() 메서드로 Iterator 객체를 구할 수 있습니다.
여기서는 모두 데이터 출력을 예시로 살펴보고 있지만 획득한 데이터를 조작하거나 다른 메서드의 인자로 전달하는등 필요한 작업에 활용할 수 있습니다.
Iterator iter = c1.iterator();
while(iter.hasNext()) {
System.out.println(iter.next());
}c) forEach()를 사용
c1.forEach(s -> System.out.println(s));
c1.forEach(System.out::println);Collection 실습예제
public class CollectionTest {
public static void main(String[] args) {
// Create a new HashSet and add data
Collection<String> c1 = new HashSet<>();
c1.add("one");
c1.add("two");
// Create a new List with two values
Collection<String> c2 = Arrays.asList("three", "four");
Collection<String> c3 = Collections.singleton("five");
// add all data in c2, c3 to c1
c1.addAll(c2);
c1.addAll(c3);
// get size of collection
System.out.println("Size of c1 : " + c1.size());
// convert collection to array
Object[] converted1 = c1.toArray();
String[] converted2 = c1.toArray(new String[c1.size()]);
// print all data in collection using for loop
for (String s : c1) {
System.out.println(s);
}
// access and print all data in the array which converted from collection
for (int i = 0; i < converted2.length; i++) {
System.out.println(converted2[i]);
}
// get Iterator object from collection and access the data
Iterator iter = c1.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
// run specific code using every elements in the collection
c1.forEach(System.out::println);
}
}- 최종적으로 컬렉션 c1 의 데이터는 one, two, three, four, five 가 됨.
- HashSet 의 특성상 순서가 보장되지 않으므로 데이터를 넣는 순서대로 출력되는 것은 아님.
- 4가지 방법으로 데이터를 출력하고 있으므로 동일 결과가 4번 반복됨.
Size of c1 : 5
four
one
two
three
five
four
...참고
