👱‍♀️ ansohxxn

👱‍♀️ ansohxxn

개인적인 필기 노트

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

Date:     Updated:

카테고리:

태그:

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

선형 자료 구조

데이터들을 일렬로 나열된 형태로 저장하고 싶을 때 사용하는 자료 구조

  • 선형 자료 구조 👉 자료를 순차적으로 나열
    • 배열
    • 동적 배열
    • 연결 리스트
  • 비선형 자료 구조 👉 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태
    • 트리
    • 그래프


🚖 배열

설명

  • 특징
    • 반드시 선언시 크기를 결정해야하며
    • 배열의 크기는 고정적이며 절대 변경할 수 없다.
    • 메모리 상에서도 원소들이 연속적으로 붙어 있다.
  • 장점
    • 메모리 안에서도 연속적으로 붙어 있어서 접근이 빠르고 편함. 인덱스로 접근이 가능한 이유!
  • 단점
    • 방을 추가하고 축소하는게 불가능

2 D 맵의 구성 Tile 들은 게임 도중에 크기가 변할 일도 보통 없고, 타일 마다 바로 바로 빠르게 접근이 가능해야 하므로 배열로 관리하는게 좋다. 이렇게 자료 구조 특징을 생각하면서 알맞는 자료 구조를 선택해야 한다.


🚕 동적 배열

설명

  • 특징
    • 배열의 크기를 유동적으로 할 수 있다.
    • 메모리 상에서도 원소들이 연속적으로 붙어 있다.
    • 따라서 실제로 사용할 크기 보다 1.5 ~ 2 배 가량 더 여유분을 두고 크기를 지정한다. 이사 횟수를 최소화 하기 위해.
      • size vs capacity
  • 장점
    • 배열의 크기를 유동적으로 늘렸다 줄였다가 가능!
    • 메모리 안에서도 연속적으로 붙어 있어서 접근이 편함. 인덱스로 접근이 가능한 이유!
  • 단점
    • 이사 비용이 크다.
      • 방을 추가하려 할 때(메모리 연속성 때문에 바로 옆 방으로 추가해야 한다.) 이미 그 방을 다른 사람이 차지하고 있다면 어쩔 수 없이 모든 방을 통째로 이사시켜야 한다. 메모리 연속성이 유지되야 하기 때문이다.
    • 중간에 삽입하고 삭제하는게 어렵다.
      • 메모리 연속성 때문에


List (in C#)

C# 에선 List가 동적 배열이다. 연결리스트 아님!

  • Add(원소값) 함수로 원소를 추가할 수 있다.
    • 메모리 연속성을 유지하기 위해 뒤에 추가된다.
      • vector의 push_back처럼!
      • C++ 에서 vector도 동적 배열이니까.. 이름을 일부러 vector라고 지어 봤다.
  • RemoveAt(index)
    • 메모리 연속성 덕분에 이렇게 인덱스로 쉽게 접근이 가능하다.
    • 해당 인덱스를 가진 원소를 삭제한다.
      • 삭제된 원소의 뒤에 있던 원소들을 앞으로 땡겨오는 식의 이사를 해주어야 해서 내부적으로 까다롭긴 하다.
using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithm
{
    class Board
    {
        public int[] array = new int[25];
        public List<int> vector = new List<int>();
        public LinkedList<int> linkedList = new LinkedList<int>();

        public void Initialize()
        {
            vector.Add(101);
            vector.Add(102);
            vector.Add(103);
            vector.Add(104);
            vector.Add(105);

            int temp = vector[2];  // 103

            vector.RemoveAt(2);  // 103 삭제
        }
    }
}


동적 배열 구현 해보기

    class MyList<T>
    {
        const int DEFAULT_SIZE = 1;
        T[] _data = new T[DEFAULT_SIZE];   // 배열의 처음 크기는 1 에서 시작한다고 해보자

        public int Count = 0;  // 실제로 사용 중인 데이터 개수
        public int Capacity { get { return _data.Length; } } // 미리 여유분을 가지고 예약된 데이터 개수. 사실상 배열의 크기와 일치.
        
        /* 추가 */ // 시간 복잡도 O(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 소유로 넘겨줌
                _data = newArray;
            }

            // 2. 공간에다가 데이터를 넣어 준다.
            _data[Count] = item;
            Count++;
        }

        /* 인덱스 접근 */ // 시간 복잡도 O(1)
        public T this[int index]
        {
            get { return _data[index]; }
            set { _data[index] = value; }
        }

        /* 삭제 */ // 시간 복잡도 O(N)
        public void RemoveAt(int index)
        {
            // 삭제할 원소의 뒤에 있는 원소들 한 칸씩 떙겨주기
            for (int i = index; i < Count - 1; i++)
                _data[i] = _data[i + 1];
            _data[Count - 1] = default(T);
            Count--;
        }
    }

