리스트(List)

개념

처음부터 고정된 크기로 선언하는 정적 배열과 달리 런타임에 크기가 동적으로 변할 수 있는 동적 배열이다

정적 배열의 한계를 극복하기 위해 나타났으며 C#에서는 System.Collections.Generic 네임스페이스의 List<T> 클래스를 사용하여 리스트를 구현한다

• 동적 배열이라 원소를 추가하고 제거하는 동작이 자유롭다. 원소를 추가하고 제거할 때 자동으로 크기가 조절된다
• 제네릭 타입을 사용하여 리스트를 선언할 때 지정한 타입의 원소만 추가할 수 있다. 타입 안정성이 높아진다
  • 타입 안정성이란?
    • 변수가 할당되거나 연산되는 동안 타입 간의 일관성과 유효성을 보장하는 개념. 프로그램이 타입 오류를 방지하고, 프로그램이 컴파일러나 런타임 환경에서 안전하게 작동하도록 함
    • 내가 이해한 바로는 코드 상에서 변수의 타입을 명시적으로 선언하고 캐스팅할 때도 명시적으로 표현해야된다고 이해함
• 여러 메서드를 제공함

선언과 초기화

유니티에서 리스트를 선언하고 초기화하는 방법을 알아보자

전반적으로 배열과 비슷한 방식으로 초기화된다

// 선언과 초기화
// 다음과 같이 초기화하면 개수가 0인 리스트임(intList를 참조해도 null이 아님)
public List<int> intList = new List<int>();

// 다음과 같이 선언하고 intList1를 참조하면 어떻게 될까?
// null 참조 에러일 것 같지만 public이라 인스펙터에서 이미 초기화된 것으로 보고 개수가 0인 리스트임 -> 유니티의 직렬화 시스템 때문
// public 없이 참조하면 null 참조임
public List<int> intList1;

// 리스트도 초기 용량을 설정할 수 있다
List<int> intList = new List<int>(100);  // 초기 용량을 100으로 설정함

// 중괄호 초기화 가능
List<int> intList = new List<int>(){1, 2, 3, 4};

리스트의 초기 용량을 100으로 설정했으면 리스트의 개수는 100이라고 생각할 지 모르지만 100이 아니다

배열은 초기화할 때 크기를 미리 지정해주면 기본값들이 채워지면서 길이를 구하면 제대로 나오는데 리스트는 왜 그럴까?

앞에서 말했듯이 리스트는 동적 배열이며 자료를 추가할 때 크기 조정을 하면서 메모리를 새로 할당하는 시스템이다. 초기 용량이 정해지며 현재 용량이 꽉 찼는데 자료를 추가하면 용량을 늘려 메모리를 새로 할당하는 식임

즉, 우리가 초기화 시 정해주는 정수는 Capacity이며, 이 리스트가 Capacity만큼 자료를 저장하는 동안은 메모리를 새로 할당하는 일이 없다. 초기 용량 설정 없이 리스트에 계속 데이터를 추가하면 메모리는 용량이 넘칠때마다 새로 할당해야 하고 이런 과정에서 성능 저하가 발생하니 미리 리스트의 Capacity를 생각해 지정해주는 것이 좋을 것 같다

예제

intList = new List<int>();

int capacity = intList.Capacity;
Debug.Log(capacity);

for(int i = 0; i < 100; i++)
{
    intList.Add(i);
    if(capacity != intList.Capacity)
    {
        capacity = intList.Capacity;
        Debug.Log(capacity);
    }
}

// 초기 용량 : 0
// 리스트에 데이터를 추가하면서 capacity가 달라질때마다 capacity를 출력했다
// 결과 : 4 8 16 32 64 128
// 2배씩 용량이 늘어나면서 메모리를 새로 할당한다

리스트 개수

리스트의 개수는 다음과 같이 구할 수 있음

intList.Count;

리스트 활용

List<int> intList = new List<int>() {1, 2, 3};

리스트에 데이터 추가

리스트를 만들었으니 이제 데이터를 추가해보자. 리스트 자체가 동적 배열이므로 여러 방법으로 데이터를 추가할 수 있다

