8.1 Collection Framework - List 인터페이스

컬렉션 프레임워크 (Collection Framework)

데이터 군을 저장하는 클래스들을 표준화한 설계

다수의 데이터를 다루는 데 필요한 다양하고 풍부한 클래스를 제공함

컬렉션 프레임워크의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스의 이름에 포함되어있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있도록 되어있다.

* vector와 Hashtable은 컬렉션 프레임이 만들어지기 이전부터 존재하기 때문에 컬렉션 프레임워크의 명명법을 따르지 않는다. (가능하면 사용하지 않는게 좋음)

 

List 인터페이스

중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용

 

1. ArrayList

컬렉션 프레임워크에서 가장 많이 사용되는 클래스

데이터의 저장순서가 유지되고 중복을 허용한다

배열이 가지고 있는 불편한 점들을 줄일수 있다 (ex. 배열은 한번 크기를 지정하면 변경할 수 없다)

* java.util.ArrayList 패키지를 import 해야 사용할수 있다

ArrayList()	크기가 10인 ArrayList생성
ArrayList(Collection c)	주어진 컬렉션이 저장된 ArrayList생성
ArrayList(int capacity)	지정된 초기 용량을 갖는 ArrayList생성
boolean add(Object o)	ArrayList의 마지막에 객체를 추가
void add(int index, Object element)	주어진 위치에 객체를 저장
boolean addAll(Collection c)	주어진 컬렉션의 모든 객체를 저장
boolean addAll(int index, Collection c)	지정된 위치부터 주어진 컬렉션의 모든 객체를 저장
void clear()	ArrayList를 완전히 비운다
Object clone()	ArrayList를 복제한다
boolean contains(Object o)	객체가 ArrayList에 포함되어 있는지 확인
void ensureCapacity(int minCapacity)	ArrayList의 용량이 최소한 minCapacity가 되도록 한다
Object get(int index)	지정된 위치에 저장된 객체를 반환
int indexOf(Object o)	지정된 객체가 저장된 위치를 반환
boolean isEmpty()	ArrayList가 비어있는지 확인
literator iterator()	ArrayList의 iterator객체를 반환
int lastIndexOf(Object o)	객체가 저장된 위치를 역방향으로 검색해서 반환
Object remove(int index)	지정된 위치에 있는 객체 제거
boolean remove(Object o)	객체를 제거
boolean removeAll(Collection c)	기정한 컬렉션에 저장된 것과 동일한 객체들을 ArrayList에서 제거
boolean retainAll(Collection c)	ArrayList에 저장된 객체 중에서 주어진 컬렉션과 공통된 것들만을 남기고 나머지는 삭제
Object set(int index, Object element)	주어진 객체를 지정된 위치에 저장
int size()	ArrayList에 저장된 객체의 수 반환
void sort(Comparator c)	지정된 정렬기준으로 ArrayList정렬
List sublist(int fromIndex, int toIndex)	fromIndex부터 toIndex 사이에 저좡된 객체를 반환
void trimToSize()	빈 공간을 없앤다

import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        ArrayList list1 = new ArrayList(10);
        list1.add(5);
        list1.add(4);
        list1.add(2);
        list1.add(0);
        list1.add(1);
        list1.add(3);

        ArrayList list2 = new ArrayList(list1.subList(1,4));
        System.out.println(list1);
        System.out.println(list2);

        Collections.sort(list1);
        Collections.sort(list2);
        System.out.println(list1);
        System.out.println(list2);

        System.out.println(list1.containsAll(list2));

        list2.add("B");
        list2.add(3, "A");
        list1.add("C");

        list2.set(3, "AA");

        System.out.println(list1);
        System.out.println(list2);

        System.out.println(list1.retainAll(list2));
        System.out.println(list1);
        System.out.println(list2);

        for(int i = list2.size()-1;i>=0;i--){
            if(list1.contains(list2.get(i)))
                list2.remove(i);
        }

        System.out.println(list1);
        System.out.println(list2);
        
    }
}

실행결과

 

  for(int i = list2.size()-1;i>=0;i--){
            if(list1.contains(list2.get(i)))
                list2.remove(i);
        }

for문의 변수 i를 0부터 증가시킨 것이 아니라 list2의 사이즈의 -1부터 감소시킨 이유,

0부터 증가시키면서 삭제하면 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 하기 때문에 맞는 결과를 얻을수 없음.

감소시키면서 삭제 작업을 해야 자리이동이 발생해도 영향을 받지 않는다

