[java][이론]014 컬렉션 프레임웍_List

14 컬렉션 프레임웍_List

1.     ArrayList

○ 데이터 저장순서 유지되고 중복 허용

○ Object배열을 이용해 데이터를 순차적으로 저장

○ 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 함

■ remove로 삭제 시 for구문으로 접근하게 되면 접근 변수를 뒤에서부터 감소시켜 역방향으로 지워야 됨

■ 자리이동 발생해도 영향 받지 않도록 해야 함

○ ArrayList 생성 시 저장 요소 개수 고려하여 실제 저장할 개수보다 약간 여유 있게 해야 함

■ 생성할 때 지정한 크기보다 더 많이 저장하면 크기가 늘어나지만 시간이 많이 걸림

■ 기존 ArrayList를 복사하고 새 ArrayList 생성해 복붙하고 새 객체 넣고 그렇게 되므로 ㅜ

○ ArrayList나 Vector 같은 것들은 배열을 이용한 자료구조

■ 읽고 저장하는 데, 임의 접근 하는 데는 효율이 좋음

■ 새로 생성된 배열로 데이터 복사하면서 크기를 늘리므로 비효율적

 

2.     LinkedList

○ 배열 이용한 구조의 단점

(1)   크기를 변경할 수 없음

(2)   비순차적인 데이터 추가 또는 삭제에 시간이 많이 걸림

○ 배열 단점 보완하는 LinkedList

■ 배열은 모든 데이터가 연속적으로 존재함

■ 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태

■ 링크드 리스트의 각 요소들은 자신과 연결된 다음 요소에 대한 참조와 데이터로 구성

class Node{

Node next;

Object obj;

}

■ 삭제!

□ 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 됨

□ 배열처럼 데이터 이동 위해 복사하는 과정이 없어 처리속도 빠름

■ 추가

□ 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경하고, 새로운 요소가 그 다음요소 참조하도록 함

■ 단 방향이므로 이전요소에 대한 접근은 어려움

 

○ Doubly Linked List & Doubly circular Linked List

■ Doubly Linked List

□ 링크드 리스트에 이전 요소에 대한 참조를 하는 참조변수 하나 더 추가

□ LinkedList는 더블 링크드 리스트로 구성됨 -> 낮은 접근성을 높임

□ 각 요소에 대한 접근이 조금 더 쉬움

class Node{

Node next;

Node previous;

Object obj;

}

■ Doubly circular Linked List

□ 더블 링크드 리스트의 첫 번째 요소와 마지막 요소가 서로를 가리키는 것

□ 맨 앞과 맨 뒤를 연결하여 순환하는 자료구조

 

○ ArrayList와 LinkedList 비교

 

 

■ 다루고자 하는 데이터의 개수가 변하지 않는다면 ArrayList가 나을 것

■ 데이터 개수 변경이 잦다면 LinkedList가 나을 수도

■ 두 클래스를 조합하여 사용하는 것도 좋음

처음 작업 전 데이터 저장에는 ArrayList 사용하다가 작업할 때 LinkedList로 옮겨서 추가 삭제 작업 하면 됨

컬렉션 프레임워크는 서로 변환 가능한 생성자 제공하므로 가능함

ArrayList aList = new ArrayList();

LinkedList lList = new LinkedList(aList);

이런 식

 

1.     Stack & Queue

1)    Stack

■ 순차적으로 데이터를 추가하고 삭제

■ ArrayList같은 배열 기반 컬렉션이 적합

■ Last In First Out

■ 수식 계산, 수식 괄호 검사, 워드프로세스의 undo/redo, 웹 브라우저의 뒤로/앞으로

2) Queue

■ 데이터 꺼낼 때 항상 첫 번째 데이터 삭제하므로 LinkedList로 구현하는 것이 적합

■ First In First Out

■ 최근사용문서, 인쇄작업 대기목록, 버퍼

3) PriorityQueue

■ 저장한 순서에 관계 없이 우선순위가 높은 것부터 꺼내는 것

■ null 저장 불가능

■ 저장공간으로 배열 사용하고, 각 요소를 힙(이진트리의 일종 부모 자식간 대소차이가 있음)이라는 자료구조로 저장

■ 숫자 뿐 아니라 객체를 저장할 수 있으며 객체 대소 비교 방식 지정해줘야 함

4) Deque

■ queue의 변형

■ 양 쪽 끝으로 추가 삭제 가능한 자료구조

■ 구현은 ArrayList, LinkedList로 구현 가능

 

2.     Iterator, ListIterator, Enumeration

○ 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스

○ 접근하는 방법의 표준화

1)    Iterator

■ 컬렉션에 저장된 요소들을 읽어오는 방법의 표준화

■ Iterator(Iterator를 구현한 클래스의 인스턴스)를 반환하는 iterator() 메서드 정의 되어있음

■ 컬렉션 클래스에 대해 iterator() 호출 -> Iterator 얻음 -> while 문이나 반복문으로 컬렉션 클래스의 요소를 읽어옴 (읽어 올 것이 있는지 확인해야 됨)