Add

가장 기본적으로 리스트의 끝에 데이터를 추가하는 방법

intList.Add(10);

// 1 2 3 10

AddRange

리스트의 끝에 다른 컬렉션(배열, 리스트)를 추가할 수 있다(여러 데이터를 추가할 수 있음)

List<int> intList1 = new List<int>(){1, 2, 3};
intList.AddRange(intList1);
// 1 2 3 1 2 3

int[] intArray = new int[]{1, 2, 3, 4};
intList.AddRange(intArray);
// 1 2 3 1 2 3 4

만약 리스트에 100만개의 데이터를 추가할 때 반복문을 이용해 매번 Add 함수로 추가하는 것과 100만개의 데이터가 담긴 컬렉션을 AddRange로 추가하는 것 중 어떤 것을 선택해야 할까??

당연하겠지만 AddRange 함수이다. 함수 호출의 오버헤드도 생각하고 리스트의 Capacity가 다 차면 새로 할당하는 것도 비용이 크기 때문임

Insert

앞에서 본 두 함수는 모두 리스트의 끝에 데이터를 추가하는 함수인데 Insert 함수는 리스트 중간에 데이터를 추가할 수 있다

// 1번째 인덱스에 10을 추가한다
// 원래 1번째 인덱스에 2가 있었는데 뒤로 한 칸씩 밀리게 됨
intList.Insert(1, 10);
// 1 10 2 3

중간에 데이터를 추가하면 그 뒤에 있는 데이터들을 뒤로 미뤄야 하기 때문에 최악의 경우 O(n)의 시간 복잡도가 걸림

인덱스를 추가할 때 리스트의 범위를 벗어나면 에러가 나니까 고려하기

InsertRange 함수도 있는데 이건 생략

데이터 삭제

Remove

리스트의 타입에 맞는 데이터와 일치하는 첫 번째 데이터를 삭제한다. 삭제를 했으면 true, 일치하는 데이터가 없어서 삭제를 못했으면 false를 반환

요소를 찾아서 제거한 후 나머지 요소들을 이동시켜야 하기 때문에 O(n)의 시간 복잡도를 가진다

bool result = intList.Remove(2);
Debug.Log(result);
// true
// 1 3

RemoveAt

Remove가 특정 데이터를 찾아 삭제하는 것이라면 RemoveAt은 인자로 받은 해당 인덱스의 데이터를 삭제하는 함수이다. 반환값은 없다

리스트의 끝을 삭제하는 것이면 O(1)이지만 리스트의 중간을 삭제하는 것이면 O(n)이 걸림

// 리스트 끝에 있는 데이터를 삭제
intList.RemoveAt(intList.Count - 1);

// 1 2

RemoveAll

해당 조건에 맞는 모든 요소를 삭제한다. 보통 람다 함수를 이용해 삭제 조건을 전달
삭제하고 옮겨야 하기에 O(n)

intList.RemoveAll(x => x > 1);
// 1 

RemoveRange

리스트의 특정 범위에 있는 요소들을 삭제함. 삭제하고 옮겨야 하기에 O(n)

// 1번째 인덱스부터 시작해 2개를 지워라
intList.RemoveRange(1, 2);
// 1

Clear

리스트의 모든 요소를 삭제하는 함수. 빈 리스트로 만들어버린다(참조해도 null 참조는 아님)
리스트의 크기를 0으로 설정하므로 O(1)의 시간 복잡도(Capacity는 변하지 않음 -> 메모리가 해제되지 않음)

intList.Clear();
// 

리스트를 Clear하고 재사용할 생각이 있으면 그대로 두고 만약 재사용없이 용량을 줄이고 싶으면 TrimExcess 함수를 사용한다

배열에도 있는 함수

배열과 똑같은 기능을 하는 함수들은 따로 적진 않고 언급만 하고 가겠다

