자료 구조
- 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미
배열
- 가장 기본적인 자료구조
- homogeneous collection: 동일한 데이터 타입만 관리 가능
- 타입이 다른 객체를 관리하기 위해서는 매번 다른 배열 필요
- Polymorphism
- Object를 이용하면 모든 객체 참조 가능 -> Collectiom Framework
- 담을 때는 편리하지만 빼낼 때는 Object로만 가져올 수 있음
- 런타임에 실제 객체의 타입 확인 후 사용해야 하는 번거로움
- Generic을 이용한 타입 한정
- 컴파일 타임에 저장하려는 타입 제한 -> 형변환의 번거로움 제거
Collection Framework
- java.util 패키지
- 다수의 데이터를 쉽게 처리하는 방법 제공 -> DB 처럼 CRUD 기능 중요
- collection framework 핵심 인터페이스
Collection interface
특징
- 입력 순서가 있는 데이터 집합
- 입력 순서가 있으므로 데이터의 중복을 허락
- 관련 클래스 관계도
주요
public class ListTest {
// 문자열을 저장할 List, 구현체는 ArrayList
List<String> friends = new ArrayList<>();
public static void main(String[] args) {
ListTest alt = new ListTest();
alt.createTest();
alt.retrieveTest();
alt.updateTest();
alt.deleteTest();
alt.deleteTest2();
}
public void createTest() {
// TODO: friends에 여러명의 친구를 등록해보자.
friends.add("홍길동");
friends.add("임꺽정");
friends.add(1, "장길산");
friends.add("홍길동");
// END
System.out.println("추가 후 내용 출력: " + friends);
}
public void retrieveTest() {
// TODO: 다양한 조회 기능을 사용해보자.
// 혹시 비어있지는 않나? 요소의 개수는 ?
System.out.println(friends.isEmpty()+" : " + friends.size());
// 반복을 이용한 요소 순회
for(String name : friends) {
System.out.println(name);
}
System.out.println(friends.indexOf("홍길동") + " : " + friends.lastIndexOf("홍길동"));
// 홍길동이 있다면 그 위치 출력
// END
}
public void updateTest() {
// TODO: 홍길동이 있다면 값을 율도국 왕으로 변경해보자.
int idx = friends.indexOf("홍길동");
if(idx >= 0) {
friends.set(idx, "율도국왕");
}
System.out.println("수정 후 : " + friends);
// END
}
public void deleteTest() {
// TODO: 0번째 친구와 율도국 왕을 삭제하시오.
System.out.println(friends.remove(0));
System.out.println(friends.remove("율도국왕"));
// END
System.out.println("삭제 후 : " + friends);
friends.clear();// 리스트 초기화
System.out.println("초기화 후 : " + friends);
}
public void deleteTest2() {
List<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.remove(1);
System.out.println(nums);
}
}
배열과 ArrayList
- 배열의 장점
- 가장 기본적인 형태의 자료 구조로 간단하며 사용이 쉬움
- 접근 속도가 빠름
- 배열의 단점
- 크기를 변경할 수 없어 추가 데이터를 위해 새로운 배열을 만들고 복사해야 함
- 비 순차적 데이터의 추가, 삭제에 많은 시간이 걸림
- 배열을 사용하는 ArrayList도 태생적으로 배열의 장-단점을 그대로 가져감
LinkedList
- 각 요소를 Node로 정의하고 Node는 다음 요소의 참조 값과 데이터로 구성됨
- 각 요소가 다음 요소의 링크 정보를 가지며 연속적으로 구성될 필요가 없다.
- 데이터 삭제 및 추가
- 각 요소가 다음 요소의 링크 정보를 가지며 연속적으로 구성될 필요가 없다.
LinkedList와 ArrayList의 용도
- 결론
- 특정 클래스가 좋고 나쁨이 아니라 용도에 적합하게 사용해야 함
- 소량의 데이터를 가지고 사용할 경우는 큰 차이가 없음
- 정적인 데이터 활용, 단순한 데이터 조회용 : ArrayList
- 동적인 데이터 추가, 삭제가 많은 작업 : LinkedList
자료 삭제 시 주의 사항
-
index를 이용한 for문
- 요소가 삭제되면 size가 줄어들기 때문에 index 차감 필요
- 거꾸로 접근하면 자연스럽게 해결
set interface
- 특징
- 입력 순서를 관리하지 않고 주머니에 구슬을 넣는 형태
- 데이터를 구별할 순서(index)가 없어 중복이 허용되지 않는다.
- 효율적인 중복 데이터 제거 수단
- 관련 클래스 관계도
동일한 데이터의 기준
- SmartPhone도 넣어보자
public class SmartPhone {
// END
String number;
public SmartPhone(String number) {
this.number = number;
}
public String toString() {
return "전화 번호: " + number;
}
// TODO: 동일한 번호의 SmartPhone이면 하나만 추가될 수 있도록 처리하시오.
@Override
public int hashCode() {
return number.hashCode();
}
@Override
public boolean equals(Object obj) {
if(obj!= null && obj instanceof SmartPhone phone) {
return this.number.equals(phone.number);
}
else return false;
}
// END
}equals()가 true를 리턴하고 hashCode()값이 같을 것
Map interface
- 특징
- Key와 Value를 하나의 Entry로 묶어서 데이터 관리
- Key : Object형태로 데이터 중복을 허락하지 않음
- Value : Object 형태로 데이터 중복이 허락 됨.
- Key와 Value를 하나의 Entry로 묶어서 데이터 관리
- 관련 클래스 관계도
Map interface의 주요 메서드
public class MapTest {
Map<String, String> hMap = new HashMap<>();
private void addMethod() {
System.out.println("추가 성공?: " + hMap.put("andy", "1234"));
// 동일한 키의 사용 결과는?
System.out.println("추가 성공?: " + hMap.put("andy", "4567"));
hMap.put("kate", "9999");
// 기존에 해당 키에 대한 값이 없을 때만 추가하기
hMap.putIfAbsent("kate", "1234");
hMap.put("henry", "4567"); // 동일한 값
hMap.put("hong", "1234");
System.out.println("추가 결과: " + hMap);
}
private void retrieveMethod() {
// TODO: kate의 전화번호가 있나요?
System.out.println(hMap.get("kate"));
System.out.println(hMap.containsKey("kate"));
// END
// TODO: map이 가지고 있는 key와 거기에 연결된 value를 출력하시오.
Set<String> keys = hMap.keySet();
for(String key : keys) {
System.out.println("key: " + key + ", value: " + hMap.get(key));
}
// END
// TODO: 값이 4567인 사람의 이름은?
Set<Entry<String,String>> entries = hMap.entrySet();
for(Entry<String, String> entry : entries) {
System.out.println(entry.getKey() + " : " + entry.getValue());
if(entry.getValue().equals("4567")) {
System.out.println("발견: " + entry.getKey());
}
}
// END
}
private void removeMethod() {
// TODO: andy의 자료를 삭제하고 출력하시오.
hMap.remove("andy");
System.out.println("삭제 후: " + hMap);
hMap.clear();
System.out.println("초기화 후" + hMap);
// END
}
public static void main(String[] args) {
MapTest hmt = new MapTest();
hmt.addMethod();
hmt.retrieveMethod();
hmt.removeMethod();
}
}정렬
- 요소를 특정 기준에 대한 내림차순 또는 오름 차순으로 배치하는 것
- 순서를 가지는 Collection들만 정렬 가능
- List 계열
- Set에서는 SortedSet의 자식 객체
- Map에서는 SortedMap의 자식 객체(Key 기준)
- Collections의 sort()를 이용한 정렬
- sort(List list)
- 객체가 Comparable을 구현하고 있는 경우 내장 알고리즘을 통해 정렬
- sort(List list)
- SmartPhone 정렬
public class SmartPhone implements Comparable<SmartPhone>{
// END
String number;
...
@Override
public int compareTo(SmartPhone o) {
return number.compareTo(o.number);
}
}
public class ListSortTest {
private List<String> names = Arrays.asList("Hi", "Java", "World", "Welcome");
public void sortPhone() {
// TODO: 전화 번호에 따라 SmartPhone을 정렬해보자.
List<SmartPhone> phones = Arrays.asList(new SmartPhone("010"), new SmartPhone("111"), new SmartPhone("001"));
Collections.sort(phones);
// END
}
}Comparator의 활용
- 객체가 Comparable을 구현하고 있지 않거나 사용자 정의 알고리즘으로 정렬하려는 경우
- String을 알파벳 순이 아닌 글자 수 별로 정렬하려면?
- sort(List list, Comparator<? super T> c)
public class StringLengthComparator implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
int len1 = o1.length();
int len2 = o2.length();
return Integer.compare(len1, len2);
}
}
public void stringLengthSort() {
// TODO: 문자열의 길이에 따라 names를 정렬해보자.
Collections.sort(names, new StringLengthComparator());
// END
System.out.println(names); // [Hi, Java, World, Welcome]
}