자바의 컬렉션 프레임워크(List)

코딩테스트를 풀다가 자바의 자료구조를 까먹어서 이 글을 쓰기 시작했다.

이 내용은 TCP school의 내용을 참고해서 정리한 내용이다.

 

자바의 컬렉션 프레임워크는 데이터를 저장하는 자료구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것이다. 이러한 컬렉션 프레임워크는 자바의 인터페이스를 사용하여 구현한다.

 

컬렉션 프레임워크 주요 인터페이스

List 인터페이스, Set 인터페이스, Map 인터페이스 이렇게 3개 존재한다. 이 중에서 List와 Set 인터페이스는 모두 Collection 인터페이스를 상속받지만, 구조상의 차이로 인해 Map 인터페이스는 별도로 정의된다.

인터페이스	설명	구현 클래스
List<E>	순서가 있는 데이터의 집합으로, 데이터의 중복을 허용함	Vector, ArrayList, LinkedList, Stack, Queue
Set<E>	순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않음.	HashSet, TreeSet
Map<K, V>	키와 값의 한 쌍으로 이루어지는 데이터의 집합으로, 순서가 없음. 이때 키는 중복을 허용하지 않지만, 값은 중복될 수 있음.	HashMap, TreeMap, Hashtable, Properties

 

컬렉션 인터페이스

컬렉션 인터페이스는 컬렉션을 다루는데 가장 기본적인 동작들을 정의하고, 그것을 메소드로 제공하고 있다. 

메소드	설명
booleand add(E e)	해당 컬렉션에 전달된 요소를 추가한다.
void clear()	해당 컬렉션의 모든 요소를 제거한다,
boolean contains(Object o)	해당 컬렉션이 전달된 객체를 포함하고 있는지를 확인함.
boolean equals(Object o)	해당 컬렉션과 전달된 객체가 같은지를 확인한다.
boolean isEmpty()	해당 컬렉션이 비어있는지를 확인한다.
Iterator<E> iterator()	해당 컬렉션의 반복자(iterator)를 반환한다.
boolean remove(Object o)	해당 컬렉션에서 전달된 객체를 제거한다.
int size()	해당 컬렉션의 요소의 총 개수를 반환함.
Object[] toArray()	해당 컬렉션의 모든 요소를 Object 타입의 배열로 반환한다.

 ArrayList<String> a = new ArrayList<>();
        a.add("a"); a.add("b");
        Object[] objects = a.toArray(); //String arrayList를 배열로 변경
        System.out.println(a.contains("a"));
        for (int i = 0; i < a.size(); i++) {
            System.out.println(objects[i]);
        }
  //true      
  //a 
  //b

 

List 컬렉션 클래스

List 컬렉션의 중요한 점은 요소의 저장 순서가 유지된다. 또, 같은 요소의 중복 저장을 허용한다.

• ArrayList<E>
• LinkedList<E>
• Vector<E>
• Stack<E>

 

ArrayList<E>

ArrayList<Integer> arr = new ArrayList<>();

arraylist 클래스는 배열을 이용하기 때문에 인덱스를 이용해 배열 요소에 빠르게 접근할 수 있다.

하지만 배열의 크기는 변경할수가 없다. 크기를 늘리기 위해서는 새로운 배열을 생성하고 기존의 요소들을 옮겨야 하는 복잡한 과정을 거쳐야 한다. 자바는 이 과정을 자동으로 수행하지만, 요소의 추가 및 삭제 작업에 걸리는 시간이 매우 길어진다.

public static void main(String[] args) {
    ArrayList<Integer> arr = new ArrayList<>();
    for (int i = 10; i >= 1; i--) {
        arr.add(i);
    }
    for(int e : arr){ //enhanced for문 나는 출력할때 자주 사용한다.
        System.out.print(e + " ");
    }
    //10 9 8 7 6 5 4 3 2 1 
    System.out.print("\n"); 
    Collections.sort(arr); //위에서 설명한 Collections에 공통적인 메소드
    for(int e : arr){
        System.out.print(e + " ");
    }
    //1 2 3 4 5 6 7 8 9 10 
}

 

LinkedList<E> 클래스

LinkedList <Integer> linkedList = new LinkedList<>();

LinkedList는 ArrayList의 단점을 극복하기 위해 만든 것이다. 하지만 각각 장단점이 존재한다.

LinkedList는 저장된 요소가 비순차적으로 분포되며, 이러한 요소들 사이를 링크로 연견한다.

• 단일 연결리스트는 한쪽으로만 연괼 된 리스트이다. 이러 리스트의 삽입과 삭제는 아주 빠르게 할 수 있지만 이전 요소로 접근하기가 매우 어렵다.
• 이중 연결리스트는 단일 연결리스트의 단점을 보완하기 위해 앞 뒤를 모두 연결 한 것이다. 

 

Stack<E> 클래스

Stack<Integer> st = new Stack<>();

Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다.

Stack의 제일 큰 특징은 LIFO라는 점이다. 이것은 가장 나중에 저장된 데이터가 가장 먼저 나오는 것이다.

메소드	설명
boolean empty()	해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환한다.
E peek()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환한다.
E pop()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거한다.
E push(E item)	해당 스택의 제일 상단에 전달된 요소를 삽입한다.
int search(Object o)	해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함. 이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.

public static void main(String[] args) {
    Stack<Integer> st = new Stack<>();
    st.push(2); st.push(1); st.push(3);
    System.out.println(st.search(2));
}
//2 1 3 순으로 저장, search(2)는 위에서 부터 내려와 제일 아래에 있는 2의 index 3을반환
//참고로 search는 1부터 시작한다.

 

Queue<E> 인터페이스

클래스로 구현된 스택과는 달리 자바에서 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다.

Queue에는 많은 종류의 Queue가 존재한다.

• 내가 제일 자주 사용하는 Queue는 Deque이다

Deque<Integer> dq = new ArrayDeque<>();

Deque는 큐이지만 앞과 뒤 모두 삽입이 가능하고 앞과 뒤 모두 제거가 가능하다.

• BlockingQueue

BlockingDeque<Integer> bdq = new LinkedBlockingDeque<>();

Queue가 꽉찼을때의 삽입 시도, Queue가 비어있을때의 추출 시도를 막는 것이다.

• PriorityQueue

//오름 차순으로 정렬
PriorityQueue<Integer> pqL = new PriorityQueue<>();

//내림 차순으로 정렬
PriorityQueue<Integer> pqH = new PriorityQeue<>(Collections.reverseOrder());

우선순위 큐라고 부른다. 우선순위 큐는 입력되는 요소를 자동으로 정렬해준다.

높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다. 내부 요소는 이진트리 구조로 존재한다. 

내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)이다

 

 

출처 

http://www.tcpschool.com/java/java_collectionFramework_concept

코딩교육 티씨피스쿨