for (int i = list.size() - 1; i >= 0; i--) { list.remove(i);}
마지막 객체부터 삭제해야 성능 향상 + 전체 삭제 가능
Array 와 List 의 차이
// 배열 - 추가, 삭제가 어렵다. 직접 구현해야한다.int[] numbers = {10,20,30,40,50};// 리스트 (ArrayList)ArrayList numbers = new ArrayList();numbers.add(10); // 추가numbers.remove(0); // 삭제// 리스트 (LinkedList)LinkedList numbers = new LinkedList();numbers.add(10); // 추가numbers.remove(0); // 삭제
Array
선언과 동시에 크기가 고정되며, 기능이 없음
배열은 인덱스에 따라서 값을 유지하기 때문에 null 값이 남게 됨 (메모리 낭비)
데이터의 갯수가 정해져 있고 자주 사용할 경우 Array 가 더 효율적
List
순서가 있는 데이터의 모임 (Sequence 라고도 부름)
가변길이의 특성을 갖고 있으며 다양한 기능을 내장하고 있음
Array List 와 Linked List 두가지가 존재함
12~14. LinkedList
배열의 장단점
장점
배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근 시간, access time)이 짧음
단점
크기를 변경할 수 없음크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함
크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리 낭비
비순차적인 데이터의 추가, 삭제에 시간이 많이 걸림
데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함
그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠름
배열의 단점을 보완
배열과 달리 LinkedList 는 불연속적으로 존재하는 데이터를 연결
데이터의 삭제 : 단 한 번의 참조변경만으로 가능
각 데이터가 노드로써 서로를 연결하고 있음
class Node { Node next; // 다음 데이터의 주소 Object obj; // 데이터}
데이터의 추가 : 한번의 Node 객체 생성과 두 번의 참조변경만으로 가능
이중 연결 리스트
LinkedList - 연결리스트. 데이터 접근성이 나쁨
Doubly Linked List - 이중 연결리스트. 접근성 향상
class Node { Node next; // 다음 데이터의 주소 Node prvious; // 이전 데이터의 주소 Object obj; // 데이터}
Doubly Circular Linked List - 이중 원형 연결리스트
이중 연결리스트에서 첫 번째 노드와 마지막 노드를 연결한 구조
ArrayList vs LinkedList - 성능 비교
순차적 데이터 추가/삭제 - ArrayList가 빠름
비순차적 데이터 추가/삭제 - LinkedList가 빠름
접근시간(access time) - ArrayList가 빠름
15~18. Stack과 Queue
Stack : LIFO(Last In First Out) 구조. 마지막에 저장된 것을 제일 먼저 꺼냄 (배열)
Queue : FIFO(First In First Out) 구조. 제일 먼저 저장한 것을 제일 먼저 꺼냄 (링크드 리스트)
Stack
Stack st = new Stack(); // 객체 생성 후 사용 가능// Stack이 비어있는지 확인boolean empty()// 맨 위에 있는 객체를 반환Object peek()// 맨 위에 있는 객체를 꺼냄Object pop()// Stack에 객체 저장Object push(Object item)// Stack 에 주어진 객체를 찾아서 위치를 반환 (맨 위에서 1, 2, 3 순으로)int search(Object o)
Queue
Queue 는 인터페이스이기 때문에 직접구현 혹은 Queue 를 구현한 클래스를 사용Queue q = new LinkedList(); // 이후 사용 가능// Queue에 객체 추가. 성공하면 true 반환. 저장공간 부족 시 IllegalStateException 발생boolean add(Object o)// Queue에서 객체를 꺼냄. 비어있으면 NoSuchElementException 발생Object remove()// 삭제없이 요소를 읽음. peek과 달리 비어있으면 NoSuchElementException 발생Object element()// Queue에 객체 추가. 성공하면 true 반환boolean offer(Object o)// Queue에서 객체를 꺼냄. 비어있으면 null 반환Object poll()// 삭제없이 요소를 읽음. 비어있으면 null 반환Object peek()
19~21. Stack과 Queue의 활용
Stack 활용의 예
수식계산
수식괄호검사
워드프로세서의 undo/redo
웹브라우저의 뒤로/앞으로
Queue 활용의 예
최근사용문서
인쇄작업 대기목록
버퍼
22~24. Iterator, Enumeration, Map
개요
컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스
Enumeration 은 Iterator 의 구버전 (잘안씀)
ListIterator 는 Iterator 의 접근성을 향상 (단방향 → 양방향) (잘안씀)
// 읽어 올 요소가 남아있는지 확인boolean hasNext()// 다음 요소를 읽어 옴Object next()
개념
컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것
List, Set, Map 모두 읽어오는 방법이 다르기 때문에 위와 같은 인터페이스를 사용
사용법
컬렉션에 iterator()를 호출해서 iterator를 구현한 객체를 얻어서 사용
List list = new ArrayList();Iterator it = list.iterator();while (it.hasNext()) { // 읽어 올 요소가 있는지 확인 System.out.println(it.next()); // 다음 요소를 읽어옴}
Map과 Iterator
Map에는 iterator()가 없다.
Map은 Collection의 자손이 아님
keySet(), entrySet(), values()를 호출해야 함
Map map = new HashMap();Iterator it = map.entrySet().iterator();
25~29. Arrays
Arrays - 배열을 다루기 편리한 메서드(static) 제공
배열의 출력
int[] arr = {1,2,3,4,5};String list = Arrays.toString(arr); // [1,2,3,4,5] 반환
String[][] str2D = new String[][]{{"aaa","bbb"},{"AAA","BBB"}};String[][] str2D2 = new String[][]{{"aaa","bbb"},{"AAA","BBB"}};System.out.println(Arrays.equals(str2D, str2D2)); // falseSystem.out.println(Arrays.deepEquals(str2D, str2D2)); // true
배열을 List로 변환
List list = Arrays.asList(new Integer[]{1,2,3,4,5}); // list = [1,2,3,4,5]List list = Arrays.asList(1,2,3,4,5); // list = [1,2,3,4,5]list.add(6) // UnsupportedOperationException 예외 발생. 읽기 전용이기 때문에List list = new ArrayList(Arrays.asList(1,2,3,4,5)); // 새로운 ArrayList. 변경가능
30~33. Comparator와 Comparable
객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스
Comparable 기본 정렬기준을 구현하는데 사용
Comparator 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용
public interface Comparable { // o1, o2 두 객체를 비교 int compareTo(Object o); // 주어진 객체(o)를 자신과 비교}public interface Comparator { int compare(Object o1, Object o2); // o1, o2 두 객체를 비교 boolean equals(Object obj); // equals를 오버라이딩하라는 뜻}
compare()와 compareTo()는 두 객체의 비교결과를 반환하도록 작성
public final class Integer extends Number implements Comparable { ... public int compareTo(Integer anotherInteger) { int v1 = this.value; int v2 = anotherInteger.value; // 같으면 0, 우측이 크면 -1, 좌측이 크면 1 반환 return (v1 < v2 ? -1 : (v1==v2? 0 : 1)); }}
Integer와 Comparable
public final class Integer extends Number implements Comparable { ... public int compareTo(Object o) { return compareTo((Integer)o); } public int compareTo(Integer anotherInteger) { int thisValue = this.value; int anotherValue = anotherInteger.value; // 같으면 0, 비교대상이 크면 -1, 자신이 크면 1 반환 return (thisValue < anotherValue ? -1 : (thisValue ==anotherValue ? 0 : 1)); }}
34~38. HashSet
HashSet
Set 인터페이스를 구현한 대표적인 컬렉션 클래스
순서를 유지하려면, LinkedHashSet 클래스를 사용
TreeSet
범위 검색과 정렬에 유리한 컬렉션 클래스
HashSet 보다 데이터 추가, 삭제에 시간이 더 걸림
HashSet - 주요 메서드
// 생성자HashSet()HashSet(Collection c)HashSet(int initialCapacity) // 초기용량 설정HashSet(int initialCapacity, float loadFactor) // 언제 용량을 늘릴건지// 추가boolean add(Object o)boolean addAll(Collection c) // 합집합// 삭제boolean remove(Object o)boolean removeAll(Collection c) // 교집합// 모두삭제void clear()// 조건부삭제boolean retainAll(Collection c) // 차집합// 포함 여부 확인boolean contains(Object o)boolean containsAll(Collection c) // 여러 객체를 모두 포함하는지// 비었는지 확인boolean isEmpty()// 저장된 객체 수 확인int size()// 객체배열로 반환Object[] toArray()Object[] toArray(Object[] a)
HashSet - 예제 3
HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인
같은 객체가 없으면 저장, 있으면 저장 X
boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출
equals()와 hashCode()가 오버라이딩 되어 있어야 함
public boolean equals(Object o) { if (!(obj instanceof Person)) { return false; } Person tmp = (Person)obj; return name.equals(tmp.name) && age==tmp.age;}public int hashCode() { return Objects.hash(name, age);}
39~45. TreeSet
TreeSet - 범위 탐색, 정렬
이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리.
이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
각 노드가 트리 형태로 연결 (LinkedList의 변형)
이진 탐색 트리(binary search tree)
부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
데이터가 많아질수록 추가, 삭제에 시간이 더 걸림 (비교 횟수 증가)
TreeSet - 데이터 저장과정 boolean add(Object o)
TreeSet 에 7,4,9,1,5 의 순서로 데이터를 저장할 때
TreeSet - 주요 생성자와 메서드
// 생성자TreeSet()HashSet(Collection c)TreeSet(Comparator comp) // 주어진 정렬기준으로 정렬하는 TreeSet 생성Object first() // 정렬된 순서에서 첫번째 객체 반환Object last() // 정렬된 순서에서 마지막 객체 반환Object ceiling(Object o) // 지정된 객체와 같은 객체를 반환. 없으면 가장 가까운 큰 값 반환Object floor(Object o) // 지정된 객체와 같은 객체를 반환. 없으면 가장 가까운 작은 값 반환Object higher(Object o) // 지정된 객체보다 큰 가장 가까운 값 반환Object lower(Object o) // 지정된 객체보다 작은 가장 가까운 값 반환SortedSet subSet(Object fromElement, Object toElement) // 범위 검색의 결과 반환SortedSet headSet(Object toElement) // 지정된 객체보다 작은 객체들SortedSet tailSet(Object fromElement) // 지정된 객체보다 큰 객체들
46~51. HashMap
HashMap과 Hashtable - 순서 X, 중복(키 X, 값 O)
Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장
HashMap(동기화 X)은 Hashtable(동기화O)의 신버전
HashMap
Map 인터페이스를 구현한 대표적인 컬렉션 클래스
순서를 유지하려면 LinkedHashMap 클래스 사용
TreeMap
범위 검색과 정렬에 유리한 컬렉션 클래스
HashMap 보다 데이터 추가, 삭제에 시간이 더 걸림
HashMap의 키(key)와 값(value)
해싱(hashing) 기법으로 데이터를 저장. 데이터가 많아도 검색이 빠름
Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { transient Entry[] table; ... static class Entry implements Map.Entry { final Object key; Object value; ... }}
해싱(hashing)
해시함수(hash function)로 해시테이블(hash table)에 데이터를 저장, 검색
