현재 노드를 head로 설정하고, 현재 노드가 null일 때까지 또는 n-1 번 반복합니다.
각 반복에서 현재 노드를 다음 노드로 업데이트합니다.
반복 후의 현재 노드가 null이면 예외를 발생시킵니다.
새로운 노드를 생성하고, 그 노드의 Data 필드에 item을 저장합니다.
새로운 노드의 Next 필드를 현재 노드의 Next로 설정합니다.
현재 노드의 Next를 새로운 노드로 설정합니다.
count를 1 증가시킵니다.
RemoveFirst: 리스트의 첫 번째 노드를 제거하고 그 데이터를 반환하는 함수.
입력: 없음.
출력: 제거된 노드의 데이터.
Remove: 리스트의 n번째 노드를 제거하고 그 데이터를 반환하는 함수.
입력: 제거할 노드의 위치 n (0-based index).
출력: 제거된 노드의 데이터.
동작:
n이 0이면 RemoveFirst를 호출하여 첫 번째 노드를 제거합니다.
n이 0보다 큰 경우:
현재 노드를 head로 설정하고, 현재 노드가 null일 때까지 또는 n-1 번 반복합니다.
각 반복에서 현재 노드를 다음 노드로 업데이트합니다.
반복 후의 현재 노드가 null이면 예외를 발생시킵니다.
제거할 노드를 현재 노드의 Next로 설정합니다.
현재 노드의 Next를 제거할 노드의 Next로 설정합니다.
제거할 노드의 데이터를 임시 변수에 저장합니다.
count를 1 감소시킵니다.
임시 변수에 저장된 데이터를 반환합니다.
Count: 리스트의 노드 개수를 반환하는 함수.
입력: 없음.
출력: 리스트의 노드 개수.
PrintAllNodes: 리스트의 모든 노드를 출력하는 함수.
입력: 없음.
출력: 없음.
<코드>
public class My_LinkedList<T>
{
private class Node
{
public T Data;
public Node Next;
public Node(T data)
{
Data = data;
Next = null;
}
}
private Node head;
private int count;
public My_LinkedList()
{
head = null;
count = 0;
}
public bool IsEmpty()
{
// ****** CODE HERE ******
// ***********************
}
public void AddFirst(T item)
{
// ****** CODE HERE ******
// ***********************
}
public void Insert(int n, T item)
{
// ****** CODE HERE ******
// ***********************
}
public T RemoveFirst()
{
// ****** CODE HERE ******
// ***********************
}
public T Remove(int n)
{
// ****** CODE HERE ******
// ***********************
}
public int Count()
{
// ****** CODE HERE ******
// ***********************
}
public void PrintAllNodes()
{
Node current = head;
while (current != null)
{
Console.Write(current.Data + " ");
current = current.Next;
}
Console.WriteLine();
}
}
// 구현 확인을 위한 코드입니다.
class Program
{
static void Main(string[] args)
{
My_LinkedList<int> list = new My_LinkedList<int>();
list.AddFirst(3);
list.AddFirst(2);
list.AddFirst(1);
list.Insert(2, 4);
list.Insert(3, 5);
Console.WriteLine("Linked List:");
list.PrintAllNodes();
Console.WriteLine("Remove First: " + list.RemoveFirst());
Console.WriteLine("Remove at 2: " + list.Remove(2));
Console.WriteLine("Linked List:");
list.PrintAllNodes();
Console.WriteLine("Count: " + list.Count());
}
}
[ 설명 문제 ]
1. LinkedList의 특성을 설명해주세요.
:노드를 추가하거나 삭제할 때는 수정하려는 위치에 있는 노드의 연결을 끊고 노드를 추가하거나 제거한 후 다시 연결하면 되기 때문에 추가 및 삭제가 빠르다. 하지만 위치를 통해서 바로 찾기 어렵기 때문에 탐색하는 데 비용이 많이 든다.
2. LinkedList는 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?
데이터를 추가하거나 제거할 일이 많을 때 사용하면 좋다. 하지만 리스트 안의 데이터를 자주 탐색해야 할 때는 사용하기 불리하다.
3. LinkedList를 본인의 프로젝트에 적용해본 경험을 말해주세요.
아직 없다.
[ 실습 문제 ]
💡 [LinkedList를 이용한 ObjectPool 만들기]
Object Pool은 객체를 미리 생성해두고 필요할 때마다 재사용하는 디자인 패턴입니다.
이는 객체 생성과 소멸에 드는 비용을 줄여 성능을 향상시킬 수 있습니다.
이 문제에서는 LinkedList를 이용하여 **수정 및 삽입의 시간 복잡도가 O(1)**인 Object Pool을 구현해야 합니다.
주요 멤버 변수
pool: 사용 가능한 객체를 저장하는 LinkedList<T>.
createFunc: 새로운 객체를 생성하는 데 사용하는 함수.
resetAction: 객체를 재사용하기 전에 초기화하는 함수.
함수 명세
GetObject
기능: 풀에서 객체를 가져옵니다. 만약 풀에 사용 가능한 객체가 없다면 새로운 객체를 생성합니다.
입력: 없음.
출력: 풀에서 가져온 객체 T.
ReleaseObject
기능: 객체를 풀에 반환합니다.
입력: 반환할 객체 obj (제네릭 타입 T).
출력: 없음.
Count
기능: 현재 풀에 있는 객체의 수를 반환합니다.
입력: 없음.
출력: 현재 풀에 있는 객체의 수 (int 값).
public class Bullet
{
public static int BulletCount = 0;
public Bullet() => ID = BulletCount++;
~Bullet() => BulletCount--;
public int ID { get; private set; }
public (float, float) Position { get; set; }
}
public class ObjectPool<T>
{
private LinkedList<T> pool;
private Func<T> createFunc;
private Action<T> resetAction;
public ObjectPool(int size, Func<T> createFunc, Action<T> resetAction = null)
{
this.pool = new LinkedList<T>();
this.createFunc = createFunc ?? throw new ArgumentNullException(nameof(createFunc));
this.resetAction = resetAction;
for (int i = 0; i < size; i++)
pool.AddFirst(createFunc());
}
public T GetObject()
{
// ****** CODE HERE ******
// ***********************
}
public void ReleaseObject(T obj)
{
// ****** CODE HERE ******
// ***********************
}
public int Count()
{
return pool.Count;
}
}
// 구현 확인을 위한 코드입니다.
class Program
{
static void Main(string[] args)
{
ObjectPool<Bullet> bulletPool = new ObjectPool<Bullet>(
10,
() => new Bullet(),
bullet => { bullet.Position = (0, 0); }
);
// 현재 풀에 있는 객체 수를 출력합니다.
Console.WriteLine($"Objects in pool: {bulletPool.Count()}");
// 여러 개의 Bullet 객체를 풀에서 얻습니다.
for (int i = 1; i <= 5; i++)
{
Bullet bullet = bulletPool.GetObject();
bullet.Position = (i * 10.0f, i * 20.0f);
Console.WriteLine($"Got bullet with ID: {bullet.ID}, Position: {bullet.Position}");
}
// 풀에서 객체를 다시 얻어서 출력했다가 반환합니다. 객체는 초기화된 상태여야 합니다.
for (int i = 1; i <= 3; i++)
{
Bullet bullet = bulletPool.GetObject();
Console.WriteLine($"Got bullet with ID: {bullet.ID}, Position: {bullet.Position}");
bulletPool.ReleaseObject(bullet);
}
// 몇 개의 객체를 풀에 반환합니다.
for (int i = 6; i <= 10; i++)
{
Bullet bullet = bulletPool.GetObject();
bullet.Position = (i * 10.0f, i * 20.0f);
bulletPool.ReleaseObject(bullet);
}
// 최종적으로 풀에 있는 객체 수를 출력합니다.
Console.WriteLine($"Final objects in pool: {bulletPool.Count()}");
}
}
