【Java】 6강. 자료구조

6강. 자료구조

 

추천글 : 【Java】 Java 목차 

---

1. 개요 [본문]

2. 리스트 [본문]

3. 셋 [본문]

4. 큐 [본문]

5. 맵 [본문]

---

a. Python 자료구조

b. GitHub 

---

 

1. 개요 [목차]

⑴ collection : 여러 개의 원소들의 집합이 객체화한 것

⑵ arrays와 collections의 비교

 

arrays	collections
고정 사이즈	가변 사이즈
객체와 primitive type 모두 저장	객체만을 저장
오직 연속적인 메모리 공간	고유의 자료구조가 있음
utility method가 없음	utility method가 있음

Table. 1. Arrays와 Collections의 비교

 

⑶ collection interface 

① 정의 : 다른 collection의 루트 인터페이스  

② 종류 : 대표적으로 List와 Set이 있음

 

출처 : 이미지 클릭

Figure. 1. collection interface hierarchy

 

① collection interface method

○ boolean add(Object element)

○ boolean remove(Object element)

○ int size()

○ boolean isEmpty()

○ boolean contains(Object element)  

 

 

2. 리스트(list) [목차]

⑴ 일반적인 특징

① 정렬된 collection

② integer index로 element에 접근할 수 있음

③ java.util.List에 저장되어 있음

④ method

○ boolean add(E e)

○ void add(int index, E element)

○ E get(int index)

○ E remove(int index)

○ boolean remove(Object o)

○ List<E> subList(int fromIndex, int toIndex)

○ int indexOf(Object o) 

⑵ ArrayList 

① 물리적으로 메모리가 연속돼 있음

⑶ LinkedList 

① 각 노드는 정방향과 역방향의 포인터를 정의하고 있음. memory space를 preoccupy하지 않음 

② method 

○ void addFirst(Object o) 

○ void addLast(Object o) 

○ Object getFirst() 

○ Object getLast() 

○ Object removeFirst() 

○ Object removeLast() 

⑷ ArrayList와 LinkedList의 퍼포먼스 비교 (ref)^]

 

출처 : 이미지 클릭

Figure. 2. ArrayList와 LinkedList의 퍼포먼스 비교^]

 

① ArrayList : get 함수의 실행이 빠른 편. 연속된 메모리를 따라가서 빈 공간에 새로운 정보를 입력하면 되므로

② LinkedList : add 함수 및 remove 함수의 실행은 빠른 편. 포인터만 추가하면 되므로

⑸ (참고) Iterator 

① 인터페이스의 한 종류로 List 밖에서 List를 제어하기 위해 사용함

② 사용하는 이유 

○ 반복적으로 배열 내 원소로 연산을 함에 있어 Iterator를 쓰면 더 효율적

○ add, remove 연산을 할 때 Iterator를 쓰지 않으면 헷갈리거나 에러가 발생할 수 있음

ConcurrentModificationException Error!

③ method : 커서 개념으로 작동하여 왼쪽에 놓인 아이템을 추가 및 삭제함

 

Figure. 3. Iterator의 개념

 

○ boolean hasNext() 

○ E next() 

○ void remove() 

⑹ (참고) SortedList<T extends Comparable<? super T>>의 의미 (ref)^]

① <?> : any type 

② <? super T> : T 또는 T의 super type

③ Comparable<? super T> : T 또는 T의 super type 간 크기 비교를 가능케 함

④ extends : generic은 interface라고 해도 extends를 씀

⑤ <T extends Comparable<? super T>> : <? super T>를 implements하는 T만을 객체로 하겠다는 의미

⑥ Comparable<T>를 썼다면 T의 super type이 Comparable을 implements 했어도 T에서 별도로 implements 해야 함

⑦ (주석) <? super T>는 조건을 더 느슨하게 하므로 "wild card"의 성격을 가짐

3. 셋(set) [목차]

⑴ 개요

