15일차 수업 정리(ArrayList, LinkedList, 자료구조)

**List
    => 자료구조에서는 배열도 List로 분류
    => java에서는 배열은 다른 종류로 구분
1. 종류
  1) Array(배열 - Dense List)
    => 동일한 자료형의 연속적인 모임
    => 크기가 고정 -  크기 변경 불가
    => 장점 : 메모리 낭비가 없음
    => 단점 : 데이터 삽입, 삭제시 복사 작업이 필요

  2) Vector(ArrayList)
    => 동일한 자료형의 연속적인 모임
    => 크기가 가변적 - 변경이 가능(여분의 공간을 미리 확보)
    => 장점 : 데이터 접근 속도가 LinkedList보다는 빠름 
    => 단점 : 메모리 낭비가 발생할 수 있음
                  중간에 데이터 삽입, 삭제시는 느림
    => 데이터베이스에서 데이터를 가져와서 사용할 때 많이 사용

  3) LinkedList
    => 동일한 자료형의 연속적인 모임 - 연속은 논리적인 개념
    => 크기가 가변 - 크기 변경이 가능(여분의 공간을 확보)
    => 장점 : 데이터를 중간에 삽입하거나 삭제시 빠르게 작업
                  연속된 빈 공간이 없어도 생성 가능
    => 단점 : 메모리 낭비가 발생할 수 있음
                  데이터 접근 속도가 느림
    => 응용프로그램에서 데이터를 저장 할 때 많이 사용

  4) Stack
    => LIFO(Last In First Out) : 마지막에 삽입한 데이터가 첫번째로 출력되는 구조
    => push, pull 로 데이터를 삽입, 삭제
    => 컴퓨터에서 연산 처리, IDE들이 괄호 검사시 사용. 프로그램이 메소드 호출시 메소드 마다 하나씩 생성하여 사용
   
  5) Queue
    => FIFO(First In First Out) : 첫번째 삽입한 데이터가 첫번째로 출력
    => 운영체제에서 명령어 저장(스케쥴링), 공장자동화 등에서 사용

  6) Deque
    => 양쪽에 삽입과 삭제가 가능한 자료구조
    => 스마트 폰에서 List계열의 뷰에서 이용

**java.util.ArrayList : 크기가 변하는 배열 클래스 - 예전 버전으로 Vector도 있음
java.lang.Object 
java.util.AbstractCollection 
java.util.AbstractList 
java.util.ArrayList 
=>클래스 상속 계층

All Implemented Interfaces : Serializable, Cloneable, Iterable, Collection, List, RandomAccess
=>구현된 엔터페이스
Cloneable: clone 메소드를 구현
Iterable: iterator 메소드를 구현

Direct Known Subclasses : AttributeList, RoleList, RoleUnresolvedList
=>ArrayList로 부터 상속받은 클래스

1. 생성자
ArrayList, ArrayList()
    => 는 제너릭이 적용된 클래스

생성을 할 때는 ArrayList<실제 자료형> 변수명 = new ArrayList<실제 자료형>();
    => 생성자에서 실제 자료형은 1.7버전부터는 생략이 가능

2. 메소드
  1) void add(데이터), void add(위치, 데이터)
    => Method Overloading : 메소드 이름은 같고 매개변수의 자료형이나 갯수가 다른 경우
  2) E get(int Index) : Index번째 데이터 가져오기
  3) E remove(int Index) : Index 번째 데이터 지우기
      E remove(E element) : element에 해당하는 데이터 지우기
  4) int size(); 데이터 갯수 리턴
    => 데이터 전체 접근은 get과 size, 빠른 열거로 가능
  5) String toString() : 데이터 각각의 toString()을 호출해서 괄호로 묶어서 리턴
  6) void sort(Comparator comparator) : 데이터를 comparator를 이용해서 비교한 후, 정렬해주는 메소드

