JAVA 문법 - ArrayList와 LinkedList(메모리 측면 비교)

강의 소개

현재 수강하고 있는 멀티캠퍼스 k-digital 지능형 웹서비스 풀 스택 과정을 수강하며 적은 내용입니다.

교재로는 자바의 정석을 사용하고 있습니다.

---

 

List컬렉션 (컬렉션 프레임워크 내)

List컬렉션은 객체를 일렬로 가지고 있는 구조이다. 객체에 인덱스를 자동으로 부여해 인덱스를 사용하여, 객체를 검색하고 삭제할 수 있다.

List컬렉션은 객체 자체를 저장하지 않고, 객체의 번지를 저장한다.

 

[힙 영역 내 List컬렉션의 형태]

 

- 특징

저장 순서가 유지된다.

같은 요소(객체)를 중복 저장할 수 있다.

 

List컬렉션 내에는 Vector, ArrayList, LinkedList, stack 등이 있다. 하지만 이 중 Vector는 사용이 권장되지는 않는다.

 

---

 

1. ArrayList

Vector를 개선한 것으로 보통 가장 많이 사용하는 컬렉션 클래스이다.

ArraList는 Object배열을 이용해서 요소를 순차적으로 저장한다. 연속적인(= 순차적) 배열을 이용하기 때문에 인덱스를 활용해 빠르게 요소인 객체에 접근할 수 있다. 그러나 배열은 저장할 수 있는 크기가 고정되어 있다. 즉, 크기를 변경할 수 없다.

만약 크기를 변경해야 하는 경우가 있다면 새로운 배열을 생성한 뒤, 데이터를 복사해야 한다. 이 과정은 자동으로 수행되지만, 크기의 변경에 너무 많은 시간이 소요된다.

 

- 구조

이렇게 힙 내부에 요소들이 순서대로 저장된다.

 

- 장점

데이터 검색에 소요되는 시간이 짧다.

- 단점

비순차적인 위치의 (배열의 끝부분을 제외한 다른 위치) 데이터 추가, 삭제에 시간이 매우 많이 걸린다.

 

- 생성 코드

// 초기 용량: 10개의 객체를 저장할 수 있는 용량 자동지정.
List<타입> 리스트이름 = new ArrayList<타입>();

만약 매개변수를 주지 않으면 10개의 객체를 저장할 수 있는 저장공간이 있는 ArrayList가 생성된다.

 

List<타입> 리스트이름 = new ArrayList<타입>(저장할 데이터의 개수);

만약 크기를 지정해서 생성하고 싶다면 저장할 크기만큼 매개변수로 주면 된다.

 

List<타입> 리스트이름 = Array.asList(요소1, 요소2, 요소3);

보통은 ArrayList를 생성하고 add로 필요에 의해 객체들을 추가하지만, 고정된 객체들로 List를 만드는 경우도 있다. 그런 경우에는 Array.asList메서드를 사용해서 한 번에 리스트를 만드는 것이 편하다.

 

 

- 메서드

추가는 add메서드, 조회는 get메서드를 사용한다.

또, 삭제는 remove메서드를 사용한다.

 

 

- ArrayList에서의 삭제(메모리 측면)

ArrayList에 저장된 특정 인덱스에 위치한 데이터를 삭제하는 과정은 아래와 같다.

 

만약 이런 ArrayList가 있고, 이 ArrayList의 이름은 arr이라고 해보자.

이 경우  data [2]를 삭제하고 싶다면 아래와 같은 코드를 사용하면 된다.

arr.remove(2)

 

remove메서드를 통해 삭제를 하면, 아래의 삭제된 위치의 바로 다음에 있던 4가 data [2]의 공간으로 복사되어 이동한다. 그렇게 되면 원래 4가 있던 위치인 data [3]은 자연스럽게 비어 null이 된다.

이 예시는 3번째(= 인덱스 2) 요소를 제거한 경우이다.

만약 첫 번째 요소를(인덱스 0에 위치한 요소) 삭제하는 경우 더 많은 배열 복사와 이동이 발생하여 시간이 많이 걸린다. 왜냐하면 삭제 시 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1 만큼씩 당겨지기 때문이다.

하지만 배열의 가장 마지막 값을 삭제하는 경우에는 배열 복사와 이동이 발생하지 않아 빠르다.

 

특정 값을 삽입하고 싶을 경우에도 삽입 위치부터 마지막 인덱스까지 모두 1씩 밀려난다. (삭제와 마찬가지로 가장 마지막 위치에 삽입하는 경우는 예외이다.)

---

 

2. LinkedList(이중 연결 리스트)

배열의 단점을 보완한 형태이다.

비순차적으로 요소를 저장하여 이들을 link로 연결한다. 즉, 연결을 통해 불연속적인 데이터를 저장하여 데이터의 추가 저장과 삭제가 빠르다.

 

- 연결 리스트의 형태

1) 단일 연결 리스트

다음 요소를 가리키는 참조가 있어서 저장과 삭제 작업이 아주 빠르게 진행된다. 또한, 특정 요소를 삭제 혹은 추가할 경우 다음 요소를 가리키는 참조만 변경하면 되어 삭제, 추가 작업이 아주 빠르다.

하지만 이전 요소에 대한 접근이 어렵다. 다음 요소에 대한 참조만 되어 있기 때문이다.

 

2) 이중 연결 리스트

앞선 단일 연결 리스트의 단점을 보완한 형태이다. 다음 요소, 이전 요소에 대한 link가 모두 있어 접근이 빠르다.

LinkedList는 이런 이중 연결 리스트를 구현한 것이다. 추가적으로, LinkedList클래스는 Link 인터페이스를 구현하여 ArrayList 클래스와 사용할 수 있는 메서드가 거의 같다. LinkedList와 ArrayList은 사용방법은 같지만, 메모리에 내부적으로 데이터(요소)를 저장하는 방식이 차이점인 것이다.

 

- 생성 코드

List<타입> 배열이름 = new LinkedList<타입>();

 

- LinkedList에서의 삭제(메모리 측면)

만약, linkedlist.remove(2) 코드를 사용하여 1번 인덱스의 값을 삭제하고 싶다고 가정해보자. 

이렇게 값을 삭제할 경우 사진과 같이 값을 제거한 뒤 연결만 새로 해주면 된다. ArrayList에서는 삭제 또는 삽입시 다른 인덱스를 당겨오거나 밀어야 했었는데, 이처럼 LinkedList는 단 한 번의 작업으로 삭제, 삽입을 진행할 수 있어 성능이 좋다.

 

---

 

ArrayList와 LinkedList의 결론

요약하자면 특징은 아래와 같다.

 

ArrayList	순차적인(= 끝에서부터) 데이터의 추가와 삭제, 검색	인덱스를 사용하여 저장된 요소를 관리
LinkedList	비순차적인(= 중간 위치에서) 데이터의 추가와 삭제	인접 참조를 link로 연결하여 저장된 요소를 관리

 

따라서 객체의 삽입, 삭제가 자주 일어나는 경우엔 LinkedList를 사용하는 것이 바람직하다. 반면 객체의 검색 또는 마지막 위치에 삽입하는 작업이 잦은 경우라면 ArrayList를 사용하는 것이 성능상 좋다.

 

---

toArray메서드

컬렉션 형태의 리스트를 배열로 바꾸기 위해서 toArray메서드를 사용한다.

List<String> list = new ArrayList<String>();
list.add("가");
list.add("나");

String[] arr = new String[list.size()];
arr = list.toArray(arr);

 

출처: 자바의 정석(남궁 성 저), 멀티캠퍼스

참고자료: 이것이 자바다(신용권 저)