🎵 C#, Unity | Part 2 - 섹션 1. 선형 자료 기초

배열, 동적배열, 연결 리스트 비교

선형 구조
선형 구조는 자료를 순차적으로 나열한 형태

• 배열
• 연결리스트
• 스택 / 큐

비선형 구조
비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

• 트리
• 그래프

/ 구분선 /

배열 :

• 사용할 방 개수를 고정해서 계약하고 (절대 변경 불가)
• 연속된 방으로 배정 받아 사용
  장점 : 연속된 방
  단점 : 방을 추가/축소 불가

동적 배열 :

• 사용할 방 개수를 유동적으로 계약
• 연속된 방으로 배정 받아 사용
  문제점 : 이사 비용은 어떻게 처리하나?
  동적 배열 할당 정책 :
• 실제로 사용할 방보다 많이, 여유분을 두고 (대략 1.5~2배) 예약
• 이사 횟수를 최소화
  장점 : 유동적인 계약 (방 추가 예약으로 이사 횟수 최소화)
  단점 : 중간 삽입/삭제가 어렵다.

연결 리스트 :

• 연속되지 않은 방을 사용
  장점 : 중간 추가/삭제 이점
  단점 : N번째 방을 바로 찾을 수가 없음 (임의 접근 Random Access불가)

동적 배열 구현 연습

class MyList<T> //리스트는 제네릭형식이므로<T>를 넣어준다
{
    const int DEFAULTSize = 1; // 배열의 사이즈 선언
    T[] _data = new T[DEFAULTSize]; // 배열 선언

    public int Count = 0; // 실제로 사용중인 데이터 개수
    public int Capacity { get { return _data.Length; } } // 예약된 데이터 개수

    // 시간 복잡도 : 0(1) 예외 케이스 : 이사 비용은 무시한다.
    public void Add(T item) // 데이터 추가
    {
        // 1. 공간이 충분히 남아 있는지 확인한다.
        if (Count >= Capacity)
        {
            // 공간을 늘려서 다시 확보한다
            T[] newArray = new T[Count * 2];
            for (int i = 0; i < Count; i++) //이사를 시켜준다
            {
                newArray[i] = _data[i];
            }
            _data = newArray;
        }
        // 2. (공간이 확보되었다고 가정시) 공간에다가 데이터를 넣어준다.
        _data[Count] = item;
        Count++;
    }

    // 시간 복잡도 : 0(1)
    public T this[int index] // 인덱서를 구현하는 부분
    {
        get { return _data[index]; }
        set { _data[index] = value; }
    }

    // 시간 복잡도 : 0(N)
    public void ReoteAt(int index)
    {
        // 101 102 103 104 105번 방이 있을 시
        // 103 번방을 지울때 (*103이 없어질 떄*) 104 /105를 앞으로 가져온다
        for (int i = index; i < Count - 1; i++)
            _data[i] = _data[Count + 1];
        _data[Count - 1] = default(T);
        Count--;
    }
}

public void Initialize()
{
        // 동적 배열 
        _data2.Add(101);
        _data2.Add(102);
        _data2.Add(103);
        _data2.Add(104);
        _data2.Add(105);

        int temp = _data2[2];
        // 데이터 추가
        // 인덱서를 이용해서 데이터를 추출한다
        // 103이 추출된다.

        _data2.RemoveAt(2);
        // 데이터 삭제
        // 몇번째 데이터를 삭제한다.
}

연결리스트 구현 연습

public void Initialize()
{
        // 연결 리스트
        _data3.AddLast(101);
        _data3.AddLast(102);
        LinkedListNode<int> node = _data3.AddLast(103);
        _data3.AddLast(104);
        _data3.AddLast(105);
  	
  	_data3.Remove(node);
}

class MyLinkedListNode<T>
{
        public T Data;
        public MyLinkedListNode<T> Next; // 다음 방
        public MyLinkedListNode<T> Prev; // 이전방
}

    class MyLinkedList<T>
    {
        public MyLinkedListNode<T> Head = null; // 첫번째
        public MyLinkedListNode<T> Tail = null; // 마지막
        public int Count = 0;

  	// 시간 복잡도는 0(1)
        public MyLinkedListNode<T> AddLast(T data) // 새로운 방을 달라고 요구할 때에
        {
            MyLinkedListNode<T> newRoom = new MyLinkedListNode<T>(); // 새로 만든 방
            newRoom.Data = data; // 데이터를 넣어준다.

            // 만약에 아직 방이 아예 없었다면, 새로 추가한 방이 곧 Head이다.
            if (Head == null)
            { 
                Head = newRoom;
            }

            // 101, 102, 103, 만 있다가 104가 추가되면 104가 끝이다.
            // 기존의 [마지막 방]과 [새로 추가 되는 방]을 연결해준다.
            if (Tail != null)
            {
                Tail.Next = newRoom;
                newRoom.Prev = Tail;
            }

            // [새로 추가되는 방]을 [마지막 방]으로 인정한다.
            Tail = newRoom;
            Count++;
            return newRoom;
        }
  
	// 시간 복잡도는 0(1)
        // 101 102 103 104 105
        public void Remove(MyLinkedListNode<T> room)
        {
            // [기존의 첫번째 방의 다음 방]을 [첫번째 방으로] 인정한다.
            if (Head == room)
                Head = Head.Next;

            // [기존의 마지막 방의 이전 방]을 [마지막 방으로] 인정한다.
            if (Tail == room)
                Tail = Tail.Prev;

            // 이전의 방이 있다면 이전 방의 다음 방을 연결한다
            // 103번을 삭제할때 102번과 104번을 연결한다
            if (room.Prev != null)
                room.Prev.Next = room.Next;

            if (room.Next != null)
                room.Next.Prev = room.Prev;

            Count--;
        }
    }