• Contains => Exits와 비슷한데 bool 반환
• IndexOf
• Find
• FindAll
• FindIndex
• Sort
• Reverse
• `BinarySearch'

배열을 리스트로 / 리스트를 배열로

리스트를 배열로 바꾸는 함수 : ToArray

int[] intArray;
intArray = intList.ToArray();

배열을 리스트로

List<int> intList1 = new List<int>()

정리

리스트에 저장되는 데이터는 배열과 똑같은 구조로 저장되긴 하는데 크기가 변할 수 있는 동적 배열이다. 그래서 메모리에 연속된 공간에 저장됨

하지만 데이터를 추가할 때 메모리 용량보다 더 많아진다면 새로 메모리 공간을 확보해 할당하므로 적당한 용량 내에서 사용하는 것이 비용을 아낄 수 있을 것이다

ArrayList

이전부터 ArrayList라는 존재자체는 알고 있었는데 정확히 무엇을 위한 자료구조인지는 몰랐다. 그냥 배열아닌가?라고 생각했었는데 공부해보니까 아니었네

개념

C#에서 제공하는 비제네릭 컬렉션 클래스 중 하나로, System.Collections 네임스페이스에 포함되어 있다

List와 마찬가지로 크기를 동적으로 조정할 수 있는 가변 배열이며 List와 다른 점으로 다양한 타입의 객체를 저장할 수 있다. List<T>와는 다르게 비제네릭이기 때문에 타입 안정성이 보장되지 않는다

다른 타입들을 저장할 수 있는 이유는 모든 타입을 object로 박싱해서 저장하고 꺼내쓸 때 원래 타입으로 언박싱하기 때문임

그래서 위험할 수 있는 자료구조라 List<T>가 단점을 보완해 같은 타입을 저장하게 했다. 그래서 ArrayList를 권장하지 않는 분위기

List와 함수 자체는 비슷하니까 따로 적지 않고 그냥 ArrayList보다는 List를 애용하기로 하자!

LinkedList

컴공이라면 한번 쯤 들어봤을 연결 리스트다. 유니티도 링크드 리스트를 지원하며 제네릭 타입으로 System.Collections.Generic 네임스페이스에 있으며 양방향 연결 리스트로 구현되어 있음

각 데이터가 노드라고 불리는 요소로 되어 있으며 각 노드는 앞 노드와 뒷 노드를 참조한다. 데이터를 추가하거나 삭제할 때 효율적으로 작업할 수 있다(배열의 경우 데이터를 중간에 추가하거나 삭제하면 빈자리를 메꿔줘야 함)

각 노드는 LinkedListNode<T> 클래스이다. 크기도 동적으로 조절이 가능함

선언&초기화

다른 자료구조와 마찬가지로 new 키워드를 사용해 선언과 초기화를 할 수 있다. 링크드 리스트도 유니티에서 자동으로 직렬화 안되므로 초기화 필요

public LinkedList<int> intList = new LinkedList<int>();

// 링크드 리스트는 초기화 시 미리 용량을 지정해주지 못함
// 리스트와 같은 다른 자료구조는 내부적으로 배열을 사용해 요소를 저장하고 메모리를 연속해 사용하기 때문에 사전에 용량을 지정하면 효율적으로 메모리를 관리할 수 있음
// 링크드 리스트는 노드라는 개별 객체를 사용해 요소를 저장하고 메모리를 연속적으로 할당하지 않는 흩어져 있는 구조이기 때문에 용량을 지정하는 것이 의미가 없음

// 하지만 다른 컬렉션으로 미리 초기화가 가능하다
int[] intArray = new int[] {1, 2, 3};
intList = new LinkedList<int>(intArray);

// 1 2 3

함수

Find(T value)

링크드 리스트는 [] 연산자를 제공하지 않으므로 다음 함수를 써서 참조해야 함
링크드 리스트에서 value에 해당하는 첫 번째 노드를 찾아서 반환한다. FindLast라면 데이터와 일치하는 마지막 노드를 반환한다

만약 일치하는 노드가 없다면 null을 반환함

LinkedListNode<int> foundNode = intList.Find(2);

AddFirst(T value)

링크드 리스트의 처음 부분에 데이터를 추가한다

intList.AddFirst(0);

// 0 1 2 3

AddLast(T value)

링크드 리스트의 마지막에 데이터를 추가한다

intList.AddLast(4);

// 1 2 3 4

AddBefore(LinkedListNode node, T value)

첫 번째 매개변수로 넘겨준 노드 앞에 value 값을 가진 노드를 추가함

intList.AddBefore(intList.Find(2), 5);

// 1 5 2 3

AddAfter(LinkedListNode node, T value)

첫 번째 매개변수로 넘겨준 노드 뒤에 value 값을 가진 노드를 추가함

intList.AddAfter(intList.Find(2), 5);

// 1 2 5 3

Remove(T value)

value에 해당하는 노드를 삭제한다. 성공했으면 true, 실패했으면 false를 반환한다

intList.Remove(2);

// 1 3

RemoveFirst/RemoveLast

각각 리스트의 첫 번째 / 마지막 노드를 삭제한다. 리스트가 비어있을 때 사용하면 에러

intList.RemoveFirst();
intList.RemoveLast();

// 2

Contains(T value)

리스트에 value에 해당하는 노드가 있는지 true/false 반환 -> Find 쓰는게 나을듯?

Clear

리스트의 모든 노드들을 날려버리는 함수

First / Last

리스트에서 첫 번째 노드와 마지막 노드를 반환하는 프로퍼티

var firstNode = intList.First;
var lastNode = intList.Last;

// 값을 바로 변경할 수 없고 Value 프로퍼티를 이용해 변경해줘야 함
intList.First = 0; // X
intList.Last.Value = 2;  // O

Count

리스트의 노드 개수를 반환하는 프로퍼티

링크드 리스트 vs 배열 vs 리스트

링크드 리스트와 배열, 리스트의 차이를 살펴보자

배열, 리스트는 내부적으로 배열을 이용해 데이터를 저장함. 배열은 연속된 메모리를 사용하고 링크드 리스트는 메모리들이 흩어져있고 이 메모리들 앞 뒤로 전과 후를 알고있는 구조임

배열

배열은 초기화 시 고정된 크기를 가지며 동적으로 크기를 조정할 수 없다. 연속적인 메모리 블록을 할당하므로 인덱스 기반 접근 시 O(1)의 시간 복잡도로 요소에 접근할 수 있다

장점으로 인덱스를 통해 빠르게 접근이 가능하며 메모리 사용 효율이 높고 단점으로는 크기가 고정되어 있어 동적으로 크기 변경이 불가하며 중간에 요소를 삽입하고 삭제하는 과정이 비효율적이다

그래서 크기가 고정되어 있는 자료구조일 때 사용하면 좋으며 행렬 계산이나 고정된 크기의 버퍼를 사용할 때 사용하면 좋다

리스트

필요에 따라 크기를 동적으로 변경할 수 있으며 내부적으로 배열을 사용하고 배열이 가득 차면 새로 메모리를 할당해 요소들을 복사한다. 내부적으로 배열을 사용하니 배열과 똑같이 인덱스를 사용해 빠른 접근이 가능함

장점으로 동적 크기 조정 가능, 인덱스를 통한 빠른 접근, 다양한 메서드와 유연성을 제공하고 단점으로 크기 조정 시 내부적으로 배열 복사가 필요하므로, 많은 요소가 추가될 때 성능이 저하될 수 있고 중간에 요소를 삽입하거나 삭제하는 것도 비효율적이다

동적으로 크기가 바뀌는 데이터일 때 사용하면 좋을 것임

링크드 리스트

연속적인 메모리 블록이 아닌 각 요소가 노드이며 이 노드들은 흩어져 있지만 각 노드는 이전 노드와 다음 노드를 참조한다. 노드를 동적으로 추가하고 삭제할 수 있음

장점으로 리스트의 처음과 끝, 중간에 요소를 추가하거나 삭제하는 것이 빨라(O(1)의 시간 복잡도) 동적 크기 조정이 매우 효율적이며 단점으로 인덱스를 통한 접근이 비효율적(O(n) 시간 복잡도)이며 각 노드가 추가적인 메모리를 사용하므로 메모리 오버헤드가 크다

리스트에 삽입과 삭제가 자주 일어날 때 사용하면 좋겠다