동적 배열과 비슷하게 구현해본 MyList 클래스

  • 멤버 변수
    • _data
      • 👉 배열. 이 배열 안에 원소를 담는데, Count >= Capacity 가 되버리면 메모리 위치를 바꿔 이사갈 것이다.
      • vector와 비슷하게 처음엔 크기 1 에서 시작한다고 설정해보았다. (원소가 추가될 수록 늘려질 것.)
    • Count
      • 👉 실제로 동적 배열의 원소로서 사용할 데이터의 개수
    • Capacity
      • 👉 미리 여유분을 가지고 예약된 데이터 개수.
      • 사실상 _data 배열의 크기와 일치한다.
  • 원소를 추가하는 함수 Add(T item)
    1. 먼저 추가하기 전에 공간이 충분히 남아 있는지를 확인한다. Count >= Capacity
      • 여유 공간이 충분히 남아 있지 않다면
      • 1️⃣ 현재 사용하는 데이터의 두 배 크기를 가진, 더 큰 집으로 이사가기 위해 새로운 배열을 만든다.
        • T[] newArray = new T[Count * 2];
      • 2️⃣ 기존에 _data 배열에 있던 원소들을 새 공간인 newArray로 이사시킨다.
      • 3️⃣ 새 공간의 이름을 _data로 바꾼다. 집 주인은 똑같되 집 공간만 더 큰집으로 변경해준 것이다.
    2. 메모리 연속성을 유지하기 위해 제일 끝 자리에 해당 원소를 추가한다.
      • _data[Count] = item
      • Count를 1 증가시킨다.
      • 시간 복잡도는 O(1)이다.
        • 공간이 충분하지 않으면 이사시키는 작업(for문)은 자주 일어나지 않는다고 판단되어 복잡도 계산시 무시되었다.
  • 인덱스로 원소에 접근하는 함수 [] 연산자 오버로딩
    • ‘동적배열이름[index]’는 곧 _data[index]를 리턴하는 것과 같다.
    • ‘동적배열이름[index] = 어떤 값’은 곧 _data[index]에 value를 세팅하는 것과 같다.
    • 시간 복잡도는 O(1)이다.
  • 인덱스로 원소를 삭제하는 함수 RemoveAt(int index)
    1. 삭제할 원소의 뒤에 있는 원소들을 한 칸씩 앞으로 땡겨준다.
    2. 원래 마지막 원소 위치였던 자리(_data[Count - 1]는 이제 더 이상 해당 동적 배열의 원소 취급을 안할 것이므로 타입에 맞는 디폴트 값으로 초기화 해주었다.
      • int 타입이라면 0 으로 초기화 됨 default(int) 는 0
    3. Count를 1 감소시킨다.
      • 시간 복잡도는 O(N)이다.
        • 삭제한 원소의 뒤에 원소들을 한칸씩 앞으로 땡겨오는 작업 때문에


🚕 연결 리스트

설명

  • 특징
    • 원소들이 메모리를 연속적으로 차지 하지 않는다. 메모리 상에서 붙어 있지 않음!
    • 원소(노드) 안에 이전 원소, 다음 원소의 위치 정보를 포함하고 있어서 메모리 안에 연속적으로 차지 하지 않더라도 이런식으로 연결되어 있는 식이다.
      • 다음 노드 정보만 갖고 있다면 단방향 연결 리스트
      • 이전 노드, 다음 노드 정보 모두를 갖고 있다면 양방향 연결 리스트
  • 장점
    • 추가하고 삭제하기가 빠르고 편하다. O(1)
      • 이전 노드와 다음 노드 정보만 바꿔주어서 chain 만 끊어주고 새로 연결해주기만 하면 됨!
  • 단점
    • 메모리 연속성을 가지지 않기 때문에 인덱스로 접근하기가 어렵다. Random Access 가 불가능.
      • 바로 바로 찾을 수가 없다. 방이 이어져 있지 않아서 다음 노드 정보를 타고 타고 찾아 가야해서. 첫 노드부터 차례대로 티팅탐색하는 수 밖에 없다.


LinkedList (in C#)

    class Board
    {
        public int[] array = new int[25];
        //public List<int> vector = new List<int>(); 동적 배열
        public LinkedList<int> linkedList = new LinkedList<int>();  // 연결 리스트

        public void Initialize()
        {
            linkedList.AddLast(101);
            linkedList.AddLast(102);
            LinkedListNode<int> node = linkedList.AddLast(103);
            linkedList.AddLast(104);
            linkedList.AddLast(105);

            linkedList.Remove(node);
        }
    }

LinkedList 는 LinkedListNode 노드들로 이루어져 있다.

  • AddLast 👉🏽 연결 리스트의 마지막 자리에 노드를 추가하기
    • 마지막 노드로서 데이터를 추가한 후
    • 해당 노드를 리턴한다. 
      LinkedListNode<int> node = linkedList.AddLast(103);
  • Remove 👉🏽 인수로 들어온 해당 노드를 삭제
    • 인수로 LinkedListNode 를 받는다. 즉 노드로 받는다.
    • 인수로 들어온 해당 노드를 삭제한다.


연결 리스트 구현 코드

using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithm
{
    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;

        public MyLinkedListNode<T> AddLast(T data)  // O(1)
        {
            MyLinkedListNode<T> newRoom = new MyLinkedListNode<T>();
            newRoom.Data = data;

            if (Head == null)
                Head = newRoom;

            if (Tail != null)
            {
                Tail.Next = newRoom;
                newRoom.Prev = Tail;
            }

            Tail = newRoom;
            Count++;

            return newRoom;
        }

        public void Remove(MyLinkedListNode<T> room)  // O(1)
        {
            if (room == Head)
            {
                Head = Head.Next;
            }

            if (room == Tail)
            {
                Tail = Tail.Prev;
            }
            
            if (room.Prev != null)
            {
                room.Prev.Next = room.Next;
            }

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

            Count--;
        }
    }


    class Board
    {
        public MyLinkedList<int> linkedList = new MyLinkedList<int>();

        public void Initialize()
        {
            linkedList.AddLast(101);
            linkedList.AddLast(102);
            MyLinkedListNode<int> node = linkedList.AddLast(103);
            linkedList.AddLast(104);
            linkedList.AddLast(105);

            linkedList.Remove(node);
        }
    }
}

연결리스트 직접 구현해보기

  • 노드 👉 데이터
    • 데이터
    • 나의 이전 노드
    • 나의 다음 노드
      • 연결 리스트는 배열과 달리 연속적으로 붙어 있지 않으므로 연결리스트 순서 상 나의 이전 노드와 다음 노드의 주소를 가지고 있어야 한다.
        • 연속적으로 붙어있진 않아도 이전 노드 주소, 다음 노드 주소를 통해 연결 리스트 상의 노드들을 탐색할 수 있음
  • 연결리스트 👉 노드들을 연결한 집합체
    • Head 연결 리스트의 첫 번째 노드의 주소
    • Tail 연결 리스트의 마지막 노드의 주소
      • Head, Tail 만 알면 된다. 각 노드들은 스스로 이전 노드 참조와 다음 노드의 참조를 담고 있으므로 탐색 가능.
    • count 노드 총 갯수

리스트 마지막에 노드 추가

        public MyLinkedListNode<T> AddLast(T data)  // O(1)
        {
            MyLinkedListNode<T> newRoom = new MyLinkedListNode<T>();
            newRoom.Data = data;

            if (Head == null)
                Head = newRoom;

            if (Tail != null)
            {
                Tail.Next = newRoom;
                newRoom.Prev = Tail;
            }

            Tail = newRoom;
            Count++;

            return newRoom;
        }
  • 노드를 새로 만들고 노드의 데이터에 인수로 들어온 데이터 할당
  • Case 1️⃣ : 빈 연결 리스트 일 때
    • 새 노드를 첫 번째 노드로 임명해주면 된다. Head = newRoom
  • Case 2️⃣ : 맨 뒤에 연결
    • 기존의 마지막 노드의 다음 노드를 새 노드로 연결해준다. Tail.Next = newRoom
    • 새 노도의 이전 노드를 기존의 마지막 노드로 연결해준다. newRoom.Prev = Tail
  • 두 케이스 다 공통적으로 새 노드를 마지막 노드로 임명해주면 된다. Tail = newRoom
  • 연결 리스트 갯수 1 증가
  • 추가한 새 노드 리턴

노드 삭제

        public void Remove(MyLinkedListNode<T> room)  // O(1)
        {
            if (room == Head)
            {
                Head = Head.Next;
            }

            if (room == Tail)
            {
                Tail = Tail.Prev;
            }
            
            if (room.Prev != null)
            {
                room.Prev.Next = room.Next;
            }

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

            Count--;
        }
  • 삭제 하고자 하는 노드를 인수로 받는다.
  • Case 1️⃣ : 삭제할 노드가 첫 번째 노드일 때
    • 기존 Head의 다음 노드를 새로운 Head로 임명해준다. Head = Head.Next
  • Case 2️⃣ : 삭제할 노드가 마지막 번째 노드일 때
    • 기존 Tail의 이전 노드를 새로운 Tail로 임명해준다. Tail = Tail.Prev
      • 노드가 단 하나밖에 없는 리스트라면 Case1️⃣,2️⃣ 둘 다 해당되어 Head, Tail이 null이 되어 빈 연결 리스트가 될 것이다.
  • Case 3️⃣ : 삭제할 노드의 이전 노드가 존재 한다면
    • 삭제할 노드의 다음 노드를, 삭제할 노드의 이전 노드의 다음 노드로 정의하여 연결해준다.
      • 삭제할 노드가 맨 마지막 노드였다면 Case2️⃣,3️⃣ 둘 다 해당될 것이다.
  • Case 4️⃣ : 삭제할 노드의 다음 노드가 존재 한다면
    • 삭제할 노드의 이전 노드를, 삭제할 노드의 다음 노드의 이전 노드로 정의하여 연결해준다.
      • 중간에 위치해있던 노드는 Case3️⃣,4️⃣ 둘 다 해당될 것이다.
  • 연결 리스트 갯수 1 감소


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

댓글남기기

참고