반응형
선형 자료 구조
데이터들을 일렬로 나열된 형태로 저장하고 싶을 때 사용하는 자료 구조
[선형 자료 구조] 👉 자료를 순차적으로 나열
- 배열 (Array)
- 동적 배열 (List)
- 연결 리스트 (LinkedList)
[비선형 자료 구조] 👉 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태
- 트리
- 그래프
배열 (Array)
특징
- 반드시 선언시 크기를 결정해야하며 배열의 크기는 고정적이며 절대 변경할 수 없다.
- 메모리 상에서도 원소들이 연속적으로 붙어 있다.
장점
- 메모리 안에서도 연속적으로 붙어 있어서 접근이 빠르고 편함. 인덱스로 접근이 가능한 이유!
단점
- 방을 추가하고 축소하는게 불가능
2D 맵의 구성시 맵의 타일(Tile)들은 게임 도중에 크기가 변할 일도 보통 없고, 타일마다 바로 바로 빠르게 접근이 가능해야 하므로 배열로 관리하는게 좋다. 이렇게 자료 구조 특징을 생각하면서 알맞는 자료 구조를 선택해야 한다.
동적 배열 (List)
특징
- 배열의 크기를 유동적으로 할 수 있다.
- 메모리 상에서도 원소들이 연속적으로 붙어 있다.
- 따라서 실제로 사용할 크기 보다 1.5 ~ 2 배 가량 더 여유분을 두고 크기를 지정한다. 이사 횟수를 최소화 하기 위해(size vs capacity)
장점
- 배열의 크기를 유동적으로 늘렸다 줄이는 것이 가능하다.
- 메모리 안에서도 연속적으로 붙어 있어서 접근이 편함. 인덱스로 접근이 가능한 이유!
단점
- 이사 비용이 크다.
- 방을 추가하려 할 때(메모리 연속성 때문에 바로 옆 방으로 추가해야 한다.) 이미 그 방을 다른 사람이 차지하고 있다면 어쩔 수 없이 모든 방을 통째로 이사시켜야 한다. 메모리 연속성이 유지되야 하기 때문이다.
- 메모리 연속성 때문에 중간에 삽입하고 삭제하는게 어렵다.
[동적 배열의 함수들]
Add(원소값) 함수로 원소를 추가할 수 있다.
- 메모리 연속성을 유지하기 위해 뒤에 추가된다. (vector의 push_back처럼!)
- C++ 에서는 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 삭제
}
}
}
[동적 배열 구현]
동적 배열과 비슷하게 구현해본 MyList 클래스
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--;
}
}
[멤버 변수]
1. _data
- 👉 배열. 이 배열 안에 원소를 담는데, Count >= Capacity 가 되버리면 메모리 위치를 바꿔 이사갈 것이다.
- vector와 비슷하게 처음엔 크기 1 에서 시작한다고 설정해보았다. (원소가 추가될 수록 늘려질 것.)
2. Count
- 👉 실제로 동적 배열의 원소로서 사용할 데이터의 개수
3.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 가 불가능.
- 바로 바로 찾을 수가 없다. 방이 이어져 있지 않아서 다음 노드 정보를 타고 타고 찾아 가야해서. 첫 노드부터 차례대로 티팅탐색하는 수 밖에 없다.
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 감소
반응형
'공부 > 인프런 - Rookiss' 카테고리의 다른 글
| Part 2-3-2. 미로 준비 : 미로 생성 알고리즘 (Binary Tree, Side Winder) (0) | 2023.08.04 |
|---|---|
| Part 2-3-1. 미로 준비 : 맵 만들기 (0) | 2023.08.04 |
| Part 2-1-2. 환경 설정 (0) | 2023.08.04 |
| Part 2-1-1. Big-O 표기법 (0) | 2023.08.04 |
| Part 2. 자료구조와 알고리즘 (0) | 2023.08.03 |