* remove()메서드 내부를 보면, 삭제할 객체의 바로 아래에 있는 데이터를 한칸씩 위로 복사해서 덮어쓰는 방식으로 처리한다.

 

 

2. LinkedList

배열의 단점(크기 변경이 불가능, 비순차적인 데이터의 추가 또는 삭제에 시간이 오래 걸림)을 보안하기위해 고안된 것

불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있음

 

배열과 링크드 리스트

링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

class Node{
	Node next;
    Object obj;
}

 

이동방향이 단방향 이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 이 점을 보안한 것이 더블 링크드 리스트(이중 연결리스트)이다.

더블 링크드 리스트(doubly linked list)는 단순히 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조 뿐만 아니라 이전 요소에 대한 참조가 가능하도록 했을뿐, 그 외에는 링킄드 리스트와 같다.

class Node{
	Node next;
    Node previous;
    Object obj;
}

링크드 리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보더 더 많이 사용된다.

 

더블 링크드 리스트의 첫번째 요소와 마지막 요소를 서로 연결시킨 이중 원형 연결리스트(doubly circular linked list)도 있다.

이렇게 하면 마지막 요소의 다음 요소가 첫번째 요소가 되고, 첫번째 요소의 이전 요소가 마지막 요소가 된다.

 

LinkedList클래스는 이름과 달리 doubly linked list로 구현되어 있는데, 이는 링크드 리스트의 단점인 접근성을 높이기 위한 것이다.

LinkedList()	LinkedList객체 생성
LinkedList(Collection c)	주어직 컬렉션을 포함하는 LinkedList객체 생성
boolean add(Object c)	지정된 객체를 LinkedList의 끝에 추가
void add(int index Object element)	지정된 위치에 객체를 추가
boolean addAll(Collection c)	주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가
boolean addAll(int index, Collection c)	지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가
void clear()	LinkedList의 모든 요소 삭제
boolean contains(Object o)	지정된 객체가 LinkedList에 포함되었는지 알려줌
boolean containsAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되었는지 알려줌
Object get(int index)	지정된 위치의 객체를 반환
int indexOf(Object o)	지정된 객체가 저장된 위치를 반환
boolean isEmpty()	LinkedList가 비어있는지 알려준다
iterator iterator()	iterator를 반환
Object remove(int index)	지정된 위치의 객체를 LinkedList에서 제거
boolean removeAll(Collection c)	지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
boolean retainAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
Object set(int index, Object element)	지정된 위치의 객체를 주어진 객체로 바꿈
Object element()	LinkedList의 첫번째 요소를 반환
boolean offer(Object o)	지정된 객체를 LinkedList의 끝에 추가
Object peek()	LinkedList의 첫번째 요소를 반환
Object poll()	LinkedList의 첫번째 요소를 반환(LinkedList에서는 제거됨)
Object remove()	LinkedList의 첫번째 요소를 제거

LinkedList역시 List인터페이스를 구현했기 때문에 ArrayList와 내부구현 방법만 다를뿐, 제공하는 메서드의 종류와 기능은 거의 같다.

 

ArrayList와 LinkedList 성능 비교

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

1) 순차적으로 추가/삭제 하는 경우에는 ArrayList가 빠르다

순차적으로 삭제한다는 것은 마지막 데이터부터 역순으로 삭제해나간다는 것을 의미하며, ArrayList는 마지막 데이터부터 삭제할 경우, 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다

(LinkedList의 경우에는 재배치가 필요함)

 

2) 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 빠르다

LinkeLIst는 각 요소간의 연결만 변경해주면 되기 때문에 처리 속도가 빠르다.

만면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리 속도가 늦다.

 

3. Stack

마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어있다.

스택의 구조

boolean empty()	Stack이 비어있는지 알려준다
Object peek()	Stack의 맨 위에 저장된 객체를 반환 (pop()과 달리 갹채를 꺼내지는 않는다)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다
Object push()	Stack에 객체를 저장
int search(Object o)	Stack에서 주어진 객체를 찾아서 그 위치를 반환

import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Stack st = new Stack();

        st.push("0");
        st.push("1");
        st.push("2");

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

실행 결과

 

 

 

 

배열을 이용한 자료구도는 데이터를 읽고 저장하는 데 효율은 좋지만 용량 변경이 필요할 때는 새로운 배열을 생성한 뒤에 기존의 배열부터 새로 생성된 배열로 데이터를 복사해야되기 때문에 효율이 떨어진다.

그래서 처음 인스턴스를 생성할때, 데이터의 개수를 고려햐여 충분한 용량의 인스턴스를 생성하는 것이 좋다.