**java.util.LinkedList
    => 데이터를 논리적으로 연속해서 저장하는 List
    => 다음 데이터의 위치를 기억해서 다음 데이터에 접근하는 방식
    => ArrayList보다 데이터 접근 속도는 느리지만 데이터를 중간에 삽입하고 삭제하는 것은 편리

**sort
    => 정렬시 2개의 데이터를 크기 비교할 수 있는 메소드를 제공
        - 자바에서는 이 메소드를 Comparator 인터페이스를 이용해서 구현하도록 강제
        - 메소드의 리턴 값이 양수이면 2개의 위치를 변경하고 리턴값이 음수이면 위치를 그대로 둠
    => 데이터 정렬시 오름차순, 내림차순 정렬 및 개발자가 직접 만든 클래스의 인스턴스를 가지고 정렬해 볼것 
    => 여러개의 데이터를 묶어서 하나의 행을 표현하기 위한클래스 작성 순서
      1) 각 속성을 저장할 프로퍼티를 private로 생성
      2) 인스턴스 생성을 위한 생성자를 작성 : 매개변수가 없는 생성자는 필수
      3) 프로퍼티를 접근하기 위한 접근자 메소드
      4) 디버깅을 위한 toString 메소드
      5) 2,3,4는 [Source] 메뉴를 이용하여 자동 생성

** Stack
    => LIFO(Last In First Out) : 마지막에 삽입된 데이터가 먼저 출력되는 구조
1. 생성 : Stack<데이터 자료형> 변수명 = new Stack<>();
2. 메소드
  1) void push(데이터) : 데이터 삽입
  2) 자료형 변수명 = pop() : 가장 마지막에 삽입된 데이터가 리턴되서 변수에 대입(마지막 데이터 삭제)
  3) 자료형 변수명 = peek() : 가장 마지막에 삽입된 데이터가 리턴되어 변수에 대입(마지막 데이터 삭제 X)
    => 메모리 공간이 가득찬 상태에서 push를 하게되면 Overflow
         데이터가 없는데 pop이나 peek를 하면 Underflow
3. 용도
    => 수식 계산, *문법 체크(괄호 - 코딩테스트 단골), 메소드 지역변수 저장

** Queue
    => FIFO(First In First Out) : 먼저 삽입한 데이터가 먼저 출력되는 구조
    => 스케쥴링(명령어들을 저장해 두었다가 순서대로 실행하는 것 - 공장 자동화 분야에 많이 이용)에 주로 이용
    => Queue는 인터페이스이고 Queue를 구현한 클래스들 중에는 PriorityQueue가 있는데 이 클래스는 데이터를 삽입

        할 때 오름차순 정렬을 해서 기억하고 있다가 데이터를 꺼낼때 오름차순 정렬한 결과로 리턴
    => 데이터를 삽입할 때는 add, 꺼낼때는 poll 메소드 사용

** Deque
    => 양쪽에서 삽입과 삭제가 가능한 자료구조
    => 스마트 폰의 테이블계열 뷰를 만들 때 사용
    => 자바에서는 인터페이스로 존재하고 ArrayDeque라는 클래스로 구현
    => 앞에 추가, 뒤에 추가하는 메소드, 앞, 뒤에서 꺼내는 메소드가 존재

** Stack, Queue, Deque 모두 중요!
  1) ArrayList -> 서버 프로그래밍에서 가장 중요
  2) LinkedList -> 응용프로그램에서 중요
  3) Queue -> 응용프로그램에서 중요
  4) Stack, Deque -> 자주 보기 어려움
  면접시, 1) ArrayList, LinkedList를 비교, 2) Stack, Queue의 기본 동작원리와 용도  

 

퀴즈!
1. 삽입정렬
    => 2번째부터 마지막 데이터까지 자신의 앞 데이터와 비교하면서 정렬

        30  34  27  33  29
1pass 30  34  27  33  29
2pass 27  30  34  33  29
3pass 27  30  33  34  29
4pass 27  29  30  33  34

2. 소수 찾기
    => 2부터 자신의 절반이 되는 숫자까지 한번도 나누어 떨어지지 않으면 소수