자료구조 #리스트

리스트 

특정 타입 값들이 순차적으로 정렬된 컬렉션이다.

자바에서는 LinkedList나 ArrayList 클래스를 일반적으로 사용한다.

리스트는 자바의 내장 컬렉션인 배열하고 다르다.

리스트는 크기 지정에 한계가 없으므로 리스트를 사용하기 전에 크기를 지정할 필요가 없다.

어떤 경우에는 LinkedList보다 ArrayList 클래스가 더 적합하며 반대일경우도 있다.

리스트는 애플리케이션의 성능과 메모리 사용량과 밀접한 관계가 있다.

리스트를 사용하려면 메서드와 생성자 매개변수는 필드 정의로 List 인터페이스 사용해야 하며, 이를 통해 상황에 따라 타입 구현을 변경하기도 쉽다.

배열과 리스트의 관계

배열은 대괄호를 이용하는 타입으로 정의

final int[] integers = new int[3]; //명시적 크기지정 final boolean[] bools = {false, true, true, false}; // 암시적으로 크기지정 final String[] strings = new String[] {"one", "two"};  // 계산된 값을 이용 final Ramdom r = new Random(); final String[] ramdomArrayLength = new String[r.nextInt(100)]; //배열의 원소에는 인덱스 값을 이용 랜덤 접근

배열 전체를 사용 중일 때 원소를 추가하려면 배열 크기를 늘려야 한다.

실제로는 더 큰 배열을 새롭게 만들고 현재 배열에 있는 모든 원소를 새로운 배열로 복사한 다음 새로운 배열이 원본 배열의 주소를 가리키도록 재할당한다.

public void arrayCopy() { int[] integers = {0,1,2,3,4}; int[] newIntegersArray = new int[integers.length+1]; System.arraycopy(integers, 0, newIntegersArray, 0, integers.length); integers = newIntegersArray; integers[5] = 5; }

배열 대신 List 인터페이스를 사용할수도 있다.

ArrayList 클래스는 리스트의 데이터로 배열을 사용하는 List 인터페이스의 구현체로 ArrayList 클래스를 생성할 때는 배열의 초기 크기를 지정할 수 있다. 크기를 지정하지 않으면 기본 배열의 크기는 10이다.

원소로 가득한 배열에 새로운 원소를 추가할 때마다 ArrayList 클래스는 자동으로 더 큰 배열을 재할당한다.

단, 시간이 소요되며 더 큰 메모리 용량을 소모한다.

ArrayList 클래스를 생성할 때 크기가 큰 컬렉션을 이용할 것이라면 기본 크기를 크게 잡는 것이 좋다.

그러면 리스트 크기를 키우느라 배열을 재할당 작업을 줄일 수 있다.

ArrayList 클래스로 생성한 배열의 시작위치나 중간 위치에 새로운 원소를 추가하려고 하면 다음에 있는 모든 원소는 공간을 만들기 위해 이동해야 한다. 배열의 크기가 크다면 연산량이 많은 작업이다.

특히 시작 위치와 가까운 곳에 원소를 추가할 수록 더 그렇다.

새로운 원소를 추가할 때 배열 크기를 크게 재할당해야 하는 경우도 마찬가지다.

배열 크기 재할당은 단방향으로 이루어진다.

ArrayList 클래스로 생성한 배열은 원소를 많이 삭제해도 배열 크기는 줄어들지 않는다.

원소의 개수가 계속 변경되는 리스트라면 ArrayList 클래스를 사용한 배열 생성은 최적의 선택이 아닐 수 있다.

메모리에 저장된 원소의 개수가 계속 변경되는 상황이라면 LinkedList 클래스로 배열을 생성하는 것이 더 적합할 수 있다.

LinkedList는 열결 리스트를 구현할 수 있는 또 다른 리스트 구현체이다.

원소들을 저장하는데 배열을 이용하지 않고, 리스트 안에서 다음 원소를 가리키는 내부 객체를 이용한다.

배열과 연결리스트

인덱스를 이용해서 원소에 접근할 경우 해당 인덱스에 접근할 때 까지 리스트를 순회해야한다. 순회는 단방향으로 이루어진다.

ArrayList 클래스로 생성하는 배열은 랜덤 접근을 통해 해당 인덱스를 바로 찾을 수 있도록 한다.

LinkedList 클래스로 생성하는 연결 리스트는 앞 원소를 참조해서 원소를 찾을 수 없다.

연결리스트는 리스트의 양방향에서 원소를 참조할 수 있는 이중 연결리스트(doubly linked list)를 이용해야 원소를 찾을 수 있게 해야한다.

리스트의 첫 부분이나 중간에 원소를 삽입/삭제 할일이 많다면 LinkedList 클래스를 사용하는 것이 좋다.

게다가 LinkedList는 ArrayList 클래스에서 배열 재할당 과정으로 인해 발생하는 손실을 막아준다.

그리고 리스트 크기가 작아지면 메모리 용량 역시 작아진다.

스택처럼 특수한 자료구조를 만들었다 자료구조로 LinkedList 클래스를 사용하는 것이 좋다.

리스트의 첫 부분에도 원소를 간단하게 넣고 뺄 수 있기 때문이다.