11장. 컬렉션( ArrayList, LinkedList, Stack, Queue인터페이스 )

ArrayList

규칙
1. ArrayList ( 동기화처리 X )     <>     Vector ( 동기화처리 O )
2. List인터페이스를 구현하므로, 저장순서가 있고 중복 허용 한다.
3. 데이터의 저장공간으로 배열을 사용한다. (배열기반)

※ Collection은 인터페이스 
   Collections은 유틸 클래스

※ 기본 Vector의 기본소스   :       Object배열이기에 모든 종류의 객체 저장가능

---

ArrayList의 메서드

생성자

	코드	설명
1	ArrayList()	기본생성자
2	ArrayList(Collection c)	컬렉션 변환시 사용
3	ArrayList(int initialCapacity)	배열의 길이를 넣어줌

---

메서드(추가)

	코드	설명
1	boolean add(Object o)	ArrayList에 추가
2	void add(int index, Object element)	어디위치에 저장할지 index로 선택가능
3	boolean addAll(Collection c)	컬렉션을 주면 컬렉션의 요소를 저장
4	boolean addAll(int index, Collection c)	위치를 정하여, 컬렉션의 요소를  저장

---

메서드(삭제)

	코드	설명
1	boolean remove(Object o)	객체를 넣어주면, 삭제
2	Object remove(int index)	특정위치의 객체를 삭제
3	boolean removeAll(Collection c)	컬렉션을 지정해주면 컬렉션의 객체를 삭제
4	void clear()	ArrayList에 있는 모든 객체를 삭제

 

---

메서드(검색, 읽기, 변경)

	코드	설명
1	int index(Object o)	몇번째에 저장되어 있는지 검색, 못찾으면 -1 반환
2	int lastIndexOf(Object o)	← 순으로 객체 검색
3	boolean contains(Object o)	객체가 존재하는지 유무
4	Object get(int index)	객체 읽기
5	Object set(int index, Object element)	특정 index위치의 객체를 변경

---

메서드(기타)

	코드	설명
1	List subList(int fromInxex, int toIndex)	from ~ to 까지 일부 뽑아서, 새로운 List를 만듬
2	Object[] toArray()	ArrayList의 객체배열을 반환
3	Object[] toArray(Object[] a)	지정된 배열에 컬렉션의 객체를 저장해서 반환
4	boolean isEmpty()	ArrayList가 비어있는지 확인
5	void trimToSize()	ArrayList의 빈공간 제거
6	int size()	ArrayList의 저장된 객체의 개수를 반환

---

예시

public static void main(String[] args) {

		ArrayList list1 = new ArrayList(10);
		list1.add(3);
		list1.add(new Integer(0));
		list1.add(4);
		list1.add(new Integer(1));
		list1.add(5);
		list1.add(2);
		System.out.println("list1 : " + list1);
		
		ArrayList list2 = new ArrayList(list1.subList(1,4));
		System.out.println("list2 : " + list2);
		
		System.out.println("list1.containsAll(list2) : " + list1.containsAll(list2));
		
		list2.add("B");
		list2.add("C");
		list2.add(2,"A"); // index 2 위치에 추가
		System.out.println("list2 : " + list2);
		
		System.out.println("list1.indexOf(1) : " + list1.indexOf(1));
		
		list1.remove(new Integer(1));	// intger 1을삭제
		list1.remove(2);				// intex 2 위치 요소를 삭제
		System.out.println("list1 : " + list1);
		
		System.out.println("list1.retainAll(list2) : "+list1.retainAll(list2));
		// list1 에서 , list2의 요소와 겹치는 것만 남기고  나머지 list1의 요소들을 삭제
		System.out.println("list1 : " + list1);
		System.out.println("list2 : " + list2);
		
		System.out.println("______________________________");
		list1.add(3);
		list1.add(new Integer(0));
		list1.add(4);
		list1.add(new Integer(1));
		list1.add(5);
		list1.add(2);
		System.out.println("list1 : " + list1);
		System.out.println("list2 : " + list2);
		System.out.println("______________________________");
		for (int i = list2.size()-1; i>=0; i--) { // 7,6,5,4,3,2,1,0 = 이면 8개가 되어버리니
			if(list1.contains(list2.get(i)))	// list2 객체가 7개이니  .szie()-1 로 맞춤
				list2.remove(i);
		}
		System.out.println("list1 : " + list1);
		System.out.println("list2 : " + list2);
		//list2의 요소중에서 list1의 객체와 일치하는것은 삭제
	}

---

ArrayList에 저장된 객체의 삭제과정 

---

---

LinkedList - 배열의 장단점

배열의 단점 보완을 위해 태어남 LinkedList
배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link)

배열의 장점
1. 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간이 짧다.  (접근시간, access time)
   ㄴ 배열의 요소 접근 0x100 (배열의주소) + (n번째+1) * 4byte(데이터 타입의 크기)

배열의 단점 
1. 크기를 변경할수 없다. (실행중...)
   ㄴ 크기를 변경해야하는 경우 새로운 배열을 생성 후 데이터를 복사해야 한다.
         ( ① 더 큰배열생성.  ② 요소복사 ③ 참조변경 )
   ㄴ 크기 변경을 피하기위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨
2. 비순차적인 데이터의 추가, 삭제에  시간이 많이 걸린다.
    ㄴ 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함. (단,<순차> 끝에추가와 끝부터 삭제는 빠르다)

---

ArrayList (배열기반:연속)      vs     LinkedList (연결기반:불연속)     성능비교

	테스트	ArrayList 시간(ms)	LinkedList 시간(ms)	결과
