[List 자료구조] 1. 코틀린의 리스트(List) 자료구조

목표

• 리스트의 특징을 이해한다.
• 코틀린에서 리스트가 구현된 방식을 안다.

---

리스트(List)

리스트(List)란 하나의 변수에 여러 값을 저장하기 위해 불연속적인 메모리 공간을 차지하는 동적(Dynamic)인 자료구조이다.

 

개요

 리스트는 여러 값을 저장하기 위해 메모리의 불연속적인 공간을 차지하고 있다. 불연속적인 공간을 차지하고 있으므로, 다음 값을 넣기 위해서는 비어있는 메모리 공간 어느 곳에나 변수를 넣으면 된다. 해당 주소값을 리스트에 추가 함으로써 리스트에 값 인스턴스의 추가가 완료된다.

 

 Kotlin에서 사용하는 List는 두가지 관점에서 나눌 수 있다. 하나는 가변성이고 다른 하나는 자료구조이다.

 

 가변성은 변화 가능(Mutable)한지 아니면, 불가능한지(Immutable)에 대한 성질이며, Kotlin은 Mutable한 List와 Immutable한 List를 모두 제공해준다. Kotlin Collection의 가변성에 대한 추가적인 자료가 필요하다면 아래 글을 참조하자.

[Kotlin Collection] 살펴보기

 자료구조는 데이터가 어떻게 구조화 되어있는지에 대한 것이다. 데이터 구조에 따라 데이터 접근, 검색, 추가, 삭제를 위한 시간 복잡도가 달라질 수 있다. 데이터가 많아질 수록 자료구조는 성능과 직결되기 때문에 중요해진다. 이 글에서는 List의 대표적인 두가지 자료구조를 다룰 것이다.

 

자료구조적 관점에서의 List

자료구조적인 관점에서 List를 살펴보면 Kotlin의 List는 두가지로 나뉜다. 하나는 ArrayList이고 다른 하나는 LinkedList이다.

*Kotlin에서 Java의 JCF(Java Collection Framework)을 사용하기 때문에 Java의 자료구조를 사용한다.

 

ArrayList

ArrayList는 Array의 성질을 가진 List로 Array의 유용한 성질을 가져와 만들어진 List이다. ArrayList는 List의 성질인 변수 추가 및 삭제를 위한 함수를 제공하면서도 Array의 성질인 원소 접근에 뛰어난 성능을 보인다. Kotlin에서는 List 생성 메서드에 대한 기본 구현체로 ArrayList를 사용하고 있다. 

 

Kotlin의 mutableListOf<T>()와 listOf<T>()를 이용해 생성되는 객체는 모두 ArrayList이다. 

코틀린의 List 생성에 대한 기본 List구현체는 ArrayList이다.

ArrayList의 자세한 특징과 시간 복잡도는 조금 길어서 별도의 글에 정리하였다.

 

[List 자료구조] 2. ArrayList

 

 

 

LinkedList

LinkedList는 각 List의 원소가 자신의 앞과 뒤 원소에 대한 참조를 저장하고 있는 구조의 List이다. 이러한 구조적 특징으로 인해 List의 원소에 접근하기 위해서는 절대 경로인 Index를 이용해 곧바로 접근이 불가능하고 맨 앞원소 혹은 맨 뒤의 원소부터 하나하나 타고 들어가야 해서 시간이 오래 걸린다. 하지만, 이러한 성질로 인해 원소의 추가와 삭제가 간편해지는 성질을 가진 List이다.