java #10 LinkedList , ArrayList , Stack , Queue , Iterator

1. LinkedList
1) 배열의 장점: 배열을 구조가 간단하고 데이터를 읽는데 걸리는 시간(접근시간 , access time)이 짧다.

2) 배열의 단점
a. 크기를 변경할 수 없다
- 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함
- 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.
b. 비순차적(중간)인 데이터의 추가, 삭제에 시간이 많이 걸린다 (자리를 옮기도록 되어있기 때문에)
- 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함
- 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

3) 배열의 단점을 보완 - LinkedList
a. 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)
- 데이터의 삭제: 단 한번의 참조 변경만으로 가능
- 데이터의 추가: 한번의 Node객체 생성과 두 번의 참조 변경만으로 가능

4) LinkedList 단점
a. 데이터 접근성이 나쁨(한번에 가는 게 아니라 건너 건너가야 됨)
b. 링크드 리스트의 단점을 보완해서 나온 것이 더블리 링크드 리스트 - 이중 연결 리스트, 접근성 향상 but 한 번에 이동은 불가, 앞 뒤로 이동 편리해짐
c. 더블리 써큘러 링크드 리스트 - 이중 원형 연결리스트 : 처음과 끝이 연결되어있음

5) ArrayList vs. LinkedList -  성능 비교
a. 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름
b. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
c. 접근시간(access time) - ArrayList가 빠름 (읽기)

2. 스택과 큐(Stack and Queue)
1) 스택과 큐(Stack and Queue)
a. Stack : LIFO(Last In First Out)구조. 마지막에 저장된 것을 제인 먼저 꺼내게 된다. (배열)
b. Queue : FIFO(First In First Out)구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다. (링크드 리스트), offer(저장), poll(추출)
c. 스택은 클래스라 객체 생성이 되지만 큐는 인터페이스이기 때문에 객체 생성이 안됨 but 큐를 구현한 클래스를 사용 
ex) Queue q = new LinkedList(); // Queue로 쓰는 것이 좋음 LinkedList자리에 다른 클래스로 바뀌어도 다 큐를 사용하기 때문에 공통으로 사용 가능
     q.offer(0);

2) 스택과 큐의 활용
a. 스틱의 활용 예 - 수식계산, 수식괄호 검사, 워드프로세서의 undo/redo, 웹 브라우저의 뒤로/앞으로
b. 큐의 활용 예 - 최근사용문서, 인쇄 작업 대기목록, 버퍼(buffer)

3. Iterator, Listiterator, Enumeration
1) Iterator, Listiterator, Enumeration
a. 컬렉션에 저장된 데이터를 접근(읽어오기)하는데 사용되는 인터페이스
b. Iterator의 인터페이스의 메서드
   boolean hasNext() : 읽어 올 요소가 남아있는지 확인한다. 있으면 ture, 없으면 false을 반환한다.
   Object next() : 다음 요소를 읽어 온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전하다.
c. Enumeration은 Iterator의 구버전
d. Enumeration 인터페이스의 메서드
   boolean hasMoreElements() : 읽어 올 요소가 남아있는지 확인하다. 있으면 true, 없으면 false를 반환한다. hasNext()와 같음
   Object nextElement() : 다음 요소를 읽어온다. next()와 같음 
e. ListIterator는 Iterator의 접근성을 향상한 것 (단방향 -> 양방향) 잘안씀
f. Iterator : 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것
              컬렉션에 Iterator()를 호출해서 Iterator를 구현한 객체를 얻어서 사용

 

import java.util.*;


public class IteratorEx {

	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);
		
		Iterator it = list.iterator();
		
		while(it.hasNext()) {
			Object obj = it.next();
			System.out.println(obj);
			
		}
			//iterator는 1회용이라 다쓰고 나면 다시 얻어와야 한다.
			it = list.iterator(); // 새로운 iterator객체를 얻는다.
			while(it.hasNext()) {
				Object obj = it.next();
				System.out.println(obj);
			}


				// for(int i= 0; i<list.size(); i++) {  // 위의 코드와 같은 결과 출력
				// Object obj = it.next();
				// System.out.println(obj);
			}
		}

	}

 

3) Map과 Iterator
a. Map에는 iterator()가 없다. keySet(). entrySet(). values()를 호출해야
ex) Map map = new HashMap();
    Iterator it = map entrySet().iterator(); -> Set eSet = map.entrySet(); Iterator it = eSet.iterator();

