[유니티 / C# ] 리스트(List)와 연결 리스트(Linked List)

⭐ 리스트 (List)

제네릭 동적 배열을 구현한 컬렉션 클래스입니다. 배열과 다르게 가변길이가 특징인 자료구조입니다.

 

 

List 특징

---

● 제네릭 타입

    ○ 리스트는 제네릭 타입으로 다양한 타입의 데이터를 저장할 수 있으며, 타입 안정성을 제공하여 컴파일 시간에

       타입 오류를 방지할 수 있습니다.

 

● 동적 배열

    ○ 요소를 추가하고 제거하는 동작이 자유롭습니다. → 가변 길이

 

● 인덱스

    ○ 인덱스를 사용해 원하는 요소에 바로 접근할 수 있습니다.

 

 

List 선언 방식

---

//기본 선언 형식
List<T> 리스트명 = new List<T>();

//선언 예시
List<int> intList = new List<int>();
List<string> strList = new List<string>();
List<float> floatList = new List<float>();

● 리스트는 제네릭 형식이기 때문에 다양한 타입들로 선언 가능합니다.

    ○ 리스트는 많은 속성과 메서드를 지원합니다.

 

 

List의 속성

---

속성	설명
Count	현재 요소 수
Capacity	내부 배열의 크기 (자동 확장, 직접 설정 가능)
Item[index]	인덱서로 요소 접근/수정

 

//List 속성 사용 예제
List<int> numbers = new List<int> { 1, 6, 3, 8, 2 }; //List<int> 선언

Debug.Log(numbers.Count);       //5

Debug.Log(numbers.Capacity);    //8

numbers[1] = 9;
Debug.Log(numbers[1]);          //9

● numbers 리스트의 요소는 1, 6, 3, 8, 2 로 총 5개 입니다.

    ○ numbers.Count → numbers 요소의 개수는 5

 

● numsbers.Capacity는 내부 배열의 크기이므로 5라고 생각할 수 있습니다.

    ○ 하지만 로그를 확인해보면 8이 찍혀 있습니다. (* 아래에서 설명)

 

● numbers[1] = 9; 는 List 클래스에 선언되어 있는 인덱서를 통해 값을 대입한 것입니다.

    ○ 따라서 numbers[1] 의 요소 값은 9로 바뀌었습니다.

 

리스트 크기 할당에 관하여

리스트는 Add를 통해 요소가 추가될 경우, 내부 배열의 사이즈가 요소 개수보다 작으면
처음 할당할 때는 기본 크기인 4만큼 키우며 그 이후부터는 배열 사이즈 * 2 씩 크기를 늘려갑니다.
따라서 리스트의 크기는 4..8...16.... 순으로 커집니다.
직접 초기 용량을 설정해 줄 수도 있습니다.

//실제 리스트의 Add 메서드
public void Add(T item)
{
    if (_size == _items.Length)
    {
        EnsureCapacity(_size + 1);
    }

    _items[_size++] = item;
    _version++;
}

//EnsureCapacity 메서드
private void EnsureCapacity(int min)
{
    if (_items.Length < min)
    {
        int num = ((_items.Length == 0) ? 4 : (_items.Length * 2)); // 초기값이 4, 이후로는 *2
        if ((uint)num > 2146435071u)
        {
            num = 2146435071;
        }

        if (num < min)
        {
            num = min;
        }

        Capacity = num;
    }
}

 

 

List의 메서드

---

리스트에는 다양한 기능을 메서드를 통해 지원합니다.

그 중에서 요소 추가, 삭제와 같은 자주 사용하는 메서드들에 대해서 알아보겠습니다.

 

💡 요소 추가 / 삽입

메서드	설명
Add(T)	리스트의 맨 뒤에 요소를 추가
AddRange(IEnumerable<T>)	지정된 컬렉션의 요소를 리스트의 맨 뒤에 추가
Insert(Int32, T)	지정된 인덱스에 요소를 삽입
InsertRange(Int32,  Ienumerable<T>)	컬렉션의 요소를 지정된 인덱스에 삽입

 

 

 

💡 요소 삭제

메서드	설명
Remove(T)	첫 번째로 일치하는 요소 제거
RemoveAt(Int32)	지저된 인덱스에 있는 요소 제거
RemoveAll(Predicate<T>)	정의한 조건과 일치하는 모든 요소 제거
RemoveRange(Int32, Int32)	특정 인덱스부터 n개 만큼의 요소 제거
Clear()	리스트의 모든 요소 제거

 

 

 

💡 검색 / 조회

메서드	설명
Contains(T)	리스트에 특정 값 존재 여부를 판단 후 bool값 반환
Equals(object)	지정된 개체가 현재 개체와 같은지 여부를 확인 후 bool값 반환
Exists(Predicate<T>)	리스트에 조건과 일치하는 요소가 있는지 확인 후 bool값 반환
Find(Predicate<T>)	리스트에서 조건과 일치하는 가장 첫 요소 반환
FindAll(Predicate<T>)	리스트에서 조건과 일치하는 모든 요소 반환
FindLast(Predicate<T>)	리스트에서 조건과 일치하는 가장 마지막 요소 반환
IndexOf(T)	리스트에 지정된 개체가 있으면 해당 인덱스 반환 → 첫 요소 인덱스 반환
LastIndexOf(T)	리스트에 지정된 개체가 있으면 해당 인덱스 반환 → 마지막 요소 인덱스 반환

 

 

 

💡 정렬 / 변환

메서드	설명
Sort()	기본 비교자를 사용하여 오름차순 정렬
Reverse()	리스트를 역순으로 뒤집기
ToArray()	리스트 요소를 새 배열에 복사

 

 

 

⭐ 연결 리스트 (Linked List)

연결 리스트는 각 요소마다 다음 노드를 참조하는 주소를 가지고 있는 선형 자료구조입니다.

 

기존의 리스트는 인덱스를 통하여 빠른 접근이 가능하지만

각 요소의 삽입, 삭제 과정에서 해당 인덱스로부터 뒤의 요소들을 새로 복사하여 이어붙이기 때문에

성능적인 문제가 발생하게 됩니다.

연결 리스트는 위와 같은 리스트 요소의 삽입, 삭제와 관련된 동작을 수행하는데 좋은 퍼포먼스를 보여주는 자료구조입니다.

 

연결 리스트 종류

---

타입	구조	특징
단일 연결 리스트	각 노드가 다음 노드만 참조	구현 단순, 역방향 탐색 불가
이중 연결 리스트	이전, 다음 노드를 참조	양방향 탐색 가능, 메모리 사용 증가
원형 연결 리스트	마지막 노드가 첫 노드를 참조	순환 탐색 가능

 

 

 

연결 리스트 속성

---

 

속성	설명
Count	연결 리스트의 노드 수
First	첫 번째 노드
Last	마지막 노드

 

 

 

 

연결 리스트 메서드

---

 

💡 요소 추가 / 삽입

메서드	설명
AddFirst(T)	맨 앞에 새 노드 추가
AddLast(T)	맨 끝에 새 노드 추가
AddBefore(LinkedListNode <T>, T)	지정 노드 앞에 새 노드 추가
AddAfter(LinkedListNode<T>, T)	지정 노드 뒤에 새 노드 추가

 

 

 

💡 요소 삭제

메서드	설명
Remove(T)	지정된 값과 일치하는 첫 번째 노드 삭제
Remove(LinkedListNode <T>)	지정된 노드 삭제
RemoveFirst()	첫 번째 노드 삭제
RemoveLast()	마지막 노드 삭제
Clear()	모든 노드 삭제

 

 

 

💡 검색 / 조회

메서드	설명
Find(T)	해당 값과 일치하는 첫 번째 노드 반환 (없으면 null 반환)
FindLast(T)	해당 값과 일치하는 마지막 노드 반환 (없으면 null 반환)
Contains(T)	해당 값과 일치하는 요소가 있으면 true, 없으면 false 반환

 

 

 

⭐ 리스트와 연결 리스트 비교

● 리스트 → 인덱스를 통한 검색, 읽기에 적절

    ○ 인덱스를 통한 빠른 접근

    ○ 대량 연산, 정렬에 유리

    ○ 유틸적인 메서드가 다양함

 

● 연결 리스트 → 요소의 삽입, 삭제가 잦은 경우 적절

    ○ 요소의 삽입, 삭제가 빠름

    ○ 리스트의 크기 예측 불필요

 

 

연산	List<T>	LinkedList<T>	비고
인덱스 접근	O(1)	O(n)
순차 탐색	O(n)	O(n)
끝에 요소 추가 (Add)	O(1) / O(n)	O(1)	평균적인 경우로 측정
중간 삽입 / 삭제	O(n)	*O(1) / O(n)	*삽입/삭제할 노드를 이미 알고 있을 때 O(1)
처음 / 끝 삭제	O(n)	O(1)