Chapter 2. 배열, 동적 배열, 연결 리스트 비교
카테고리: Algorithm Lesson 2
인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click
선형 자료 구조
데이터들을 일렬로 나열된 형태로 저장하고 싶을 때 사용하는 자료 구조
- 선형 자료 구조 👉 자료를 순차적으로 나열
- 배열
- 동적 배열
- 연결 리스트
- 비선형 자료 구조 👉 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태
- 트리
- 그래프
🚖 배열
설명
- 특징
- 반드시 선언시 크기를 결정해야하며
- 배열의 크기는 고정적이며 절대 변경할 수 없다.
- 메모리 상에서도 원소들이 연속적으로 붙어 있다.
- 장점
- 메모리 안에서도 연속적으로 붙어 있어서 접근이 빠르고 편함. 인덱스로 접근이 가능한 이유!
- 단점
- 방을 추가하고 축소하는게 불가능
2 D 맵의 구성 Tile 들은 게임 도중에 크기가 변할 일도 보통 없고, 타일 마다 바로 바로 빠르게 접근이 가능해야 하므로 배열로 관리하는게 좋다. 이렇게 자료 구조 특징을 생각하면서 알맞는 자료 구조를 선택해야 한다.
🚕 동적 배열
설명
- 특징
- 배열의 크기를 유동적으로 할 수 있다.
- 메모리 상에서도 원소들이 연속적으로 붙어 있다.
- 따라서 실제로 사용할 크기 보다 1.5 ~ 2 배 가량 더 여유분을 두고 크기를 지정한다. 이사 횟수를 최소화 하기 위해.
sizevscapacity
- 장점
- 배열의 크기를 유동적으로 늘렸다 줄였다가 가능!
- 메모리 안에서도 연속적으로 붙어 있어서 접근이 편함. 인덱스로 접근이 가능한 이유!
- 단점
- 이사 비용이 크다.
- 방을 추가하려 할 때(메모리 연속성 때문에 바로 옆 방으로 추가해야 한다.) 이미 그 방을 다른 사람이 차지하고 있다면 어쩔 수 없이 모든 방을 통째로 이사시켜야 한다. 메모리 연속성이 유지되야 하기 때문이다.
- 중간에 삽입하고 삭제하는게 어렵다.
- 메모리 연속성 때문에
- 이사 비용이 크다.
List (in C#)
C# 에선
List가 동적 배열이다. 연결리스트 아님!
Add(원소값)함수로 원소를 추가할 수 있다.- 메모리 연속성을 유지하기 위해 뒤에 추가된다.
- vector의
push_back처럼! - C++ 에서 vector도 동적 배열이니까.. 이름을 일부러 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)
- 먼저 추가하기 전에 공간이 충분히 남아 있는지를 확인한다. Count >= Capacity
- 여유 공간이 충분히 남아 있지 않다면
- 1️⃣ 현재 사용하는 데이터의 두 배 크기를 가진, 더 큰 집으로 이사가기 위해 새로운 배열을 만든다.
- T[] newArray = new T[Count * 2];
- 2️⃣ 기존에
_data배열에 있던 원소들을 새 공간인newArray로 이사시킨다. - 3️⃣ 새 공간의 이름을
_data로 바꾼다. 집 주인은 똑같되 집 공간만 더 큰집으로 변경해준 것이다.
- 메모리 연속성을 유지하기 위해 제일 끝 자리에 해당 원소를 추가한다.
- _data[Count] = item
Count를 1 증가시킨다.- 시간 복잡도는
O(1)이다.- 공간이 충분하지 않으면 이사시키는 작업(for문)은 자주 일어나지 않는다고 판단되어 복잡도 계산시 무시되었다.
- 먼저 추가하기 전에 공간이 충분히 남아 있는지를 확인한다. Count >= Capacity
- 인덱스로 원소에 접근하는 함수 [] 연산자 오버로딩
- ‘동적배열이름[index]’는 곧
_data[index]를 리턴하는 것과 같다. - ‘동적배열이름[index] = 어떤 값’은 곧
_data[index]에value를 세팅하는 것과 같다. - 시간 복잡도는
O(1)이다.
- ‘동적배열이름[index]’는 곧
- 인덱스로 원소를 삭제하는 함수 RemoveAt(int index)
- 삭제할 원소의 뒤에 있는 원소들을 한 칸씩 앞으로 땡겨준다.
- 원래 마지막 원소 위치였던 자리(
_data[Count - 1]는 이제 더 이상 해당 동적 배열의 원소 취급을 안할 것이므로 타입에 맞는 디폴트 값으로 초기화 해주었다.- int 타입이라면 0 으로 초기화 됨 default(int) 는 0
Count를 1 감소시킨다.- 시간 복잡도는
O(N)이다.- 삭제한 원소의 뒤에 원소들을 한칸씩 앞으로 땡겨오는 작업 때문에
- 시간 복잡도는
🚕 연결 리스트
설명
- 특징
- 원소들이 메모리를 연속적으로 차지 하지 않는다. 메모리 상에서 붙어 있지 않음!
- 원소(노드) 안에 이전 원소, 다음 원소의 위치 정보를 포함하고 있어서 메모리 안에 연속적으로 차지 하지 않더라도 이런식으로 연결되어 있는 식이다.
- 다음 노드 정보만 갖고 있다면 단방향 연결 리스트
- 이전 노드, 다음 노드 정보 모두를 갖고 있다면 양방향 연결 리스트
- 장점
- 추가하고 삭제하기가 빠르고 편하다.
O(1)- 이전 노드와 다음 노드 정보만 바꿔주어서 chain 만 끊어주고 새로 연결해주기만 하면 됨!
- 추가하고 삭제하기가 빠르고 편하다.
- 단점
- 메모리 연속성을 가지지 않기 때문에 인덱스로 접근하기가 어렵다. Random Access 가 불가능.
- 바로 바로 찾을 수가 없다. 방이 이어져 있지 않아서 다음 노드 정보를 타고 타고 찾아 가야해서. 첫 노드부터 차례대로 티팅탐색하는 수 밖에 없다.
- 메모리 연속성을 가지지 않기 때문에 인덱스로 접근하기가 어렵다. 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이 되어 빈 연결 리스트가 될 것이다.
- 노드가 단 하나밖에 없는 리스트라면 Case1️⃣,2️⃣ 둘 다 해당되어
- 기존
- Case 3️⃣ : 삭제할 노드의 이전 노드가 존재 한다면
- 삭제할 노드의 다음 노드를, 삭제할 노드의 이전 노드의 다음 노드로 정의하여 연결해준다.
- 삭제할 노드가 맨 마지막 노드였다면 Case2️⃣,3️⃣ 둘 다 해당될 것이다.
- 삭제할 노드의 다음 노드를, 삭제할 노드의 이전 노드의 다음 노드로 정의하여 연결해준다.
- Case 4️⃣ : 삭제할 노드의 다음 노드가 존재 한다면
- 삭제할 노드의 이전 노드를, 삭제할 노드의 다음 노드의 이전 노드로 정의하여 연결해준다.
- 중간에 위치해있던 노드는 Case3️⃣,4️⃣ 둘 다 해당될 것이다.
- 삭제할 노드의 이전 노드를, 삭제할 노드의 다음 노드의 이전 노드로 정의하여 연결해준다.
- 연결 리스트 갯수 1 감소
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기