4. Arrays - 배열을 다루기 편리한 메서드(static) 제공
1) 배열의 출력 - toString()
ex) static String toString(boolean[] a)

2) 배열의 복사 - copyOf(), copyOfRange()
ex) int[] arr = {0,1,2,3,4};
    int[] arr2 = Arrays.copyOf(arr, arr.length); // arr2 = [0,1,2,3,4]
    int[] arr4 = Arrays.copyOf(arr,7); // arr4 = [0,1,2,3,4,0,0]
    int[] arr5 = Arrays.copyOfRange(arr, 2, 4); // arr5 = [2,3] // from ~ to 인데 항상 from은 포함이고 to는 포함이 아님!! 주의할 것
    int[] arr6 = Arrays.copyOfRange(arr, 0, 7); // arr6 = [0,1,2,3,4,0,0]

3) 배열 채우기 -fill() , setAll()
ex) int[] arr = new int[5]
    Arrays.fill(arr, 9); // arr = [9,9,9,9,9]
    Arrays.setAll(arr, (i) -> (int)(Math.random()*5+1); // ar = [1,5,2,1,1] // 람다식 랜덤값

4) 배열의 정렬과 검색 - sort(), binarySearch()
ex) int[] ar = {3,2,0,1,4};
    int idx = Arrays.binarySearch(arr,2); // idx = -5 잘못된 결과 (이진 탐색을 정렬되어 있을 때만 사용, 정렬이 되어있지 않을 때 사용하면 잘못된 결과가 나옴)
    Arrays.sort(arr); // 배열을 정렬한다.
    System.out.println(Arrays.toString(arr)); // [0,1,2,3,4] // [0,1,2,3,4]
    int idx = Arrays.binarySearch(arr, 2); // idx = 2 올바른 결과

5) 다차원 배열의 출력 - deepToString() : 1차원 배열 출력은 toString , 2차원 배열 출력은 deeptoString

6) 다차원 배열의 비교 - deepEquals()  

7) 배열을 List로 변환 - asList(Object... a)
ex) List list = Arrays.asList(1,2,3,4,5) // list = [1,2,3,4,5]
     list.add(6) // 예외 발생 List list가 읽기전용이기 때문에 추가를 지원하지 않음
     List list = new ArrayList(Arrays.asList(1,2,3,4,5)); // 추가하려면 이 코드처럼 새로운 ArrayList를 생성 그리고 변경가능!!    

8) Comparator와 Compable 
a. 객체를 정렬하는데 필요한 메서드를 정희한 인터페이스 (정렬기준을 제공)
- Comparable 기본 정렬기준을 구현하는데 사용.
- Comparator 기본 정렬기준 외에 다른 기준으로 정렬하고자 할 때 사용

 

 public interface Comparator {
	int compare(Object o1, Object o2);
	boolean equlas(Object obj); // o1, o2 두 객체를 비교 equals를 오버라이딩하라는 뜻
}
    public interface Comparable {
	int compareTo (Object o); // 주어진 객체(o)를 자신과 비교
}

 import java.util.Arrays;
import java.util.Comparator;

public class ComparatorEx {

	public static void main(String[] args) {
		String[] strArr = {"cat","Dog","lion","tiger"};
		
		Arrays.sort(strArr); // String의 Comparable 구현에 의한 정렬
		System.out.println("strArr =" + Arrays.toString(strArr));
		Arrays.parallelSort(strArr,String.CASE_INSENSITIVE_ORDER); // 대소문자 구분안함
		System.out.println("strArr =" + Arrays.toString(strArr));
		
		Arrays.sort(strArr,new Descending()); // 역순 정렬
		System.out.println("strArr =" + Arrays.toString(strArr));

	}
}
class Descending implements Comparator {
	public int compare(Object o1, Object o2) {
		if( o1 instanceof Comparable && o2 instanceof Comparable) {
		Comparable c1 = (Comparable)o1;
		Comparable c2 = (Comparable)o2;
		return c1.compareTo(c2) * -1; // 기본 정렬 기준에 -1을 곱해서 기본 정렬방식의 역으로 변경한다.
	}									// 또는 c2.compareTo(c1)와 같이 순서를 바꿔도 된다.
	return -1;
   }
}