1	순차  추가	606	406	ArrayList 빠름
2	비순차 삭제	11	46	ArrayList 빠름
3	중간 추가	7832	31	LinkedList 빠름
4	중간 삭제	6694	380	LinkedList 빠름
5	접근시간 테스트	1	432	ArrayList 빠름

---

스택 & 큐 (Stack & Queue)

스택 : LIFO구조. 마지막에 저장된 것을 먼저 꺼낸다. ( 배열에 적합 ) 
큐 : FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다. ( LinkedList에 적합 )

※ peek() 나오는 출구에서 본다고 생각

 

 

Stack의 메서드

	메서드	설명
1	boolean empty()	Stack이 비어있는지 확인
2	Object peek()	맨위 객체 읽기만.
3	Object pop()	삭제. 비어있다면 EmptyStackException 예외발생
4	Object push(Object item)	저장.
5	int search(Object o)	객체를 검색하여 위치를 반환. 못찾으면 -1반환 (배열과 달리 1부터 시작)

---

Queue의 메서드

	메서드	설명
1	boolean isEmpty()	객체 비어있는지 확인
2	boolean add(Object o)	저장. 저장공간 부족시 IllegaStateException 예외발생
3	Object remove()	삭제. 비어있다면 NoSuchElementException 예외발생
4	Object element()	삭제없이 읽기. 비어있으면 예외발생 (예외 설정시사용)
5	Object poll()	삭제. 비어있으면 null반환.
6	Object peek()	맨아래 객체 읽기,  비어있으면 null반환.
	Object offer()	저장. 공간이없으면 null을 반환

 

---

큐 (Queue)

큐(Queue)는 인터페이스 이다.
1. 직접구현
2. 큐를 구현한 클래스를 사용 ( Java API 에있음 )

 

java API를 통하여 큐를 구현한 클래스중 골라서 사용. ( 익숙한 LinkedList 확인 )

---

스택 & 큐 (Stack & Queue)의 활용

---

Stack예제 ( 괄호가 짝수면 맞음, 닫는괄호가 모자라면 틀림, 

public static void main(String[] args) {
		
		Stack stack = new Stack();
		String expression = "((3+5)*8-2)";	 
		
		System.out.println("expression : " + expression);
		
		try {
			for (int i = 0; i < expression.length(); i++) {
				char ch = expression.charAt(i);
				
				if(ch == '(') {
					stack.push(ch+"");
				}else if( ch == ')') {
					stack.pop();
				}  
			}
			
			if(stack.isEmpty()) {
				System.out.println("괄호 개수가 맞습니다.");
			}else {
				System.out.println("괄후 개수가 틀립니다.");
			}
		}catch (EmptyStackException e) {
			System.out.println("꺼낼 괄호가 없습니다.");
		}
        
        
// _________________________실행결과_________________________		
//		expression : ((3+5)*8-2)
//		괄호 개수가 맞습니다.

---

Queue 인터페이스 사용을 위해, LinkedList구현 예제

public class ex11_4 { // 최근 5개 명령어 이력 보여주기
	static Queue queue = new LinkedList();
	static final int MAX_SIZE = 5; // Queue에 최대 5개 까지만 저장되도록

	public static void main(String[] args) {
		System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");
		while (true) {
			System.out.print(">>> ");
			try {
				Scanner scan = new Scanner(System.in);
				String input = scan.nextLine().trim(); // 화면으로부터 라인단위로 입력받는다.

				if ("".contentEquals(input))
					continue; // continue면 아래 다 건너띄고 다시 while 처음으로 ~

				if (input.equalsIgnoreCase("q")) {
					System.exit(0); // 프로그램 종료

				} else if (input.equalsIgnoreCase("help")) {
					System.out.println(" help : 도움말을 보여줍니다.");
					System.out.println(" q 또는 Q : 프로그램을 종료합니다.");
					System.out.println(" history : 최근에 입력한 명령어를 " + MAX_SIZE + "개 보여줍니다.");

				} else if (input.equalsIgnoreCase("history")) {
					save(input); // 입력받은 명령어를 저장 후, linkedList의 내용을 보여준다.
					LinkedList list = (LinkedList) queue;

					for (int i = 0; i < list.size(); i++) {
						System.out.println((i + 1) + "." + list.get(i));
					}
				} else {
					save(input);
					System.out.println(input);
				}
			} catch (Exception e) {
			}
		} // while
	}// main

	public static void save(String input) {
		if (!"".equals(input)) { // queue에 저장한다.
			queue.offer(input);
		}
		// queue의 최대크기를 넘으면 제일 처음 입력됫 것을 삭제한다.
		if (queue.size() > MAX_SIZE)
			queue.remove();
	}
}


//_________________________실행결과_________________________	
//help를 입력하면 도움말을 볼 수 있습니다.
//>>> 테스트
//테스트
//>>> 테스트1
//테스트1
//>>> 테스트2
//테스트2
//>>> 테스트3
//테스트3
//>>> 테스트4
//테스트4
//>>> history
//1.테스트1
//2.테스트2
//3.테스트3
//4.테스트4
//5.history
//>>>

 

 

---

Java API 소스 보기 4가지?

1. /JDK 설치경로/src.zip

2. 이클립스에서 해당 API, 컨트롤 + 왼쪽마우스 클릭

3. 이클립스에서 해당 API, F3 키보드

4. 이클립스에서 해당 API, 우클릭 open Declaration

---

출처 : 남궁성의 정석코딩

https://www.youtube.com/@MasterNKS