자바[JAVA] 자료구조 구현 1 - List Interface

0. Array and List

 

배열은 뭐고 리스트는 뭘까? 그리고 배열이 있는데 리스트를 써야하는 이유는 무엇일까?

 

 

0.1 Array

 

배열은 선형적인 자료구조 중의 하나로 데이터를 일렬로 늘여 놓은 형태의 자료구조입니다. 어떤 언어를 배우던 가장 기본적으로 배우게 되는 메모리 공간 형태이며, 자료형(Data Type)이 둘 이상의 값을 저장할 수 없습니다.(다만, Python 제외)

 

 

0.2 List

 

리스트도 배열과 마찬가지로 선형적인 자료구조 중의 하나입니다.  하지만 배열과 달리 길이가 가변적입니다. 이를 동적할당(Dynamic allocation)이라고 합니다. 또한 배열과 달리 메모리 공간상에 연속적으로 나열되어 할당되지 않고 주소(reference) 를 통해 데이터들이 연결되어있는 형태입니다.

 

배열이나 리스트의 기본 동작인 삽입, 삭제, 검색의 시간복잡도를 보면 왜 우리가 리스트를 사용해야 하는지 알 수 있습니다. 우선 해당 자료구조에 빈 공간을 허용하지 않는다고 가정합니다.

 

 

0.3 Insert with Array and List

 

배열의 경우 삽입은 일반적으로 O(N) 의 시간복잡도를 가집니다. 만약 배열의 가운데에 원하는 요소를 삽입하고자 한다면 뒤에 데이터들을 모두 밀어줘야 하기 때문입니다. 또한 배열의 길이는 가변적이지 않기 때문에 배열의 크기를 넘어간다면 다시 배열의 크기를 크게 할당하고 모든 값들을 복사한 후 삽입을 해야 합니다.

 

이에 반해 리스트, LinkedList 의 경우 O(1) 의 시간복잡도를 가집니다. 주소를 통해 데이터들이 연결되어있기 때문에 주소값만 수정해줌으로써 데이터가 삽입되는 효과를 얻을 수 있습니다.

 

 

0.4 Delete with Array and List

 

삭제의 경우도 비슷한데, 배열의 경우 빈 공간을 허용하지 않기 때문에 뒤에 요소들을 앞으로 당겨주는 동작이 추가적으로 필요합니다.(시간복잡도는 O(N)) 하지만 리스트의 경우 삽입과 비슷하게 주소값만 수정함으로써 삭제된 효과를 얻을 수 있습니다.(시간복잡도는 O(1)) 

 

 

0.5 Search with Array and List

 

검색의 경우 배열은 굉장히 빠릅니다. 만약 정렬되어있다면 이진 탐색을 통해 O(logN) 에 탐색을 할 수 있습니다. 이는 색인(index) 를 통한 접근이 가능하기 때문입니다.

 

하지만 리스트의 경우 검색은 빠르지 않습니다. LinkedList 의 경우 정렬이 되어있든 되어있지 않든 추가적인 기능이 있지 않다면 선형 탐색을 통해 O(N) 에 탐색을 할 수 있습니다. 하지만 이진 탐색 트리(BST) 와 같이 다양한 자료구조를 통해 이를 극복할 방법이 다양하게 존재합니다.(In the case of BST, Time Complexity of Search : O(h) with height of graph h)

 

 

0.6 List Interface in JAVA

 

자바에서는 앞서 설명한 리스트의 특징들을 List Interface 를 통해 구현해놨습니다.

https://docs.oracle.com/javase/8/docs/api/java/util/List.html 

List (Java Platform SE 8 )

크게 중요한 메소드들은 다음과 같습니다.

Methods of List Interface

 

 

 

1. List Interface

 

interface List<E>{
    /**
     * 리스트에 요소를 추가합니다.
     * 
     * @param e 리스트에 추가할 요소
     * @return 리스트에서 중복을 허용하지 않을 경우에 
     *          리스트에 이미 중복되는 요소가 있을 경우{@code false} 를 반환하고,
     *          중복되는 요소가 없을 경우 {@code true}를 반환
     */
    public boolean add(E e);

    /**
     * 리스트에 요소를 특정 위치에 추가합니다.
     * 특정 위치 및 이후에 요소들은 한 칸씩 뒤로 밀립니다.
     * 
     * @param index 리스트에 요소를 추가할 특정 위치 변수
     * @param e 리스트에 추가할 요소
     */
    public void add(int index, E e);

    /**
     * 리스트에서 특정 요소를 삭제합니다. 
     * 동일한 요소가 여러 개일 경우 가장 처음 발견한 요소만 삭제합니다.
     * 
     * @param o 리스트에서 삭제할 요소
     * @return 리스트에 삭제할 요소가 없거나 삭제에 실패할 경우 {@code false} 를 반환하고
     *          삭제에 성공할 경우 {@code true} 를 반환
     */
    public boolean remove(Object o);

    /**
     * 리스트의 index 위치에 있는 요소를 삭제합니다.
     * 
     * @param index 리스트에서 삭제 할 위치 변수
     * @return 삭제된 요소를 반환
     */
    public E remove(int index);

    /**
     * 리스트에서 특정 요소가 있는지 알려줍니다.
     * 
     * @param o 리스트에서 찾는 요소
     * @return 찾는 요소가 있다면 {@code true} 를 반환하고,
     *          찾는 요소가 리스트에 없다면 {@code false} 를 반환
     */
    public boolean contains(Object o);

    /**
     * 리스트에 있는 요소의 개수를 반환합니다.
     * 
     * @return 리스트에 있는 요소 개수를 반환
     */
    public int size();

    /**
     * 리스트에 있는 특정 위치의 요소를 반환합니다.
     * 
     * @param index 리스트에 접근할 위치 변수
     * @return 리스트의 index 위치에 있는 요소 반환
     */
    public E get(int index);

    /**
     * 리스트에서 특정 위치에 있는 요소를 새 요소로 대체합니다.
     * 
     * @param index 리스트에 접근할 위치 변수
     * @param e 새로 대채할 요소 변수
     */
    public void set(int index, E e);

    /**
     * 리스트에 요소가 비어있는지를 반환합니다.
     * 
     * @return 리스트에 요소가 없는 경우 {@code true}, 요소가 있을 경우 {@code false} 를 반환
     */
    public boolean isEmpty();

    /**
     * 리스트에서 특정 요소가 어느 index 에 위치하는지 알려줍니다.
     * 
     * @param o 리스트에서 위치를 찾을 요소
     * @return 리스트에서 처음으로 요소와 일치하는 위치를 반환,
     *          만약 일치하는 요소가 없을 경우 -1 을 반환
     */
    public int indexOf(Object o);

    /**
     * 리스트에 있는 요소들을 모두 삭제합니다.
     */
    public void clear();
}