① duplicate elements가 없음

⑵ 공통 method : position의 개념이 없음

① boolean add(E e); 

② boolean remove(Object o); 

③ boolean contains(Object o); 

④ int size(); 

⑤ Object[] toArray(); 

⑥ println(); // Set의 출력 순서와 Iterator의 iteration 순서는 같음 

⑦ .addAll(Set set);

⑧ .removeAll(Set set);

⑶ HashSet 

① 메커니즘 : 많은 메모리를 소모함

 

출처 : 서울대학교 컴퓨터 프로그래밍(이영기 교수님) 수업

Figure. 4. HashSet의 메커니즘^]

 

⑷ TreeSet 

① TreeSet은 depth-first traversal 순서로 원소를 보여줌

② natural order 

○ 작은 값에서 큰 값으로 정렬되는 오름차순 정렬에만 사용됨

○ Comparable<T>를 implements하고 compareTo() method를 재정의하여 사용 

 

class Employee implements Comparable<Employee>{
    String str;
    Employee(String str) {
        this.str = str;
    }
    @Override
    public int compareTo(Employee e){
        return str.compareTo(e.str);
    }
    @Override
    public String toString(){
        return str;
    }
}
public class Main{
    public static void main(String[] args){
        Set<Employee> set = new TreeSet<>();
        Employee e1 = new Employee("B");
        Employee e2 = new Employee("A");
        set.add(e1);    set.add(e2);
        System.out.println(set); // [A, B]
    }
}

 

③ special order

○ 오름차순 이외의 기준으로도 정렬할 수 있게 됨

○ Comparator<T>를 implements하고 compare() method를 재정의하여 사용

○ natrual order와 달리 새로운 class를 정의해야 하고 TreeSet을 정의할 때 약간 달라짐

 

class Employee{
    String str;
    Employee(String str) {
        this.str = str;
    }
    @Override
    public String toString(){
        return str;
    }
}
class EmployeeComp implements Comparator<Employee>{
    @Override
    public int compare(Employee e1, Employee e2){
        return e1.str.compareTo(e2.str);
    }
}
public class Main{
    public static void main(String[] args){
        Set<Employee> set = new TreeSet<>(new EmployeeComp());
        Employee e1 = new Employee("B");
        Employee e2 = new Employee("A");
        set.add(e1);    set.add(e2);
        System.out.println(set);
    }
}

 

④ 관련 예제 

4. 큐(queue) [목차]

⑴ Queue 

① 일반적으로 FIFO(first-in-first-out)으로 작동하지만 FIFO가 아닌 Queue도 있음

② method

○ boolean add(E e)

○ E remove() : retrieves and removes the head of this queue

○ E poll() : retrieves and removes the head of this queue

○ E peek() : retrieves, but does not remove, the head of this queue

⑵ Deque 

① double ended queue의 약자

② method

○ void addFirst(E e) 

○ void addLast(E e) 

○ void peekFirst() 

○ void peekLast() 

○ void pollFirst() 

○ void pollLast() 

⑶ PriorityQueue 

① min/max heap의 일종

② poll 등의 method를 실행할 때 가장 작은 원소를 출력함

 

 

5. 맵(map) [목차]

⑴ map interface 

Figure. 5. map interface hierarchy

 

① 개요

○ key는 unique함 : 하나의 key는 맵에서 오직 한 번 나타남. 하나의 key는 하나의 value만 맵핑할 수 있음

○ value는 unique하지 않음 

○ Map의 key set이나 value set은 많은 경우 Collection 형태

② method

○ put(K key, V value) 

○ V get(Object key) 

○ boolean containsKey(Object key) 

○ boolean containsValue(Object value) 

○ boolean isEmpty() 

○ Set<K> keySet() 

○ int size()

⑵ HashMap 

⑶ TreeMap 

① natural order와 special order : TreeSet 참고

 

입력: 2020.10.20 22:08