C# - 자료구조 : Indexer, List, LinkedList

자료구조(data Structure), 컨테이너(Container, 컬렉션(Collection) 모두 같은 맥락에서 사용되는 단어다.

 

인덱서 (Indexer)

클래스 내부의 요소나 기능을 마치 배열처럼 인덱스로 접근하게 해주는 기능이다.

Item[] items;

// [접근지정자] [반환형태] this [int i]
public Item this[int i]
{
	get { return items[i]; }
	set { items[i] = value; }
}

 

클래스 내에서 이런 형태로 만들어주면 된다.

 

기존에는 클래스 내에 있는 아이템을 가져오기 위해서는

Inventory myInven = new Inventory(10);

// 2번째 아이템 가져오는 기존 방법
Console.WriteLine( (myInven.GetInven()[2]).Name );
Console.WriteLine( myInven.Inven[2].Name );
Console.WriteLine( myInven.GetItem(2).Name );

 

프로퍼티로 직접 접근해서 가져오던

인벤토리를 통으로 건내주는 메서드를 만들어서 인덱스로 탐색하던

특정 인덱스의 아이템을 반환해주는 메서드를 사용하던

 

가독성도 그다지 좋지 않고 번거롭다.

 

하지만 인덱서를 적용해뒀다면

Console.WriteLine(myInven[2].Name);

 

좀 더 직관적이고 깔끔해진다.

 

이 인덱서와 제네릭 컨테이너를 같이 사용해서 예시 코드를 더 보도록 하자.

Ally와 Enemy 두 클래스를 받아 사용할 제네릭 클래스 Troop을 구성한다면

class Ally
{
    public string Name { get; set; }
}

class Enemy
{
    public string Name { get; set; }
}

class Troop<T> // 제네릭으로 Ally, Enemy에 모두 대응
{
    T[] army;

    public T this[int index] // 인덱서 활용
    {
        get { return army[index]; }
        set { army[index] = value; }
    }

    public Troop(int troopSize) // 생성자
    {
        army = new T[troopSize];
    }
}

class Program
{
    static void Main(string[] args)
    {
        Troop<Ally> myTeam = new Troop<Ally>(10);
        myTeam[0] = new Ally();
        myTeam[1] = new Ally();
        myTeam[2] = new Ally();
        myTeam[2].Name = "Saitama";

        Troop<Enemy> yourTeam = new Troop<Enemy>(10);
        yourTeam[0] = new Enemy();
        yourTeam[1] = new Enemy();
        yourTeam[2] = new Enemy();
        yourTeam[2].Name = "Kakarot";
    }
}

 

 

이렇게 작성할 수 있다.

코드의 재사용성과 가독성이 확실히 좋아졌다.

 

 

---

 

List<T>

기존의 배열은 크기가 정해져있어 Javascript를 하던 사람의 입장에서는 굉장히 불편했다.

그리고 그러한 배열의 불편함을 해결해준 List라는 것이 존재했다.

<T> 를 보면 알 수 있듯이 제네릭이 적용돼있으며 사실상 배열+인덱서의 업그레이드 버전이라고 봐도 된다.

List에 값이 들어오면 자동으로 크기를 조정하며, 다양한 메서드들을 제공하기 때문에 매우 유용하다.

 

List<int> myInts = new List<int>();
myInts.Add(1);
myInts.Add(2);
myInts.Add(3);

Console.WriteLine(myInts.Count);    // 현재 요소 개수
Console.WriteLine(myInts.Capacity); // 내부 배열 크기

 

 

List는 내부적으로 들어오는 배열 크기에 따라 Capacity라는 총 공간이 확보된 뒤,

Count 라는 실질 공간으로 관리된다.

이렇게 말하면 무슨 의미인지 잘 와닿지 않을 수 있는데

예를들어

현재 myInts[2] 까지만 Add가 돼있기 때문에 myInts[3] 이상에 접근하려 하면 에러가 반환된다.

 

배열을 넣을 공간(Capacity)이 확보 됐는데 왜 접근을 못해?

라고 당연히 의문이 들었다.

그래서 List를 뜯어보았는데...

public T this[int index]
{
    [__DynamicallyInvokable]
    get
    {
        if ((uint)index >= (uint)_size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }

        return _items[index];
    }
    [__DynamicallyInvokable]
    set
    {
        if ((uint)index >= (uint)_size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }

        _items[index] = value;
        _version++;
    }
}

 

이렇게 구성돼있다.

즉, 입력한 index가 _size(Count, 즉 실제 값이 있는 요소 수) 보다 큰 경우 예외처리를 해두었다.

 

Capacity가 이미 공간을 확보했으니 컴파일러가 터지는 건 아닐텐데 왜 이런 예외처리를 했을까...

예상되는 이유로는 리스트 중간에 빈 값이 존재하길 원치 않았기 때문인 거 같은데

정답을 아는 분이 있다면 공유 부탁드립니다.

 

List에서 자주 쓰이는 메서드

Add(item)	리스트 끝에 요소 추가	입력 데이터를 동적으로 수집
AddRange(collection)	다른 컬렉션을 한 번에 추가	배열 → 리스트 변환 시
Insert(index, item)	특정 인덱스 위치에 요소 삽입	중간 삽입
Remove(item)	해당 값을 찾아 제거 (첫 번째 항목만)	특정 원소 제거
RemoveAt(index)	해당 인덱스의 요소 제거	조건에 맞는 인덱스 삭제
RemoveAll(predicate)	조건에 맞는 모든 요소 제거	필터링
Clear()	모든 요소 삭제	초기화 시
Contains(item)	리스트에 해당 값이 있는지 확인	탐색 문제
IndexOf(item)	값의 인덱스 반환 (없으면 -1)	위치 찾기
LastIndexOf(item)	마지막으로 등장한 인덱스 반환	뒤에서 탐색
Find(predicate)	조건을 만족하는 첫 번째 요소 반환	최소/특정 값 찾기
FindAll(predicate)	조건을 만족하는 모든 요소 반환 (List로)	조건 필터링
FindIndex(predicate)	조건을 만족하는 첫 번째 요소 인덱스	위치 기반 탐색
FindLast(predicate)	조건을 만족하는 마지막 요소 반환	뒤에서 조건 찾기
Sort()	오름차순 정렬	정렬 문제
Sort(comparer)	사용자 정의 정렬 기준으로 정렬	커스텀 정렬
Reverse()	순서를 뒤집음	역순 문제
BinarySearch(item)	이진 탐색 (정렬된 리스트 전제)	빠른 탐색
Exists(predicate)	조건을 만족하는 요소가 있는지 여부	조건 충족 여부 검사
ForEach(action)	각 요소에 대해 액션 수행	디버깅 출력/배치 연산
ToArray()	리스트를 배열로 변환	함수 매개변수 전달 시
GetRange(index, count)	특정 범위를 잘라서 새로운 리스트 반환	슬라이싱
ConvertAll(converter)	리스트의 모든 요소를 다른 형식으로 변환	형 변환, 매핑

 

 

 

2차원 List

다차원 배열이 가능하듯이 다차원 List도 가능하다.

List<List<int>> twoDim = new List<List<int>>();

twoDim.Add(new List<int>());
twoDim.Add(new List<int>());
twoDim.Add(new List<int>());

twoDim[0].Add(1);       // 첫 줄 첫 칸에 값 추가
Console.WriteLine(twoDim[0][0]); // 접근

 

 

단 List는 가변형이기에 정사각 행렬 같은 형태는 보장받기 어려우니 적절한 상황에 맞춰 쓰도록 하자.

 

 

 

LinkedList<T>

List는 내부적으로 연속적으로 이어져있는 배열을 사용하기 때문에, 중간에 데이터를 삽입 / 삭제 시 문제가 있다.

삭제의 상황을 예로 들면

1

2

3

4

5

 

이런 List가 있다 가정했을 때, 리스트.Remove(3), 즉 3을 제거한다고 가정해보자.

그러면 List는 3을 제거하는 것이 아닌, 3 뒷자리 모든 배열을 복사해서 붙여넣고, _size(Count)를 줄인다.

1

2

4

5

5

 

즉 이런 형태가 되지만 _size가 줄었기 때문에 맨 뒤에 5는 접근할 수 없는 상태가 되는, 삭제라기 보단 비활성화에 가까운 상태가 된다.

 

중간에 값이 추가 될 때도 같은 방식으로

1

2

3

4

5

 

리스트.Inser(2, 10) 으로 2번 인덱스 자리에 10 값을 넣는다면

1

2

10

3

4

5

 

이렇게 10을 넣고 뒤쪽에 3, 4, 5를 복사해서 넣는 형태가 된다.

 

이게 무엇인 문제인데 호들갑이냐고 할 수도 있지만 지금은 고작해야 몇개 몇십개의 데이터니까 그러지

수천, 수만개의 리스트가 몇번이고 변경되는 상황이 발생한다면 어마어마한 비용이 발생할 것이다.

최적화가 중요한 게임에서는 큰일 날 일이다.

 

그리고 이런 상황을 위해 존재하는 것이 LinkedList 다.

LinkedList는 데이터와 데이터가 연결은 되어있지만 연속적으로 연결되어 있지 않고, 데이터는 각각 다음/이전 데이터의 주소값을 들고 있는 방식이다.

본인 값, 다음 위치, 이전 위치 3가지 데이터를 갖고있는 Node가 연결돼있는 형태라고 보면 된다.

그래서 List에 비해 중간에 삭제하거나 추가해도, 다음 값을 가리키는 데이터만 수정하면 되므로 수정시 부하가 List에 비해 가볍다.

단점으로는 다음 리스트 값이 무엇인이 찾으려면 차례대로 주소값을 추적하면서 탐색해야하기 때문에 검색 속도가 느리다.

 

 

 

아래는 LinkedList의 동작의 이해를 위해 수업 시간에 Node를 구현해본 코드다.

 

using System;
using System.Collections.Generic;

namespace LinkedList
{
    public class Node<T>
    {
        public T Value { get; set; }
        public Node<T> Next { get; set; }

        public Node(T value)
        {
            Value = value; // 데이터를 넣고 있네?
            Next = null; // 일단 다음 없음
        }
    }

    class LinkedList2<T>
    {
        public int Count { get; private set; } // 그냥 노드 갯수
        public Node<T> Head { get; private set; } // NodeT 형식의 주소를 기억할 수 있는 헤드란 이름의 껍데기

        public LinkedList2()
        {
            Head = null; // 명시적으로 머리 비움
            Count = 0; // 링크드리스트 만들어질 때 0
        }

        //Add Last
        // 만약 헤드가 null 이면? 맨 처음에 추가된 노드가 시작과 동시에 헤드
        // 그렇지 않다면 현재 마지막 노드를 찾아서 뒤에 연결

        public void AddLast(T value)
        {
            Node<T> newNode = new Node<T>(value); // Add 지시 받았으니 노드 새거 하나 생성

            if (Head == null ) // 최초 실행시, Head가 null 일 것임
            {
                Head = newNode; // 처음 추가된 노드를 헤드에더 주소 복사해 줌
            }
            else
            {
                Node<T> current; // 노드의 주소를 임시로 기억할 껍데기 생성
                current = Head; // else 문에 들어왔다는 뜻은, Head에 무언가 값이 있다는 뜻
                // 고로 이걸 임시 current에 복사했음

                //1. 맨 처음엔 헤드가 들어있다
                //2. 헤드의 Next가 만약 널이 아니라면 반복수행
                while ( current.Next != null )
                {
                    current = current.Next;
                }
                current.Next = newNode;
            }
            Count++;
        }

        // 지정된 값을 가진 노드를 찾아서 제거
        // 삭제 성공 여부를 bool로 반환
        public bool Remove(T value)
        {
            if(Head == null) // 머리 비었따면 or count가 0일떄
            {
                return false;
            }

            // 헤드 속에 있는 값이 우항과 같다면?
            //if(Head.Value == value)
            if (Head.Value.Equals(value)) // T같이 내용을 모를 때에는 Equals로 비교
            {
                Head = Head.Next; // 머리 다음 대상이 이제 머리
                Count--; // 숫자 줄이고
                return true;
            }

            //헤드가 아니고 중간, 또는 끝 노드 탐색
            Node<T> current = Head; // 일단 머리에 적힌 주소를 임시 current에 주소 복사해서 기억

            // 앞에 것도 참이고 뒤에것도 참일 때
            while(current.Next != null && !current.Next.Value.Equals(value))
            {
                current = current.Next; // AddLast와 비슷하게, 다음 노드로 옮겨감
            }

            if(current.Next == null)
            {
                return false;
            }

            // 삭제처리
            current.Next = current.Next.Next; // 그냥 이렇게 연결 끊어주면 GC가 알아서 지움
            Count--;

            return true;
        }

        // 노드 찾기
        public Node<T> Find(T value)
        {
            Node<T> current = Head; // 항상 헤드 시작

            while (current != null)
            {
                if(current.Value.Equals(value))
                {
                    return current;
                }
                current = current.Next;
            }
            return null;
            // 현재 노드가 null이 아닌 동안 현재 값가 같은 것들을 찾아 리턴하거나, 없으면 다음으로 이동
            // 끝까지 가도 없으면 null 반환
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            // 검증
            LinkedList2<int> myLList = new LinkedList2<int>();

            //추가 테스트
            myLList.AddLast(1);
            myLList.AddLast(2);
            myLList.AddLast(3);

            // 출력
            Node<int> current;
            current = myLList.Head;
            while(current != null)
            {
                Console.WriteLine(current.Value);
                current = current.Next;
            }


            Console.WriteLine("---제거테스트---");
            // 제거 테스트
            myLList.Remove(2);
            
            current = myLList.Head;
            while(current != null)
            {
                Console.WriteLine(current.Value);
                current = current.Next;
            }
        }
    }
}