[자료구조] 0. Java 리스트 인터페이스 (List Interface)

자료구조란?

• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법들이다.
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 된다.
• 데이터의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있다.
• 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요하다.

---

List Interface

자바 컬렉션 프레임워크(Collection(List, Map, Set), Collection(Stack, Queue))에서 지원하는 ArrayList, LinkedList 같은 리스트 클래스들은 우리가 조금더 데이터들을 다루기 쉽도록 메소드들을 구현한 것이다.

 

공통점

• 동일한 특성의 데이터들을 묶는다.
• 반복문 내에 변수를 이용하여 하나의 묶음 데이터들에 모두 접근할 수 있다.

차이점 - 배열

• 처음 선언한 배열의 크기(길이)를 변경할 수 없다. 이를 정적 할당(static allocation)이라고 한다.
• 메모리에 연속적으로 나열되어 할당된다.
• index에 위치한 하나의 데이터를 삭제하더라도 해당 index에는 빈공간으로 계속 남는다.

차이점 - 리스트

• 리스트의 길이가 가변적이다. 이를 동적 할당(dynamic allocation)이라고 한다.
• 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되는 것이 아닌 각 데이터들은 주소(referenc)로 연결되어 있다.)
• 데이터 사이의 빈 공간을 허용하지 않는다.

---

배열의 장단점

장점

• 데이터의 크기가 정해져 있는 경우 메모리 관리가 편하다.
• 메모리에 연속적으로 나열되어 할당되기 때문에 index를 통한 색인(접근)속도가 빠르다.

단점

• 배열의 크기를 변경할 수 없기 때문에 초기에 너무 큰 크기로 설정했을 경우 메모리 낭비가 심해지고, 반대로 너무 작은 크기로 설정했을 경우 데이터를 못 담는 상황이 발생할 수 있다.
• 데이터를 삽입(add), 삭제(remove)를 할 때 빈 공간을 허용하지 않고자 한다면, 뒤의 데이터들을 모두 밀어내거나 당겨주어야 하므로 삽입, 삭제가 빈번한 경우에는 적합하지 않다.

 

리스트의 장단점

장점

• 데이터 개수에 따라 해당 개수만큼 메모리를 동적 할당해주기 때문에 메모리 관리가 편해진다.
• 빈 공간을 허용하지 않기 때문에 데이터 관리에도 편하다.
• 포인터(주소)로 각 데이터들이 연결되어 있기 때문에 해당 데이터에 연결된 주소만 바꿔주면 되기 때문에 삽입, 삭제에 용이하다.(ArrayList는 예외)

단점

• 객체로 데이터를 다루기 때문에 적은 양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 커진다. 예를 들어, primitive type인 int는 4Byte를 차지한다. 반면에 Wrapper Class인 Integer는 32bit JVM에선 객체의 헤더(8Byte), 원시 필드(4Byte), 패딩(4Byte)으로 '최소 16Byte'를 차지한다. 거기에 이러한 객체 데이터들을 다시 주소로 연결하기 때문에 16 + α가 된다.
• 기본적으로 주소를 기반으로 구성되었고 메모리에 순차적으로 할당하는 것이 아니기 때문에 (물리적 주소가 순차적이지 않다.) 색인(검색)능력은 떨어진다.

---

배열 (Array)

• 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같다.
• 동일한 데이터 타입을 순서에 따라 관리하는 자료구조
• 정해진 크기가 있다.
• 요소의 추가와 제거시 다른 요소들의 이동이 필요하다.
• 배열의 i번째 요소를 찾는 인덱스 연산이 빠르다.
• JDK 클래스 : ArrayList, Vector

 

Array 구현하기

 

public class Array {
    int[] intArr;
    int count;                  // 개수

    public int ARRAY_SIZE;
    public static final int ERROR_NUM = -999999999;

    // 기본 생성자. 이 예제에서 배열의 사이즈는 10으로 기본 생성한다.
    public Array() {
        count = 0;
        ARRAY_SIZE = 10;
        intArr = new int[ARRAY_SIZE];
    }

    // 사이즈를 받아 생성하는 생성자. 배열의 사이즈는 Size의 크기대로 생성한다.
    public Array(int size) {
        count = 0;
        ARRAY_SIZE = size;
        intArr = new int[size];
    }

    // 배열에 요소를 추가한다.
    public void addElement(int num) {
        if (count >= ARRAY_SIZE) {
            System.out.println("Not enough memory.");
            return;
        }
        intArr[count++] = num;
    }

