Day10 - 동적할당, 자료 구조, List와 Set

Java의 Collection Framework

• Java에 추가된 Collection Framework를 사용하기 위해선 Interface를 이용한다.

동적할당

• 객체를 새로 생성해 그 객체 안에 이전의 객체를 레퍼런스하는것을 반복한다.
• 배열의 복사와 달리 객체생성을 통한 동적할당은 낭비하는 메모리가 없어 성능이 더 뛰어나다.
  • 다만 읽어들일때에는 배열보다 성능이 떨어진다.

class Node{  
  int su;  
  Node nxt;  
}

class Linked{
    Node node;
    int cnt;

    void add(int su) {
      node.su = su;
      Node temp2 = node; 
       // 1.   
       Node node = new Node();  
       node.su = su;  
       // 2.  
       Node node = new Node();  
       node.su = su;  
       this.node.nxt = node;  
       // 3.   
       Node node = new Node();  
       node.su = su;  
       this.node.nxt.nxt = node;  
       // 4.   
       Node node = new Node();  
       node.su = su;  
       this.node.nxt.nxt.nxt = node;
    }
  int get(int idx) {
    if(idx == 0) return node.su;
    if(idx == 1) return node.nxt.su;
    if(idx == 2) return node.nxt.nxt.su;
    return node.nxt.nxt.nxt.su;
  }

반복문을 통한 동적할당

class Node{
    int su;
    Node nxt;
}

class Linked{
    Node node;
    int cnt;

    void add(int su) {
        cnt++;
        Node temp = new Node();

        temp.su = su;
        if(cnt == 1) {
            this.node = temp;
        }else {
            Node temp2 = this.node;
            while(true) {
                if(temp2.nxt == null) break;
                temp2 = temp2.nxt;
            }
            temp2.nxt = temp;
        }
            }
    int get(int idx) {

        Node temp = this.node;
        for(int i = 0; i < idx; i++) {
            temp = temp.nxt;
        }
        return temp.su;
    }
    int size() {
        return cnt;
    }
}

public class Ex01 {

    public static void main(String[] args) {
        Linked list = new Linked();
        list.add(1111);
        list.add(2222);
        list.add(3333);
        list.add(4444);

        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

}

Java에서 제공하는 동적할당

• java.util.List 인터페이스에 저장된 Collection Framework

        //java가 제공하는 클래스
        java.util.LinkedList list1 = new java.util.LinkedList();
        list1.add(1111);
        list1.add(2222);
        list1.add(3333);
        list1.add(4444);

        for(int i = 0; i < list1.size(); i++) {
            System.out.println(list1.get(i));
        }

        // 배열을 활용한 동적할당
        java.util.ArrayList list2 = new java.util.ArrayList();
        list2.add(1111);
        list2.add(2222);
        list2.add(3333);
        list2.add(4444);

        for(int i = 0; i < list1.size(); i++) {
            System.out.println(list1.get(i));
        }

• 배열을 사용한 동적할당은 이론적으로 read에 유리, create, update, delete에 불리하다.
• 객체를 활용한 동적할당은 이론적으로 create, update, delete에 유리, read에 불리하다.

---

객체와 배열의 수행시간 평가하기

