자바를 사용하는 개발자라면 정말 자주 사용할 인터페이스 중 하나로 List 가 있습니다. 데이터를 담는 컬렉션 중 하나입니다.
대표적으로는 다음과 같은 메소드를 가지고 있습니다.
- add
- get/set
- indexOf
- isEmpty/size
- remove
- clear
실제로 무척 자주 사용하는 인터페이스이며, 개발자 기술 면접에서도 자주 언급되는 내용입니다. 오늘은 그 구현체인 Array List와 Linked List를 살펴보려고 합니다.
ArrayList
내부를 배열로 구현한 리스트입니다. 컬렉션의 크기 (size)를 필드로 따로 관리하고, 실제 배열은 리스트의 크기와 같거나 그것보다 큽니다. 배열과 size를 필드로 가집니다.
이 때문에 get/set 에 유리합니다. 그러나 새 값을 추가할 때 배열을 새로 만들고 오브젝트를 모두 옮겨야 할 가능성이 있습니다. 이 때문에, 컬렉션의 전체 크기보다 더 큰 배열을 만들어 놓는 것으로 이 문제를 해결합니다. 그러나 리스트의 가장 앞에에 값을 추가하고 싶을 때는 어쩔 수 없이 새롭게 일일히 배치해야 합니다.
또한 배열을 사용하기 때문에, 메모리에 물리적으로 나란히 저장되는 이점이 있습니다. 컴퓨터 하드웨어는 연속된 메모리를 읽어올 때 성능에 이점이 있습니다.
- add (뒤에 추가) : O(1)
배열의 size+1 번째 행에 오브젝트를 추가해줍니다.
- add (앞에 추가) : O(n)
기존의 배열보다 큰 크기의 배열을 생성하고, 추가할 오브젝트를 첫번째 행에 더하고, 기존 배열의 행을 모두 옮깁니다.
- get : O(1)
배열에서 바로 값을 호출합니다. set도 마찬가지로 O(1) 입니다.
- indexOf : O(n)
배열을 순회하면서 equals()를 통해 비교합니다.
- isEmpty : O(1)
필드의 size 값이 0인지를 확인합니다.
- remove : O(n)
새 배열을 만들고, 삭제할 행을 모든 오브젝트를 옮겨오고, 삭제한 행 이후의 값들의 행번호를 하나씩 당깁니다.
가장 마지막 값을 삭제한다면, 가장 마지막의 오브젝트를 지우고 사이즈를 1 줄이기만 하면 됩니다. (이 경우 O(1))
- clear : O(n)
배열을 순회하면서 모든 값을 비우고, size를 0만 조절해주면 됩니다.
실제 구현체의 코드는 다음 주소에서 확인할 수 있습니다.
[https://developer.classpath.org/doc/java/util/ArrayList-source.html]
LinkedList (Singly)
내부를 노드 형태로 연결합니다. 각 노드는 다음 노드의 참조값(next)을 가지고 있습니다. 첫번째 노드(head)와 size를 필드로 가지고 있습니다.
각 노드들을 연결하기 위한 참조를 가지기 때문에, 메모리에서 손해를 볼 수 있습니다.
- add (뒤에 추가): O(n)
노드를 순회하면서 마지막 노드를 찾습니다. 마지막 노드에 새 노드를 연결합니다.
- add (앞에 추가): O(1)
새 노드를 생성합니다. head 를 새로 만든 새 노드로 생성하고, next를 기존의 head 노드로 변경합니다.
- get/set : O(n)
노드를 순회하면서 원하는 순서의 노드를 찾습니다. 값을 반환하거나 새 노드로 변경합니다.
- indexOf : O(n)
노드를 순회하면서 equals로 확인합니다.
- isEmpty/size : O(1)
size 값이 0 인지 확인하거나 반환합니다.
- remove : O(n)
노드를 순회하면서 삭제할 노드를 찾습니다. 해당 노드를 next로 가지는 이전 노드의 next를 삭제할 노드의 next로 변경해줍니다.
가장 첫번째 값을 지운다면, head 노드를 기존 head 노드의 next 로 변경해주면 됩니다. (이 경우 O(1))
- clear : O(n)
head를 null로, size 를 0으로 바꿔줍니다. 마치 O(1)처럼 보입니다.
그러나 주의해야할 점은, head 에서 연결이 끊어진 n개의 노드들은 언젠가 garbage collector가 일일히 청소해줘야합니다. 이 청소에 걸리는 비용은 노드의 갯수에 비례합니다. 즉 O(n)이 됩니다.
LinkedList (Doubly)
Singly Linked List와 동일하게 내부를 노드로 연결합니다. 단, 연결할 때 각 노드는 자신의 다음 노드(next)만이 아니라 자신의 이전 노드(prev)의 참조값도 가지고 있습니다. head, size 말고도 가장 마지막 노드인 tail 을 필드로 가지고 있습니다.
실제 Java의 LinkedList 는 Singly Linked List가 아닌 Doubly Linked List의 코드를 사용합니다.
- add (뒤에 추가): O(1)
새 노드를 만들고 기존의 tail의 next에 새 노드를 연결, 새 노드의 prev에 기존의 tail을 추가합니다. 그리고 tail을 새 노드로 변경합니다.
- add (앞에 추가): O(1)
새 노드를 만들고 기존의 head의 prev에 새 노드를 연결, 새 노드의 next에 기존의 head를 추가합니다. 그리고 head를 새 노드로 변경합니다.
- get/set : O(n)
Singly와 동일합니다. 단, index가 head 와 tail 중 어디에 더 가까운지 알 수 있으므로, 실질적으로는 Singly 보다 더 빠르게 작동합니다. index가 size / 2 보다 크다면 tail에서부터 탐색을, 작다면 head 부터 탐색을 합니다.
- indexOf : O(n)
Singly 와 동일합니다. 노드를 순회하면서 확인합니다.
- isEmpty/size : O(1)
Singly와 동일합니다. size 가 0 인지 확인합니다.
- remove : O(n)
Singly와 동일합니다. 단, 가장 첫번째와 가장 마지막 오브젝트를 제거할 때에는 O(1)로 동작합니다. 실제로 가장 첫번째 요소나 가장 마지막 요소를 삭제하는 경우가 많다면 중요합니다.
가장 첫번째나 마지막 오브젝트를 지우고, 그 노드와 연결된 오브젝트를 새로운 head나 tail로 변경합니다.
- clear : O(n)
Singly 와 동일합니다.
실제 구현체의 코드는 다음 주소에서 확인할 수 있습니다.
[https://developer.classpath.org/doc/java/util/LinkedList-source.html]
정리
- ArrayList 는 get과 set에 유리합니다. 오브젝트의 입출력 자체가 중요하다면 ArrayList가 유리합니다.
- LinkedList 는 add와 remove에 유리합니다. 리스트의 요소 추가/삭제가 빈번히 일어난다면 LinkedList가 유리합니다.
- Linked List는 Singly와 Doubly가 있으나, Doubly가 (메모리 사용을 제외한다면) Singly에 비해 유리합니다. 자바는 기본적으로 Doubly Linked List 를 사용합니다.
- Linked List는 ArrayList보다 종종 더 많은 메모리를 사용합니다. (공간 복잡도에 있어서 불리)
유의할 점은, 이런 선택 기준은 어플리케이션의 성능이 자료 구조에 의존하는 형태가 아니라면 큰 의미가 없다는 점입니다. 이를테면, 외부 DB와의 입출력에서 발생하는 IO가 어플리케이션 실행시간의 주요원인이라면, 어플리케이션 내부의 List 선택은 큰 의미가 없을 수 있습니다.
또한, 성능 자체가 어플리케이션의 주요한 관심사가 아닐 수도 있습니다.
앨런 B. 다우니의 Think Data Structures를 참고했습니다.