    // 원하는 위치에 요소를 삽입.
    public void insertElement(int position, int num) {
        int i;

        if (count >= ARRAY_SIZE) {
            System.out.println("Not enough memory");
            return;
        }

        if (position < 0 || position > count) {
            System.out.println("IndexOutOfBoundsException");
            return;
        }

        for (i = count - 1; i >= position; i--) {
            intArr[i + 1] = intArr[i];
        }

        intArr[position] = num;
        count++;
    }

    // 원하는 위치의 요소를 삭제.
    public int removeElement(int position) {
        int ret = ERROR_NUM;

        if (isEmpty()) {
            System.out.println("There is no element");
            return ret;
        }

        if (position < 0 || position >= count) {
            System.out.println("IndexOutOfBoundsException");
            return ret;
        }

        ret = intArr[position];

        for (int i = position; i < count - 1; i++) {
            intArr[i] = intArr[i + 1];
        }
        count--;

        return ret;
    }

    // 원하는 위치의 요소 검색
    public int getElement(int position) {
        if (position < 0 || position > count - 1) {
            System.out.println("검색 위치 오류. 현재 리스트 개수는 " + count + "개 입니다.");
            return ERROR_NUM;
        }
        return intArr[position];
    }

    // 모든 요소 출력
    public void printAll() {
        if (count == 0) {
            System.out.println("출력할 내용이 없습니다.");
            return;
        }

        for (int i = 0; i < count; i++) {
            System.out.println(intArr[i]);
        }
    }

    // 모든 요소 삭제
    public void removeAll() {
        for (int i = 0; i < count; i++) {
            intArr[i] = 0;
        }
        count = 0;
    }

    // 배열 사이즈 반환
    public int getSize() {
        return count;
    }

    // 배열이 비었는지 확인
    public boolean isEmpty() {
        if (count == 0) {
            return true;
        } else {
            return false;
        }
    }
}

 

 

List Interface에 선언된 대표적 메소드

 

메소드	리턴 타입	설명
add(E e)	boolean	요소를 추가한다
remove(Object o)	boolean	지정한 객체와 같은 첫 번째 객체를 삭제한다.
contains(Object o)	boolean	지정한 객체가 컬렉션에 있는지 확인한다. 있을 경우 true, 없으면 false를 반환한다.
size()	int	현재 컬렉션에 있는 요소 개수를 반환한다.
get(int index)	E	지정된 위치에 지정된 원소를 반환한다.
set(int index, E elements)	E	지정된 위치에 있는 요소를 지정된 요소로 바꾼다.
isEmpty()	boolean	현재 컬렉션에 요소가 없다면 true, 존재한다면 false를 반환한다.
equals(Object o)	boolean	지정된 객체와 같은지 비교한다.
indexOf(Object o)	int	지정된 객체가 있는 첫 번째 요소의 위치를 반환한다. 만약 없을 경우에는 -1을 반환한다.
clear()	void	모든 요소들을 제거한다.

 

이 대표적인 메소드를 바탕으로 인터페이스를 하나 만들어보자. 그리고 이 인터페이스를 사용하여 다음 포스팅에서 다룰 ArrayList, LinkedList를 구현해볼 것이다.

 

/**
 * Java List Interface
 * List는 ArrayList, SinglyLinkedList, DoublyLinkedList에 의해 각각 구현된다.
 */

public interface List<E> {

    /**
     * 리스트에 요소를 추가한다.
     *
     * @param value 리스트에 추가할 요소
     * @return 리스트에서 중복을 허용하지 않을 경우에 리스트에
     *         중복되는 요소가 있을 경우 {@code false} 를 반환하고
     *         중복되는 요소가 없다면 {@code true}를 반환
     */
    boolean add(E value);

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

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

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

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

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

    /**
     * 리스트에 특정 요소가 있는지 여부를 확인한다.
     *
     * @param value 리스트에서 찾을 특정 요소 변수
     * @return 리스트에 특정 요소가 존재할 경우 {@code true}, 없을 경우 {@code false} 반환
     */
    boolean contains(Object value);

    /**
     * 리스트에 특정 요소가 몇 번째 위치에 있는지를 반환한다.
     *
     * @param value 리스트에서 위치를 찾을 요소 변수
     * @return 리스트에서 처음으로 요소와 일치하는 위치를 반환
     *         만약 일치하는 요소가 없다면 -1 반환
     */
    int indexOf(Object value);

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

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

    /**
     * 리스트에 있는 모든 요소 모두 삭제.
     */
    public void clear();
}