연결 리스트는 노드(Node)라는 구조를 사용하여 데이터를 저장하는 자료구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함하며, 노드들은 포인터를 통해 서로 연결된다. 연결 리스트는 배열과 달리 크기가 고정되어 있지 않아 동적으로 데이터를 추가하거나 삭제할 수 있으며, 메모리 공간을 효율적으로 사용할 수 있다.
단뱡향 링크드 리스트 (Singly Linked List) : 단방향으로만 연결되어 있는것으로 다음 노드로만 이동 가능
양방향 링크드 리스트 (Double Linked List) : 이전 노드와 다음 노드를 가리키는 포인터를 모두 갖고 있어 양방향으로 탐색이 가능한 자료구조
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class MyNode<T>
{
public T Data;
public MyNode<T> Next = null;
public MyNode(T data)
{
Data = data;
}
}
public class MyLinkedList<T>
{
private MyNode<T> HeadNode;
public void Add(bool isFront, T data)
{
MyNode<T> newNode = new MyNode<T>(data);
if (isFront)
{
newNode.Next = HeadNode;
HeadNode = newNode;
}
else if (HeadNode == null)
{
HeadNode = newNode;
}
else
{
MyNode<T> iterator = HeadNode;
while (iterator.Next != null)
{
iterator = iterator.Next;
}
iterator.Next = newNode;
}
}
public void PrintIteration()
{
var curNode = HeadNode;
while (curNode != null)
{
Debug.Log(curNode.Data);
curNode = curNode.Next;
}
}
public void RemoveAt(int removeIndex)
{
if (HeadNode == null)
return;
if (removeIndex == 0)
{
HeadNode = HeadNode.Next;
return;
}
int currentIndex = 0;
MyNode<T> curNode = HeadNode;
while (curNode.Next != null)
{
if (currentIndex > removeIndex - 1)
{
if (curNode.Next != null)
{
curNode.Next = curNode.Next.Next;
}
else
{
curNode.Next = null;
}
break;
}
curNode = curNode.Next;
currentIndex++;
}
}
}
유니티에서 구현한 단방향 링크드 리스트이다.
- MyNode<T> 클래스:
- 각 노드를 표현
- Data는 노드의 데이터를 저장
- Next는 다음 노드를 가리킨다.
- MyLinkedList<T> 클래스:
- HeadNode는 리스트의 첫 번째 노드를 가리킨다.
- Add 메서드:
- isFront가 true면 리스트 앞에 추가한다.
- false면 리스트 끝에 추가한다.
- PrintIteration 메서드:
- 리스트의 모든 요소를 순회하며 출력한다.
- RemoveAt 메서드:
- 지정된 인덱스의 노드를 제거한다.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class DoubleNode<T>
{
public T Data;
public DoubleNode<T> Next;
public DoubleNode<T> Prev;
public DoubleNode(T data)
{
Data = data;
Next = null;
Prev = null;
}
}
public class DoubleLinkedList<T>
{
private DoubleNode<T> headDoubleNode;
private DoubleNode<T> tailDoubleNode;
public int Count { get; private set; }
public void AddFirst(T data)
{
DoubleNode<T> newDoubleNode = new DoubleNode<T>(data);
if (headDoubleNode == null)
{
headDoubleNode = newDoubleNode;
tailDoubleNode = newDoubleNode;
}
else
{
newDoubleNode.Next = headDoubleNode;
headDoubleNode.Prev = newDoubleNode;
headDoubleNode = newDoubleNode;
}
Count++;
}
public void AddLast(T data)
{
DoubleNode<T> newDoubleNode = new DoubleNode<T>(data);
if (headDoubleNode == null)
{
headDoubleNode = newDoubleNode;
tailDoubleNode = newDoubleNode;
}
else
{
tailDoubleNode.Next = newDoubleNode;
newDoubleNode.Prev = tailDoubleNode;
tailDoubleNode = newDoubleNode;
}
Count++;
}
public void AddMiddle(T data)
{
if (Count <= 1)
{
AddLast(data);
return;
}
DoubleNode<T> newDoubleNode = new DoubleNode<T>(data);
DoubleNode<T> current = headDoubleNode;
int middleIndex = Count / 2;
for (int i = 0; i < middleIndex - 1; i++)
{
current = current.Next;
}
newDoubleNode.Next = current.Next;
newDoubleNode.Prev = current;
current.Next.Prev = newDoubleNode;
current.Next = newDoubleNode;
Count++;
}
public void RemoveFirst()
{
if (headDoubleNode == null)
return;
headDoubleNode = headDoubleNode.Next;
if (headDoubleNode != null)
headDoubleNode.Prev = null;
else
tailDoubleNode = null;
Count--;
}
public void RemoveLast()
{
if (tailDoubleNode == null)
return;
tailDoubleNode = tailDoubleNode.Prev;
if (tailDoubleNode != null)
tailDoubleNode.Next = null;
else
headDoubleNode = null;
Count--;
}
public void RemoveAt(int removeIndex)
{
if (headDoubleNode == null || removeIndex < 0 || removeIndex >= Count)
return;
if (removeIndex == 0)
{
RemoveFirst();
return;
}
if (removeIndex == Count - 1)
{
RemoveLast();
return;
}
DoubleNode<T> current = headDoubleNode;
for (int i = 0; i < removeIndex; i++)
{
current = current.Next;
}
current.Prev.Next = current.Next;
current.Next.Prev = current.Prev;
Count--;
}
public void PrintAll()
{
DoubleNode<T> current = headDoubleNode;
while (current != null)
{
Debug.Log(current.Data);
current = current.Next;
}
}
public DoubleNode<T> Find(T data)
{
DoubleNode<T> current = headDoubleNode;
while (current != null)
{
if (EqualityComparer<T>.Default.Equals(current.Data, data))
return current;
current = current.Next;
}
return null;
}
}
유니티에서 구현한 양방향 링크드 리스트이다.
- DoubleNode<T> 클래스:
- 각 노드를 표현
- Data: 노드가 저장하는 실제 데이터
- Next: 다음 노드를 가리키는 참조
- Prev: 이전 노드를 가리키는 참조
- DoubleLinkedList<T> 클래스:
- headDoubleNode: 리스트의 첫 번째 노드를 가리킨다.
- tailDoubleNode: 리스트의 마지막 노드를 가리킨다.
- Count: 리스트의 현재 노드 수를 추적한다.
- 주요 메서드:
- AddFirst: 리스트의 맨 앞에 새 노드를 추가
- AddLast: 리스트의 맨 뒤에 새 노드를 추가
- AddMiddle: 리스트의 중간에 새 노드를 추가
- RemoveFirst: 첫 번째 노드를 제거
- RemoveLast: 마지막 노드를 제거
- RemoveAt: 지정된 인덱스의 노드를 제거
- PrintAll: 모든 노드의 데이터를 출력
- Find: 특정 데이터를 가진 노드를 찾아 반환
연결 리스트는 다양한 응용 분야에서 사용된다. 예를 들어, 스택, 큐, 해시 테이블 등의 자료구조를 구현하는 데 사용되며, 그래프, 트리와 같은 복잡한 자료구조를 표현하는 데에도 활용된다. 또한 게임에서 플레이어의 인벤토리 관리, 실행 취소/다시 실행 기능 구현, 또는 캐릭터의 스킬 목록 관리 등에 활용될 수 있다.