15일차 공부Collection, ArrayList, LinkedList, Stack

1~2 교시

 

Collection : 여러 개의 요소를 묶어서 하나의 객체로 만든 것

=> java.util. 패키지에 존재

=> Set(데이터의 순서를 유지하지 않는 데이터의 집합으로 중복을 허용하지 않음), List(순서가 있는 데이터의 집합으로 중복을 허용)의 상위 인터페이스

=> 컬렉션 인터페이스의 장점

 1) 자료구조나 알고리즘을 개발자가 구현할 필요가 없어 편리

 2) 일반 배열을 사용하지 않고 프레임워크가 제공해주는 컬렉션을 적절히 선택해서 사용하면 빠른 속도로 작업처리가능

 3) 통합된 API 구조로 효율성 증대

메소드

add(Object o), addAll(Collection c)

clear()

contains(Object o), containsAll(Collection c)

equals(Object o)

isEmpty()

iterator() : 이터레이터 반환

remove(Object o), removeAll(Collection c)

retainAll(Collection c): Collection에 포함된 데이터를 제외하고 삭제

size()

toArray(): Object 배열로 반환

데이터의 타입이 Object가 아니고 E, T, K, V로 되어 있으면 Generics가 적용된 것으로 인스턴스를 생성할 때 사용한 Generics 타입을 리턴

 

**List

=> 자료구조에서는 배열도 List로 분류한다.

=> java에서는 배열은 다른 종류로 구분

1. 종류

1) Array(배열 - 자료구조에서는 Dense List)

=> 동일한 자료형의 연속적인 모임

=> 크기가 고정 - 크기 변경이 안됨

=> 장점은 메모리 낭비가 없다.

=> 단점 데이터를 삽입하거나 삭제할 때 복사작업이 필요하다.

 

2) Vector(ArrayList)

=> 동일한 자료형의 연속적인 모임

=> 크기가 가변 - 크기 변경이 가능(여분의 공간을 확보)

=> 장점 데이터 접근 속도가 LinkedList보다는 빠르다

=> 단점 메모리 낭비가 발생할 수 있고 중간에 데이터를 삽입하거나 삭제할 때는 느리다.

=> 데이터베이스에서 데이터를 가져와서 사용할 때 많이 사용

 

3) Linked List

=> 동일한 자료형의 연속적인 모임 - 연속은 논리적인 개념

=> 크기가 가변 - 크기 변경이 가능(여분의 공간을 확보)

=> 데이터를 중간에 삽입하거나 삭제할 때 빠르게 작업, 연속된 빈 공간이 없어도 생성 가능

=> 메모리 장비가 발생할 수 있고 데이터 접근 속도가 느리다.

=> 응용 프로그램에서 데이터를 저장할 때 많이 사용

 

4) Stack

=> LIFO (Last In First Out) : 마지막에 삽입한 데이터가 첫번째로 출력되는 구조

=> push, pop으로 데이터를 삽입하고 삭제

=> 컴퓨터에서 연산을 처리할 때 IDE 들이 괄호 검사를 할 때 이용, 프로그램이 메소드를 호출할 때 메소드 마다 하나씩 생성해서 사용

 

5) Queue

=> FIFO (First In First Out) : 첫번째 삽입한 데이터가 첫번째로 출력되는 구조

=> 운영체제에서 명령어 저장(스케줄링), 그리고 공장 자동화 등에서 이용

 

6) Deque

=> 양쪽에 삽입과 삭제가 가능한 자료구조

=> 스마트 폰에서 List 계열의 뷰에서 이용

 

 

 

 3 교시

 

**java.util.ArrayList : 크기가 변하는 배열 클래스 - 예전 버전으로 Vector도 있음

• java.lang.Object
• • java.util.AbstractCollection<E>
  • • java.util.AbstractList<E>
    • • java.util.ArrayList<E>

=> 클래스 상속 계층

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccessDirect Known

=> 구현된 인터페이스

Cloneable : clone 메소드를 구현

Iterable : Iterable 메소드를 구현

 

Direct Known Subclasses:

AttributeList, RoleList, RoleUnresolvedList

=> ArrayList로부터 상속받은 클래스

 

1. 생성자

ArrayList<E>

ArrayList()

=> <E>는 제너릭이 적용된 클래스

 

생성할 때는

ArrayList<실제자료형> 변수명 = new ArrayList<실제자료형>();

=> 생성자에서 실제 자료형은 1.7버전부터는 생략이 가능

 

2. 메소드

void add(데이터)

void add(위치, 데이터)

=> Method Overloading : 메소드 이름은 같고 매개변수의 자료형이나 개수가 다른 경우

 

E get(int index): index 번째 데이터 가져오기

E remove(int index) : index 번째 데이터 지우기

E remove(E element) : element에 해당하는 데이터 지우기

 

int size() : 데이터 개수리턴

=> 데이터 전체 접근은 get과 size를 이용해서 가능하고 빠른 열거로도 가능

 

String toString() : 데이터 각각의 toString()을 호출해서 괄호로 묶어서 리턴

 

void sort(Comparator comparator) : 데이터를 comparator를 이용해서 비교한 후 정렬해주는 메소드

 

 

 

 