■ 표준화! 이므로 다형성을 위해 참조변수의 참조형은 List로 하고 생성되는 실 인스턴스는 자식 클래스로 생성하면 다양한 컬렉션끼리 호환도 되므로, 그렇게 쓰자

■ Map 인터페이스 구현한 컬렉션 클래스는 key와 value값을 쌍으로 저장하므로 iterator() 직접 호출 불가능

keyset()이나 entrySet()과 같은 메서드들로 키와 값을 각각 따로 Set 형태로 얻어와 그 set에 iterator() 호출하여 Iterator 얻음

Map map = new HashMap();

List mvList = map.entrySet().iterator();

List mkList = map.keySet().iterator();

 

■ List 클래스들은 저장 순서 유지하기 때문에 Iterator 이용해 읽어온 결과도 저장 순서와 동일

Set 클래스들은 저장 순서 유지 안 하므로 Iterator도 저장 순서와 같지 않음

 

2)    ListIterator & Enumeration

■ ListIterator : Iterator에 양방향 조회기능 추가(List 구현한 경우만 사용 가능)

■ Enumeration : Iterator의 구버젼

■ 둘 다 뒤(앞)에 읽어올 것 있는지 has… 메서드로 확인해야 함

 

3.     Arrays

○ 배열을 다루는 데 유용한 메서드가 정의되어 있는 클래스

1)    배열의 복사

■ copyOf() : 배열 전체 복사

■ copyOfRange() : 베열 일부 복사해 반환. 범위의 끝은 포함X

2)    배열 채우기

■ fill() : 배열 모든 요소를 지정된 값으로 채움

■ setAll() : 배열 채우는데 사용할 함수형 인터페이스를 매개변수로 받음

함수형 인터페이스를 구현한 객체를 매개변수로 지정하던가 람다식으로 지정해야 함

Arrays.setAll(arr, ()->(int) (Math.random()*5)+1);

3)    배열의 정렬과 검색

■ sort() : 배열 정열할 때 사용

■ binerySearch() : 배열에 지정된 값이 저장된 위치 찾아서 반환. 배열이 정렬된 상태에서만 가능

이진검색! : 배열 검색 범위를 반복적으로 죽여가며 검색하므로 빠르지만 정렬이 필요

4)    문자열 비교와 출력

■ 출력

□ toString() : 일차원 배열에서 사용

□ deepToString() : 다차원 배열에서 사용. 모든 요소를 재귀적으로 접근해 구성

■ 비교

□ equals() : 일차원 배열에서 사용 가능

□ deepEquals() : 다차원 배열 비교

다차원 배열에서 equals() 사용하면 배열에 저장된 배열 주소를 비교하게 됨

5)    배열을 List로 변환

■ asList() : 배열을 List에 담아 반환

매개변수 타입이 가변인수라 배열 생성 없이 저장할 요소들만 나열하는 것도 가능

■ asList() 가 반환한 List의 크기를 변경할 수 없으므로 새 리스트 생성해서 반환된 리스트 넣어 새로 생성

List list = new ArrayList(Arrays.asList(1,2,3,4,5));

6)    parallelXXX(), spliterator(), stream()

■ parallel로 시작하는 메서드들 : 여러 쓰레드가 작업을 나누어 처리하도록 함

■ spliterator() : 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator 반환

■ stream() : 컬렉션을 스트림으로 변환

 

4.     Comparator & Comparable

○ Arrays.sort() 호출 시 정렬된 것은 Charater클래스가 Comparable 구현해서 가능한 것(equals()도)

○ Comparable & Comparator

■ Comparable : 기본 정렬 기준을 구현하는 데 사용

compareTo() 메서드가 정의되어 있음

Comparable인터페이스!

이 것을 구현한 클래스들은 기본적으로 오름차순으로 정렬

이 것을 구현한 클래스들의 객체를 비교하는 것은 sort로 바로 정렬, 비교 가능

■ Comparator : 기본 정렬 기준 외에 다른 기준으로 정렬하고자 할 때 사용

compare() 메서드를 제정의하여 사용

Comparable 구현한 클래스 아니라면 정렬비교 기준이 없으니 Comparator을 만들어 기준을 만들어 준다는 느낌

Comparator의 compare() 메서드를 오버라이딩 -> Comparable의 객체를 생성해 그 객체에 있는 compareTo()메서드 사용하여 compare()을 재정의!

■ Arrays.sort() 메서드는 배열 정렬 시 Comparator 지정하지 않으면 기본 저장하는 객체에 구현된(Comparable 구현한 객체) 내용에 따라 정렬됨

static void sort(Object[] a) // 객체 배열에 저장된 객체가 구현한 Comparable에 의한 정렬

static void sort(Object[] a, Comparator c) // 지정한 Comparator에 의한 정렬

■ 대소문자 구분 없는 Comparator : 상수 형태로 제공됨

String.CASE_INSENSTIVE_ORDER을 컴퍼레이터 자리에 넣으면 됨

■ 내림차순 구현

String에 구현된 compareTo() 결과에 *-1 해주거나

비교하는 객체의 위치를 바꿔서 뒤에 있는 애와 앞의 애 자리 바꿔 compareTo써주면 됨