List
정의
- 하나의 변수에 여러 값을 저장하기 위해서 불연속적인 메모리 공간을 차지하는 동적(Dynamic)인 자료구조이다.
- 데이터를 순차적으로 저장하는 자료구조이다.
- 배열이 가진 인덱스라는 장점을 버리고 빈틈없는 데이터 적재라는 장점을 취한 것이다.
특징
- 리스트는 순서가 있는 데이터들의 모임이다. 따라서 sequence라고도 부른다.
- index는 몇 번째의 데이터인가 정도의 의미를 가진다.
- 빈 엘리먼트를 허용하지 않는다.
- 중복을 허용한다.
- python의 list는 크기가 가변적이고, 어떤 원소 타입이던지 쉽게 저장할 수 있지만 그래서 많은 메모리가 필요하다.
in Kotlin
Kotlin에서 List는 두가지가 존재한다. 변화가 가능한 Mutable타입과 변화가 불가능한 Immutable타입이 존재한다.
Kotlin의 mutableListOf()와 listOf() 모두 기본 List생성 메서드는 기본으로 ArrayList를 사용한다
구현 방법
- 순차 자료구조: ArrayList
- 연결 자료구조: LinkedList
ArrayList
정의
- ArrayList는 내부가 배열(Array)형태로 된 List이다.
- 구현할 자료들을 논리적인 순서대로 메모리에 연속해서 저장하는 자료구조이다.
특징
- List의 추가 및 삭제가 가능한 성질을 위한 함수를 제공하면서, Array의 빠른 원소 접근이 가능하다.
- 데이터들을 순서대로 저장하기 때문에, 저장 시작 위치부터 빈 자리없이 순서대로 저장한다. 따라서 논리적인 순서와 물리적인 순서가 일치한다.
- 데이터의 삽입이나 삭제가 생기면, 연속적인 물리적 위치를 유지하기 위해서 원소를 옮기는 추가작업이 필요하다.
- 배열로 구현하기 때문에 인덱스를 통해서 접근이 가능하다.
- 찾고자 하는 원소의 위치를 알고 있다면 O(1)에 접근 가능하다. 즉, 무작위 접근(random access)이 가능하다.
삽입
- ArrayList는 List의 가변적인 성질을 위해서 초기에 일정량의 메모리 공간을 잡고 시작한다.
- 초기에 설정한 메모리가 가득찬다면 더 큰 메모리 공간을 잡아서 연산을 이어간다.
- 향후 값이 추가될 것을 대비하여 하나의 추가 공간이 아닌 일정 사이즈만큼 미리 메모리를 잡는다.
- 기존 공간을 이용하는 것이 아는 더 큰 메모리를 잡고 기존 메모리의 복사를 수행하게 된다.
- 이처럼, ArrayList는 사이즈가 고정되어 있기 때문에, 삽입 시에 사이즈를 늘려주는 연산이 추가되어야 한다.
- 이런 연산은 시스템의 성능 저하로 이어질 수 있다.
- 따라서 데이터들이 자주 변경되는 경우에는 사용하지 않는 것이 좋다.
- 삽입 과정
- List의 크기를 삽입될 자료만큼 늘리는 연산을 수행한다.
- 삽입될 자료의 위치를 기준으로 기존의 데이터를 뒤 또는 앞으로 이동하는 연산을 수행한다.
- 해당 위치에 자료를 입력한 후 삽입 연산을 마친다.
- 삽입 시간 복잡도 : O(1)
- ArrayList에 여유 공간이 있는 경우
삭제
- 자료들이 지속적을 삭제되는 과정에서 ArrayList에서는 그 공간만큼 낭비되는 메모리가 생긴다.
- 삭제 과정
- 삭제될 자료가 위치한 인덱스의 자료를 삭제한다.
- 삭제한 자료의 인덱스를 기준으로 이후의 자료들을 이동하는 연산을 수행한다.
- List의 맨 마지막은 비어있는 상태로 삭제를 완료한다.
- 삭제 시간 복잡도 : O(N)
- 이동하는 연산을 수행
in Kotlin
mutableListOf를 통해서 ArrayList를 생성한다.
val mutableList = mutableListOf<Int>(1,2,3)
mutableList[1]
// 검색 1
for (i in 0..mutableList.size)
if(mutableList[i] == 1)
println(mutableList[i])
// 검색 2 : 확장함수 이용
println(mutableList.find { it == 1 }
// 없는 경우 null
LinkedList
정의
- 각 원소가 자신의 앞과 뒤의 원소에 대한 참조를 가지고 있는 자료구조이다.
- 메모리에 저장된 물리적 위치나 순서에 상관없이, 링크에 의해서 논리적인 순서를 표현하는 자료구조이다.
- 메모리 공간에 모여있지 않고, 산재되어 있을 수 있다(non-continuous)
- 데이터 필드와 링크 필드를 가지는 Node라는 요소로 구성되어 있고, Node를 연결하여 만들어지는 리스트이다.
- 데이터 필드는 말 그대로 데이터를 저장하고, 링크 필드는 다음 노드를 가리키는 포인터를 저장한다.
특징
- 삽입, 삭제 시간 복잡도 : O(1)
- 특정 노드의 삽입이나 삭제를 할 때, 노드의 링크 필드(포인터)만 수정하면 되므로 빠르게 연산이 가능하다.
- 삽입해야 하는 위치를 찾아야 한다면 O(N)이 걸리게 된다.
- 무작위 접근이 불가능하고, 순차 접근만 가능하다.
- 절대 경로인 인덱스(index)를 통한 접근이 불가능하다.
- 이전의 노드를 통해서만 노드에 접근할 수 있기 때문에, 탐색을 하려면 처음부터 진행해야 한다.
- 순차 접근에서도 참조의 지역성때문에 LinkedList보다 ArrayList가 빠르다.
- n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어서 자료를 저장하지만, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장한다. 따라서 node들이 이곳저곳 산재되어 있어서 접근하는데 ArrayList보다 긴 지연 시간이 소모된다.
- 데이터 필드 이외에도 링크 필드를 위해 추가적인 메모리가 할당되므로 비실용적일 수 있다.
- 링크 포인터로 검색하므로 연속적인 기억 공간이 없더라도 노드의 저장이 가능하다.
- Tree 구조의 근간이 되는 자료구조이다.
안녕하세요