    public static void main(String[] args) {
        java.util.LinkedList list1;
        list1 = new java.util.LinkedList();

        long before = System.currentTimeMillis();
        for(int i = 0; i < 10000000; i++) {
            list1.add(i);
        }
        long after = System.currentTimeMillis();

        System.out.println("객체 동적할당의 수행시간 : " + (after - before) + "ms");

        java.util.ArrayList list2;
        list2 = new java.util.ArrayList();

        before = System.currentTimeMillis();
        for(int i = 0; i < 10000000; i++) {
            list2.add(i);
        }
        after = System.currentTimeMillis();

        System.out.println("배열 동적할당의 수행시간 : " + (after - before) + "ms");

        // read의 수행시간
        before = System.currentTimeMillis();
        Object obj;
        for(int i = 0; i < 10000000; i++) {
            list1.get(i);
        }
        after = System.currentTimeMillis();

        System.out.println("객체 동적할당의 read시간 : " + (after - before) + "ms");
        before = System.currentTimeMillis();
        for(int i = 0; i < 10000000; i++) {
            obj = list2.get(i);
        }
        after = System.currentTimeMillis();

        System.out.println("배열 동적할당의 read시간 : " + (after - before) + "ms");
    }

객체 동적할당의 수행시간 : 1551ms
배열 동적할당의 수행시간 : 964ms

=> List를 사용할 떄는 배열을 사용하는것이 좋다.

---

자료구조

1. 선형
   • 순서가 없다.
   • 반복이 가능하다.
   • 인덱스를 통해 자료를 관리한다. (예: ArrayList, LinkedLisk, ...)
   • Queue : 선입선출
   • Stack : 선입후출
   • Deque: 후입선출
2. 비선형
   • 순서가 없다.
   • 중복이 불가능하다.
   • (예: java.util.HashSet())

java.util.HashSet set;
set = new java.util.HashSet();

set.add("첫번째");
set.add("두번째");
set.add("세번째");
set.add("네번째");
set.add("다섯번째");

// 비선형 구조의 data 읽기
java.util.Iterator ite = set.iterator();
System.out.println(ite.next());
System.out.println(ite.next());
System.out.println(ite.next());
System.out.println(ite.next());
System.out.println(ite.next());

=> 비선형 구조는 중복된 자료를 넣어도 합쳐진다.

java.util의 인터페이스들

// 선형
java.util.List list;
list  = new java.util.ArrayList();

// 추가하기
list.add("첫번째");
list.add("세번째");
list.add(1, "두번째");

System.out.println(list);

// 삭제하기
// list.clear();
list.remove(1); // 지운 값을 반환
list.remove("두번째"); // boolean으로 반환 
System.out.println(list.isEmpty());

// 불러오기
boolean boo1 = list.contains("두번째");
System.out.println(list);
System.out.println(boo1);

java.util.List list2;
list2 = new java.util.ArrayList();
list2.add("첫번째");
list2.add("두번째");
list2.add("세번째");
System.out.println(list2);

System.out.println(list == list2);
System.out.println(list.equals(list2));

// 가져오기
//System.out.println(list.get(1));
System.out.println(list.indexOf("두번째"));
System.out.println(list.lastIndexOf("두번째"));

System.out.println(list.hashCode());
System.out.println(list2.hashCode());

java.util.List list3;
list3  = new java.util.ArrayList();

list3.add(1);
list3.add(2);
list3.add(3);
list3.remove(1); // 우선순위 Index가 먼저 지워진다. 

System.out.println(list3);

// 수정하기
list.set(1, "2번째");
System.out.println(list);

// 사이즈 반환
System.out.println(list.size());

// sublist
list3 = list2.subList(0, 1);
System.out.println(list3);

// Object 배열로 반환
// String[] arr = list.toArray();
// String[] arr = (String[])list.toArray(); // 적용 불가 - 수행해보기 전까지 캐스팅이 되는지 알수없다.
Object[] arr = list.toArray();
System.out.println(java.util.Arrays.toString(arr));

String[] tmp = new String[list.size()];
for(int i = 0; i < list.size(); i++) {    // String 배열에 list array를 적용하는 방법 
    tmp[i] = (String)arr[i];
}

ArrayList

ArrayList list1 = new ArrayList();
ArrayList list2 = new ArrayList(3); // Initial capacity 지정

// List의 복사 
list1.add(1111);
list1.add(2222);
ArrayList list3 = new ArrayList(list1);
System.out.println(list1 == list3); // false - list3은 복사된 레퍼런스 

java.util.List list4 = list1.subList(0, list1.size());
System.out.println(list1 == list4); // false

list2.addAll(list1);
System.out.println(list2); // [1111, 2222]
System.out.println(list1 == list2); // false

// 끼워넣기
list2.addAll(1, list1);
System.out.println(list2); // [1111, 1111, 2222, 2222]

// shadow copy (옅은복사)
ArrayList list5 = (ArrayList)list1.clone();
System.out.println(list4);
System.out.println(list1 == list4);

// 읽기
// int su = list1.get(1); // 불가 
Object su = list1.get(1); 
int su2 = (int)list1.get(1);
System.out.println(su2);

// 사용되지 않은 사이즈 날리기
list1.trimToSize();

LinkedList

Queue

LinkedList list1 = new LinkedList();
list1.add(1111);
list1.add(2222);
list1.add(3333);
list1.add(4444);

// 복사
LinkedList list2 = new LinkedList(list1);
System.out.println(list2);

ArrayList list3 = new ArrayList(list1);
System.out.println(list3);

// QUEUE : 선형 자료 구조 중 선입선출 
Queue list4 = new LinkedList();

// 에러시 Special value를 리턴하는 메서드 사용
list4.offer("첫번째");
list4.offer("두번째");
list4.offer("세번째");
list4.offer("네번째");

// System.out.println(list4.peek()); // 첫번째
// list4.poll();
// System.out.println(list4.peek()); // 두번째 
// list4.poll();
// System.out.println(list4.peek()); // 세번째
// list4.poll();
// System.out.println(list4.peek()); // 네번째
// list4.poll();
// System.out.println(list4.peek()); // null

// 반복으로 list 살펴보기
// while(list4.peek() != null) {
//         System.out.println(list4.poll());
// }

Object obj;
while((obj = list4.peek()) != null) {
    System.out.println(obj);
    list4.poll();
}

Deque (Stack)

Deque stack = new LinkedList();

// 선입선출
stack.offerFirst("첫번째");
stack.offerFirst("두번째");
stack.offerFirst("세번째");

System.out.println(stack.pollFirst()); // 세번쨰
System.out.println(stack.pollFirst()); // 두번째
System.out.println(stack.pollFirst()); // 첫번째
System.out.println(stack.pollFirst()); // null

Deque stack2 = new LinkedList();

// 후입후출
stack2.offerLast("첫번째");
stack2.offerLast("두번째");
stack2.offerLast("세번째");

System.out.println(stack2.pollLast()); // 세번쨰
System.out.println(stack2.pollLast()); // 두번째
System.out.println(stack2.pollLast()); // 세번째
System.out.println(stack2.pollLast()); // null