동적 배열(List)과 연결 리스트(LinkedList) 구현
알고리즘 자료구조에 앞서 List와 LinkedList의 동작 방식에 대해 알아보도록 하자.
List
List는 List내의 칸을 방이라고 가정하면 방의 개수를 유동적으로 늘리는 것이며, 연속된 방을 배정받아서 사용한다고 생각하면 된다. 이는 일반 배열에 비해 비용이 많이 든다는 문제점이 있지만, 고정되어 추가/축소가 불가능한 배열에 비해 유동적이기 때문에 유연하다고 볼 수 있다.
다만 중간에 삽입 혹은 삭제가 거의 불가능하다는 점이 단점이다.
일단 리스트의 Add와 RemoveAt을 보자면 일반적으로 사용한다면 간단하게 참조하여 사용하면 된다.
그러나 이번 포스트에서 할 일은 하나하나 풀어보면서 구현 원리에 대해 알아보는 것이다.
internal class ListBoard
{
public int[] _data = new int[25]; // 배열
public List<int> _data2 = new List<int>(); // 동적 배열
public LinkedList<int> _data3 = new LinkedList<int>(); // 연결 리스트
public void Initialize()
{
_data2.Add(101);
_data2.Add(102);
_data2.Add(103);
_data2.Add(104);
_data2.Add(105);
int temp = _data2[2];
_data2.RemoveAt(2);
}
}
기본적으로 List는 생성 후에 .Add와 .RemoveAt으로 추가, 삭제가 가능하다.
이를 하나하나 풀어보도록 하자.
동적배열(List) 구현
1. Add
class MyList<T>
{
const int DEFAULT_SIZE = 1;
T[] _data = new T[DEFAULT_SIZE];
public int Count = 0; // 실제로 사용중인 데이터 개수
public int Capacity { get { return _data.Length; } } // 예약된 데이터 개수
}
상수로 기본 사이즈를 정해두고, 데이터 개수와 앞으로 들어올 데이터를 선언해준다.
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++;
}
Count와 Capacity의 크기를 비교하여 Count가 크거나 같을 때 새로운 배열로 이사가기 위해 크기를 늘리고 이사를 간 후 기존에 있던 배열에서 새로운 배열로 바꿔준다.
그리고 새로 생긴 공간에 item을 넣어준다.
2. Search
그리고 이건 현재 데이터에 어떤 item이 들어있는지 알려주는 코드이다.
public T this[int index]
{
get { return _data[index]; }
set { _data[index] = value; }
}
_data[2] 와 같은 원리라고 보면 된다.
3. RemoveAt
public void RemoveAt(int index)
{
// index를 기준으로(삭제될 수를 기준으로) 하나씩 당겨줌
// 101 102 103 104 105 의 수 중 2번째 수를 지운다고 가정하면
// 101 102 104 105 105 이렇게 밀어내는 식이라고 생각하고
// 마지막에 105를 default인 0 으로 교체해준 후 공간을 삭제해주는 형식이다.
for(int i = index; i < Count - 1; i++)
{
_data[i] = _data[i + 1];
}
_data[Count - 1] = default(T);
Count--;
}
삭제하는 것은 다음과 같다. 먼저 수를 밀어낸 후, 가장 마지막에 위치한 수치의 공간을 삭제해주는 방법이다.
for문을 돌려 받아온 index의 값부터 배열의 끝까지 반복문을 돌려 위치를 한칸씩 앞으로 옮겨준다.
그러면 삭제되어야 할 index는 덮어진 상태이며, 마지막 수는 두 개가 되는데 이를 default값인 0으로 덮어주고
그리고 Count를 줄여 삭제해주도록 한다.
디버깅 하면 다음과 같다.
Count * 2 를 해줬기 때문에 2배씩 늘어난 Count를 볼 수 있으며, 값이 순차적으로 찼다가 RemoveAt해주니 가운데 103이 사라진 모습을 볼 수 있다.
연결리스트 구현(LinkedList)
1. Add
class MyLinkedListNode<T>
{
// 참조, 주소값을 저장함
// 방 안에 방이 있는것이 아닌, 그 방을 가리키는 주소가 있는 것이다.
public T Data;
public MyLinkedListNode<T> Next;
public MyLinkedListNode<T> Prev;
}
먼저 받아올 Data와 Data의 Next와 Prev를 정해준다. 이는 추후에 Search에서도 이용될 수 있는 데이터의 노드를 가리킨다.
class MyLinkedList<T>
{
public MyLinkedListNode<T> Head = null; // 첫번째
public MyLinkedListNode<T> Tail = null; // 마지막
public int Count = 0;
// O(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
// 기존의 [마지막 방]과 [새로 추가되는 방]을 연결해준다.
if (Tail != null)
{
Tail.Next = newRoom;
newRoom.Prev = Tail;
}
// [새로 추가되는 방]을 [마지막 방]으로 인정한다.
Tail = newRoom;
Count++;
return newRoom;
}
}
Add단계에서 생성한다음 Data에 인자로 받아온 data를 넣어준다.
생각해야 할 것은 일단 처음 생성하는 방인지에 대한 처리를 해주고 그게 아니라면 가장 끝에 있는 방과 추가되는 방을 링크로 연결해줘야 한다.
그리고 새로추가된 방이 가장 끝에 있기 때문에 마지막 방으로 만들어주면 끝이다.
2. Remove
public void Remove(MyLinkedListNode<T> room)
{
// [기존의 첫번째 방 다음방] 을 [첫번째 방]으로 인정한다.
if(Head == room)
Head = Head.Next;
// [기존의 마지막 방의 이전 방] 을 [마지막 방]으로 인정한다.
if(Tail == room)
Tail = Tail.Prev;
// 102 와 104를 연결해주는 것
if(room.Prev != null)
room.Prev.Next = room.Next;
// 104와 102를 연결해주는 것
if(room.Next != null)
room.Next.Prev = room.Prev;
Count--;
}
Remove에서는 만약 첫번째 방을 삭제한다면 그 다음에 왔던 수를 가장 첫번째 방으로 해줘야 한다.
반대로 마지막 방을 삭제하게 된다면 마지막 방의 앞이 마지막이 되기 때문에 이를 처리해주도록 한다.
그리고 이전 방이 null이 아니라 값이 있다면, 이전에 있던 다음수와 다음수를 연결해 준다.
말이 좀 어려워지는데 103이 삭제해야 되는 수라고 치면 103의 이전의 다음수를 104로 만들어준다.
103의 이전의 다음수라면 당연히 -+ 하여 103이어야 하는데, 지금은 103을 삭제해줘야 하기 때문에 103의 다음수인 104를 연결해줌으로써 103을 자연스럽게 삭제하는 것이다.
마찬가지로 이 반대도 처리해주면서 Count를 - - 해준다면 삭제가 된다.
