ArrayList,LinkedList,lterator

ArrayList

 

저장순서가 유지되고 중복을 허용합니다 vector를 개선하는 것으로 

 

• ArrayList는 Object배열 을 이용해서 데이터를 순차적으로 저장합니다. 
• ArrayList는 일반 배열과 똑같습니다.
• vector와 다르게 ArrayList는 비동기화 입니다.
• ArrayList는 객체만 저장가능합니다
• Autoboxing에 의해 기본형이 참조형으로 자동 형변환이 가능합니다.

 

 

장점 

 

ArrayList 최고 장점은 구조가 간단하고 데이터를 읽는데 걸리는시간이 짧습니다

 

 

단점

 

• 실행중 크기를 변경할 수 없습니다 새로운 배열을 생성해서 데이터를 복사해야합니다 충분히 큰크기의 배열을 생성해야하므로 메모리 낭비가 됩니다.
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸립니다    배열의 중간에 데이터를 추가하려면 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 합니다.

 

 

 

 

 

 

 

public class ArrayList extends AbstractList
implements List, RandomAccess,Cloneable,Java.io.Serializable {
    ...
      transient Objects[] elementData;//Object배열   , 객체 배열 ,다형성 ,모든종류의 객체 저장
}

 

 

 

 

LinkedList

배열의 단점을 보완하기 위해서 링크드 리스트 라는 자료구조를 고안 했습니다.

 

장점

중간 리스트의 정보를 수정하기 정말 쉽습니다.

 

단점

낮은 접근성,단방향이기 때문에 스캔이 데이터의 개수가 많아질수록 데이터를 읽어오는 접근시간이 일반  베열 보다 느립니다.

 

LinkedList 보다 접근성을 보다 항상 시킨 더블 써큘러 링크드 리스트 도 있습니다.

class Node {
    Node next;   //다음 요소의 주소를 저장
    Object obj;  //데이터를 저장
}

 

 

 

더블 써큘러 링크드 리스트

 

 

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름 비효율적인 메모리사용
LinkedList	느리다	빠르다(변경)	데이터가 많을수록 접근성이 떨어짐

 

 

Stack & Queue

• Stack : 마지막에 저장되는 데이터를 가장 먼저 꺼내는 LIFO 구조(바닥이 있는 상자)
  → 순차적으로 데이터를 추가하고 삭제하는 연산을 하기 때문에 Stack은 ArrayList로 구현하면 좋습니다
  수식계산,수식괄호검사,워드프로세서의 undo(작업했던거 취소)/redo(되돌리기). 
  웹브라우저의 뒤로/앞으로
• Queue : 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO 구조 (줄서기)
  → 큐는 처음 저장한 데이터를 가장 먼저 꺼내기 때문에 저장된 데이터를 꺼낼때마다 삭제로 인한 데이터의 복사가 발생하므로 LinkedList로 Queue를 구현하는 것이 적합합니다.
  최근 사용문서, 인쇄작업 대기목록, 버퍼(buffer)

                                                              Stack                                          Queue 

 

 

 

import java.util.*;

class StackQueueEx {
	public static void main(String[] args) {
		Stack st = new Stack();
		Queue q = new LinkedList();	 // Queue인터페이스의 구현체인 LinkedList를 사용
		
		st.push("0");
		st.push("1");
		st.push("2");

		q.offer("0");
		q.offer("1");
		q.offer("2");

		System.out.println("= Stack =");
		while(!st.empty()) {
			System.out.println(st.pop());
		}

		System.out.println("= Queue =");
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

PriorityQueue

스택이나 큐 같은 경우 저장한 순서에 따라 데이터를 넣고 뺏지만, 우선순위큐는 저장 순서와 관계없이 우선순위가 높은 것부터 꺼냅니다.

 추가로 null을 저장할 수 없습니다. null은 우선순위가 없기때문에

우선순위큐는 저장공간으로 배열을 사용하고, 각 요소를 Heap의 형태로 저장합니다.

Deque

큐의 변형으로 양쪽 끝에서 데이터를 추가하고 삭제가 가능한 구조입니다.

lterator

 

 

접근 인터페이스

 

List(배열),set(트리방식),Map() 각각 읽어오는 방법들이 다 다르고 복잡합니다. 그래서

 

컬랙션에 저장된 요소들을 읽어오는 방법을 표준화(통일) 하였습니다.

 

 

 public interface Iterator {
        boolean hasNext();
        Object next();
        void remove();
 }
public interface Collection{
    ...
    public Iterator Iterator();
    ...
}

 

메서드	설명
boolean hasNext()	읽어 올 요소가 남아있는지 확인한다. 있으면 true.없으면 false를 반환한다.
Object next()	다음 요소를 읽어 온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어올 요소가 있는지 확인하는 것이 안전하다
void remove()	next()로 읽어 온 요소를 삭제한다.next()를 호출한 다음에 remove()를 호출해야한다.(선택적 기능)

 

Collection c =new ArrayList(); //다른 컬렉션으로 변경시 이 부분만 고치면 된다.
    Iterator it = c.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }

 

(map에는 Iterator()가 없습니다.)