**java.util.LinkedList

=> 데이터를 논리적으로 연속해서 저장하는 List

=> 다음 데이터의 위치를 기억해서 다음 데이터에 접근하는 방식

=> ArrayList보다 데이터 접근 속도는 느리지만 데이터를 중간에 삽입하고 삭제하는 것은 편리

빨간부분만 LinkedList로 바구면 바낀다.

 

 

 

 

 

 

ArrayList 와 LinkedList의 중간 삽입 데이터 처리 속도를 비교해보자.

10만 번했을때의 시간차이

 

 

ArrayList 와 LinkedList 데이터 읽기 속도를 비교해보자.

삽입은 ArratList가 더 느리지만 데이터읽기는 ArrayList가 더 빠르다.

 

 

 

 

5 교시

 

**sort

=> 정렬을 할 때는 2개의 데이터를 크기 비교를 할 수 있는 메소드를 제공

자바에서는 이 메소드를 Comparator 인터페이스를 이용해서 구현하도록 강제한다.

메소드의 리턴값이 양수이면 2개의 위치를 변경하고 리턴값이 음수이면 위치를 그대로 둔다.

 

=> 데이터 정렬을 할 때는 오름차순과 내림차순 정렬을 해보고 개발자가 직접 만든 클래스의 인스턴스들을 가지고 정렬을 해봐야 한다.

 

오름차순

o1- o2를 하면 오름차순, o2 - o1으로 하면 내림차순이 된다.

list.sort(new Comparator에서 오류 두번나는건 import한번하고 다음에 add 클릭하면된다.

 

문자열 내림차순

return o2.compareTo(o1); 이렇게 작성하면 오름차순으로 정렬되서 위의 결과와 반대로 출력된다.

 

=> 여러 개의 데이터를 묶어서 하나의 행을 표현하기 위한 클래스 작성 순서

1. 각 속석을 저장할 프로퍼티를 private으로 생성

2. 인스턴스 생성을 위한 생성자를 작성 : 매개변수가 없는 생성자는 필수 constructor and superclass

3. 프로퍼티를 접근하기 위한 접근자 메소드  select all -> getter and setters

4. 디버깅(논리적오류나 예외해결) 을 위한 toString 메소드   toString

 

2.3.4.는 [Source] 메뉴를 이용해서 자동 생성

 

NFL 패싱 순위 정렬

 

 

** Stack

=> LIFO(Last In First Out) : 마지막에 삽입된 데이터가 먼저 출력되는 구조

1. 생성

Stack<데이터의자료형> 변수명 = new Stack<>();

 

2. 메소드

1) void push(데이터) : 데이터 삽입

2) 자료형 변수명 = pop() : 가장 마지막에 삽입된 데이터가 리턴되서 변수에 대입, 마지막 데이터는 삭제된다.

3) 자료형 변수명 = peek() : 가장 마지막에 삽입된 데이터가 리턴되서 변수에 대입, 마지막 데이터는 삭제되지 않는다.

 

=> 메모리 공간이 가득 찬 상태에서 push를 하게 되면 Overflow

데이터가 없는데 pop이나 peek를 하면 Underflow

 

3. 용도

=> 수식 계산

=> 문법체크 중 괄호 검사 - 코딩 테스트에서 많이 출제

=> 메소드의 지역변수 저장

 

 

 

**Queue

=> FIFO(First In First Out) : 먼저 삽입된 데이터가 먼저 출력되는 구조

=> 스케줄링 (명령어들을 저장해두었다가 순서대로 실행하는 것 - 공장 자동화 분야에 많이 이용)에 주로 이용

=> Queue는 인터페이스이고 Queue를 구현한 클래스 들 중에는 PriorityQueue가 있는데 이 클래스는 데이터를 삽입할 때 오름차순 정렬을 해서 기억하고 있다가 데이터를 꺼낼 대 오름차순 정렬한 결과로 리턴한다.

=> 데이터를 삽입할 대는 add, 꺼낼 때는 poll 메소드 사용

 

**Deque

=> 양쪽에서 삽입과 삭제가 가능한 자료구조

=> 스마트폰의 테이블 계열의 뷰를 만들 때 사용

=> 자바에서는 인터페이스로 존재하고 ArrayDeque라는 클래스로 구현

=> 앞에 추가하는 메소드와 뒤에 추가하는 그리고 앞에서 꺼내는 메소드의 뒤에서 꺼내는 메소드가 존재

 

** Stack, Queue, Deque 모두 중요한 자료구조인데 일반 응용프로그램을 만들 때는 Queue는 자주 사용하고 Stack이나 Deque 등은 자주 보기 어렵다.

프로그래밍을 할 때는 ArrayList(서버프로그래밍에서는 가장 중요), LinkedList(응용프로그램에서 중요), Queue(응용프로그램에서 중요)가 중요하고 면접을 볼 때는 ArrayList와 LinkedList의 비교와 Stack과 Queue의 기본 동작원리가 용도가 중요하다.

 

그냥 Queue와 다르게 PriorityQueue는 우선순위가 높은 데이터가 먼저 나온다.