Unity 개발자를 위한 C# LinkedList(링크드 리스트) 구현

Queue(큐)와 List에 이어 이번 글에서는 노드(Node)들을 포인터로 연결해서 관리하는 LinkedList 구조를 살펴보겠습니다. 이 글에서 구현할 LinkedList는 양방향 원형 연결 리스트(doubly circular linked list)로, 각 노드가 이전 노드(Prev)와 다음 노드(Next)를 모두 알고 있고, 마지막 노드와 첫 노드가 다시 서로 연결되어 있는 구조입니다.

 

기본적인 리스트(List)가 배열 기반 동적 리스트라면, LinkedList는 노드 기반 연결 리스트입니다. 배열 기반 List는 인덱스 접근이 매우 빠른 대신, 중간 삽입/삭제 시 데이터를 많이 옮겨야 합니다. 반대로 LinkedList는 인덱스 접근은 느리지만, 노드를 기준으로 한 삽입/삭제가 매우 빠르다는 장점을 가집니다.

 

이 글에서는 LinkedList의 개념과 특징을 정리하고, 양방향 원형 LinkedList를 직접 구현한 뒤, Unity에서 테스트하는 예제를 함께 살펴보겠습니다.

---

1. LinkedList 구조와 동작 방식

LinkedList는 각 요소를 Node라는 객체로 감싸고, 이 노드들이 서로를 가리키는 포인터(참조)로 연결되는 구조입니다.

• 각 노드는 Value (실제 데이터), Prev (이전 노드), Next (다음 노드) 정보를 가집니다.
• 리스트의 시작점은 Head 노드로 관리합니다.
• 양방향 리스트이므로 Prev 방향, Next 방향 모두로 순회할 수 있습니다.
• 원형 리스트이므로 Head.Prev는 마지막 노드(Last), Last.Next는 다시 Head를 가리킵니다.

내부적으로는 배열을 사용하지 않기 때문에, 인덱스로 바로 접근하는 기능은 없습니다.
대신, 특정 노드를 이미 가지고 있다면 그 노드 기준으로 앞/뒤에 삽입하거나 제거하는 작업은 항상 O(1) 시간에 처리할 수 있습니다.

 

정리하면 LinkedList는:

• 배열처럼 연속된 메모리가 아니라 노드끼리 연결된 구조이고,
• 중간 삽입/삭제가 매우 빠른 대신,
• 임의 위치 탐색은 순차적으로 따라가야 하므로 O(n) 시간이 걸립니다.

---

2. LinkedList가 활용되는 대표적인 사례

LinkedList는 “현재 위치를 기준으로 앞/뒤로 이동”하는 흐름이 있을 때 특히 잘 어울립니다. 실제 개발에서 자주 등장하는 예시는 다음과 같습니다.

• Undo / Redo 체인
  이전 상태, 다음 상태를 노드로 연결해 두고 현재 상태 노드를 기준으로 앞/뒤로 이동하며 작업을 취소/재실행합니다.
• 게임 이벤트 / 컷신 타임라인
  여러 연출/이벤트를 순서대로 노드로 연결해 두고, 현재 노드에서 다음 이벤트, 혹은 이전 이벤트로 이동하며 처리합니다.
• 상태 머신(State Machine)의 순환 구조
  일정 상태들이 반복적으로 순환하는 경우, 원형 LinkedList로 구성하면 자연스럽게 순환 흐름을 표현할 수 있습니다.
• 재생 목록(Playlist)
  음악/영상 플레이어에서 현재 곡/영상 노드를 기준으로 이전/다음 트랙으로 이동할 때 유용합니다.
• 빈번한 삽입/삭제가 필요한 버퍼
  중간에 끼워 넣거나 지우는 작업이 많고, 인덱스 접근 속도가 크게 중요하지 않은 경우에 적합합니다.

배열 기반 List와 비교하면

• LinkedList : 순서가 중요하고 중간 삽입/삭제가 잦은 곳
• 배열 기반 List : 랜덤 인덱스 접근과 캐시 효율이 중요한 곳

※ 실제 게임 개발에서는 LinkedList가 노드 객체를 계속 생성·삭제하기 때문에 GC가 많이 발생하여 잘 사용되지 않습니다. 대부분의 상황에서는 배열 기반 List<T>가 더 효율적입니다.

---

3. LinkedList가 제공하는 기능 (구현 기준)

이번에 구현할 LinkedList는 다음과 같은 기능을 제공합니다.

• 기본 정보
  • int Count : 현재 저장된 노드(요소) 개수
  • Node First : 리스트의 첫 노드(Head)
• 앞/뒤 삽입
  • AddFirst(T value) : 리스트 맨 앞(Head) 앞에 새 노드 추가
  • AddLast(T value) : 리스트 맨 뒤(Last) 뒤에 새 노드 추가
  • AddBefore(Node node, T value) : 특정 노드 앞에 삽입
  • AddAfter(Node node, T value) : 특정 노드 뒤에 삽입
• 삭제
  • Remove(T value) : 해당 값을 가진 첫 노드를 찾아 제거
  • Remove(Node node) : 특정 노드 직접 제거
  • RemoveFirst(out T value) : 첫 노드 제거 후 값 반환
  • RemoveLast(out T value) : 마지막 노드 제거 후 값 반환
• 탐색
  • Find(T value) : Head부터 정방향으로 첫 번째 일치 노드 탐색
  • FindLast(T value) : Last부터 역방향으로 마지막 일치 노드 탐색
• 기타
  • Clear() : 모든 노드 제거
  • IEnumerable<T> 구현 : foreach로 순회 가능

이 정도 기능을 구현해 두면, .NET의 LinkedList<T>와 유사한 방식으로 대부분의 상황에 활용할 수 있습니다.

---

4. LinkedList 내부 동작 방식

이제 LinkedList가 실제로 어떻게 동작하는지, 간단한 예시를 통해 단계별로 살펴보겠습니다. 여기서는 값 A, B, C, D, E를 추가/삭제하는 과정을 예로 들겠습니다.

 

✔ 초기 상태

• 리스트에는 아직 어떤 노드도 없습니다.
• head = null, count = 0

 

✔ A 추가 (AddFirst 또는 AddLast)

• 새 노드 A를 생성합니다.
• 리스트가 비어 있으므로 Head가 A를 가리키게 합니다.
• 원형 리스트이기 때문에 A.Prev와 A.Next 모두 A 자신을 가리키도록 설정합니다.
• head = A, count = 1

 

✔ B 추가 (AddLast)

• 새 노드 B를 생성합니다.
• 현재 리스트의 마지막 노드는 Head.Prev를 통해 얻을 수 있습니다. (즉, Last = Head.Prev)
• 새 노드는 항상 마지막 노드(Head.Prev) 바로 뒤에 삽입됩니다. 원형 리스트이므로 Last.Next는 Head이며, 이 위치에 새 노드를 연결해 원형 구조를 유지합니다.
• head = A, count = 2

 

✔ C, D 추가 (AddLast)

• 같은 방식으로 C, D를 추가합니다.
• 각 삽입은 참조 몇 개만 교체하면 되므로 O(1)에 가깝게 처리됩니다.
• head = A, count = 4

 

✔ C 제거 (Remove)

• 제거할 노드 C의 이전 노드(B)와 다음 노드(D)를 구합니다.
• B와 D를 서로 직접 연결해 C를 리스트에서 분리합니다.
• 그리고 C의 Prev/Next를 null 처리하여 완전히 고립시킵니다.
• head = A, count = 3

 

• 중간 노드를 제거할 때는 그 노드의 양옆 노드를 서로 연결해 원형 구조를 유지합니다.
• 배열 기반 List처럼 데이터를 앞으로 당기는 작업은 없고, 포인터(참조)만 수정되기 때문에 중간 삭제가 매우 빠릅니다.

 

✔ A 제거 (Remove)

• 현재 Head는 A이므로, A를 제거하면 새 Head는 A.Next, 즉 B가 됩니다.
• A의 이전 노드(=마지막 노드 D)와 A의 다음 노드(B)를 서로 연결합니다.
• Head를 B로 갱신합니다.
• head = B, count = 2

 

• Head를 제거하면 Head를 그다음 노드로 옮긴 뒤, 양옆 노드를 다시 연결해 원형 구조를 유지합니다.

 

✔ E를 B와 D 사이에 삽입 (AddAfter 또는 AddBefore)

• 새 노드 E를 생성합니다.
• E는 B와 D 사이에 삽입되며, 삽입은 Prev/Next 참조만 교체하는 방식으로 처리됩니다.
• E.Prev = B, E.Next = D로 설정합니다.
• B.Next를 E로 바꾸고, D.Prev를 E로 바꿔 두 노드를 E에 연결합니다.
• head = B, count = 3

 

※ 이런 방식 덕분에 LinkedList는 현재 노드를 알고 있다는 전제에서, 앞/뒤 삽입이나 삭제를 할 때 항상 O(1) 성능을 기대할 수 있습니다.

---

5. C#으로 LinkedList 직접 구현하기

아래 코드는 양방향 원형 LinkedList를 C# 제네릭으로 구현한 예제입니다.

using System;
using System.Collections;
using BCL = System.Collections.Generic; // BCL - Base Class Library

namespace Daebak.Common.Collections
{
    /// <summary>
    /// 양방향 원형 연결 리스트(doubly circular linked list) 구현
    /// Head를 기준으로 Prev는 역방향, Next는 정방향 순회 가능
    /// </summary>
    public class LinkedList<T> : BCL.IEnumerable<T>
    {
        /// <summary>
        /// 리스트의 각 노드를 나타내는 클래스
        /// Prev/Next 포인터로 양방향 연결 유지
        /// </summary>
        public class Node
        {
            public Node Prev;               // 이전 노드(previous)
            public Node Next;               // 다음 노드(next)
            public LinkedList<T> List;      // 소속된 리스트 정보

            public T Value { get; private set; }

            public Node(T value)
            {
                Value = value;
            }
        }

        private Node _head;                 // 리스트의 첫 노드(Head)
        private int _count;                 // 요소 개수
        private readonly BCL.IEqualityComparer<T> _cmp; // 값 비교용 comparer

        public int Count => _count;

        // 리스트의 첫 노드 반환. (null일 수도 있음)
        public Node First => _head;

        // 리스트의 마지막 노드 반환.
        // 원형 구조이므로 Head.Prev가 Last가 됨
        private Node Last => _head == null ? null : _head.Prev;

        /// <summary>
        /// comparer를 지정할 수 있는 생성자.
        /// 기본은 EqualityComparer<T>.Default 사용.
        /// </summary>
        public LinkedList(BCL.IEqualityComparer<T> comparer = null)
        {
            _cmp = comparer ?? BCL.EqualityComparer<T>.Default;
        }

        /// <summary>
        /// 리스트 완전히 초기화
        /// 각 노드의 Prev/Next/List 정보 모두 해제
        /// </summary>
        public void Clear()
        {
            if (_head != null)
            {
                Node cur = _head;
                do
                {
                    Node next = cur.Next;

                    cur.Prev = null;
                    cur.Next = null;
                    cur.List = null;

                    cur = next;

                } while (cur != _head);
            }

            _head = null;
            _count = 0;
        }

        /// <summary>
        /// 리스트의 앞(Head)에 value를 가진 새 노드 추가
        /// </summary>
        public Node AddFirst(T value)
        {
            Node node = new Node(value);
            InsertNodeBeforeHead(node);
            return node;
        }

        /// <summary>
        /// 리스트의 뒤(Last)에 value를 가진 새 노드 추가
        /// </summary>
        public Node AddLast(T value)
        {
            Node node = new Node(value);

            if (_head == null)
            {
                InsertNodeBeforeHead(node);
            }
            else
            {
                InsertNodeAfter(Last, node);
            }

            return node;
        }

        /// <summary>
        /// 특정 노드 앞에 value 삽입
        /// </summary>
        public Node AddBefore(Node node, T value)
        {
            ValidateNode(node);

            Node n = new Node(value);
            InsertNodeBefore(node, n);

            return n;
        }

        /// <summary>
        /// 특정 노드 뒤에 value 삽입
        /// </summary>
        public Node AddAfter(Node node, T value)
        {
            ValidateNode(node);

            Node n = new Node(value);
            InsertNodeAfter(node, n);

            return n;
        }

        /// <summary>
        /// value와 동일한 값을 가진 첫 노드를 찾아 제거
        /// 제거 시 true, 없으면 false 반환.
        /// </summary>
        public bool Remove(T value)
        {
            Node found = Find(value);
            if (found == null)
            {
                return false;
            }

            Remove(found);

            return true;
        }

        /// <summary>
        /// 지정한 노드를 리스트에서 제거
        /// </summary>
        public void Remove(Node node)
        {
            ValidateNode(node);

            // 노드가 1개만 있는 경우
            if (_count == 1)
            {
                _head = null;
            }
            else
            {
                // 양방향 연결 제거
                node.Prev.Next = node.Next;
                node.Next.Prev = node.Prev;

                // 제거한 노드가 Head라면 Head를 다음 노드로 이동
                if (node == _head)
                {
                    _head = node.Next;
                }
            }

            node.Prev = null;
            node.Next = null;
            node.List = null;

            --_count;
        }

        /// <summary>
        /// 첫 노드를 제거하고 그 값을 반환
        /// </summary>
        public bool RemoveFirst(out T value)
        {
            if (_head == null)
            {
                value = default;
                return false;
            }

            value = _head.Value;
            Remove(_head);

            return true;
        }

        /// <summary>
        /// 마지막 노드를 제거하고 그 값을 반환
        /// </summary>
        public bool RemoveLast(out T value)
        {
            Node last = Last;
            if (last == null)
            {
                value = default;
                return false;
            }

            value = last.Value;
            Remove(last);

            return true;
        }

        /// <summary>
        /// 리스트에서 value와 동일한 값을 가진 첫 노드 찾기
        /// </summary>
        public Node Find(T value)
        {
            if (_head == null)
            {
                return null;
            }

            Node cur = _head;
            do
            {
                if (_cmp.Equals(cur.Value, value))
                {
                    return cur;
                }

                cur = cur.Next;

            } while (cur != _head);

            return null;
        }

        /// <summary>
        /// 리스트에서 value와 동일한 값을 가진 마지막 노드 찾기
        /// Reverse 방향으로 탐색 수행.
        /// </summary>
        public Node FindLast(T value)
        {
            if (_head == null)
            {
                return null;
            }

            Node last = Last;
            Node cur = last;
            do
            {
                if (_cmp.Equals(cur.Value, value))
                {
                    return cur;
                }

                cur = cur.Prev;

            } while (cur != last);

            return null;
        }

        /// <summary>
        /// foreach 사용을 위해 순회 Enumerator 제공
        /// Head부터 Next 방향으로 순회
        /// </summary>
        public BCL.IEnumerator<T> GetEnumerator()
        {
            if (_head == null)
            {
                yield break;
            }

            Node cur = _head;
            do
            {
                yield return cur.Value;
                cur = cur.Next;

            } while (cur != _head);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// Head 앞에 새 노드 삽입
        /// 리스트가 비어 있다면 node는 단독 원형 구조가 됨
        /// </summary>
        private void InsertNodeBeforeHead(Node node)
        {
            if (_head == null)
            {
                // 단일 노드 → Prev/Next 모두 자기 자신
                node.Prev = node;
                node.Next = node;
                node.List = this;

                _head = node;
                ++_count;

                return;
            }

            InsertNodeBefore(_head, node);
            _head = node;
        }

        /// <summary>
        /// 참조 노드(refNode) 앞에 새 노드 삽입
        /// </summary>
        private void InsertNodeBefore(Node refNode, Node newNode)
        {
            newNode.List = this;

            newNode.Prev = refNode.Prev;
            newNode.Next = refNode;

            refNode.Prev.Next = newNode;
            refNode.Prev = newNode;

            // Head 앞에 삽입되면 Head 갱신
            if (refNode == _head)
            {
                _head = newNode;
            }

            ++_count;
        }

        /// <summary>
        /// 참조 노드(refNode) 뒤에 새 노드 삽입
        /// </summary>
        private void InsertNodeAfter(Node refNode, Node newNode)
        {
            newNode.List = this;

            newNode.Next = refNode.Next;
            newNode.Prev = refNode;

            refNode.Next.Prev = newNode;
            refNode.Next = newNode;

            ++_count;
        }

        /// <summary>
        /// 노드가 null이거나 리스트에 속해 있지 않을 경우 예외 처리
        /// </summary>
        private void ValidateNode(Node node)
        {
            if (node == null)
            {
                throw new ArgumentNullException(nameof(node));
            }

            if (node.List != this)
            {
                throw new InvalidOperationException("해당 노드는 이 리스트에 속하지 않습니다.");
            }
        }
    }
}

---

6. 유니티(Unity) 환경에서 테스트해 보기

이제 Unity에서 직접 LinkedList를 생성하고, 앞/뒤 삽입 및 삭제가 제대로 동작하는지 확인해 보겠습니다.

using UnityEngine;
using Daebak.Common.Collections;

public class Test_LinkedList : MonoBehaviour
{
    void Start()
    {
        LinkedList<int> list = new();

        Debug.Log("=== AddFirst / AddLast ===");
        list.AddFirst(20);   // [20]
        list.AddFirst(10);   // [10, 20]
        list.AddLast(30);    // [10, 20, 30]
        list.AddLast(40);    // [10, 20, 30, 40]

        Dump(list);

        Debug.Log("\n=== AddAfter / AddBefore ===");
        var node20 = list.Find(20);
        list.AddAfter(node20, 25);   // [10, 20, 25, 30, 40]

        var node10 = list.First;
        list.AddBefore(node10, 5);   // [5, 10, 20, 25, 30, 40]

        Dump(list);

        Debug.Log("\n=== Remove(25) ===");
        list.Remove(25);             // [5, 10, 20, 30, 40]
        Dump(list);

        Debug.Log("\n=== RemoveFirst / RemoveLast ===");
        if (list.RemoveFirst(out int first))
            Debug.Log($"RemoveFirst: {first}");

        if (list.RemoveLast(out int last))
            Debug.Log($"RemoveLast: {last}");

        Dump(list);

        Debug.Log("\n=== Find / FindLast ===");
        var first20 = list.Find(20);
        var last20 = list.FindLast(20);
        Debug.Log($"Find(20):     {(first20 != null ? first20.Value.ToString() : "null")}");
        Debug.Log($"FindLast(20): {(last20 != null ? last20.Value.ToString() : "null")}");

        Debug.Log("\n=== Clear ===");
        list.Clear();
        Dump(list);
    }

    private void Dump(LinkedList<int> list)
    {
        System.Text.StringBuilder sb = new System.Text.StringBuilder();
        sb.Append("[ ");

        var node = list.First;
        if (node != null)
        {
            var cur = node;
            do
            {
                sb.Append(cur.Value);
                sb.Append(" ");
                cur = cur.Next;

            } while (cur != node);
        }

        sb.Append("]");
        Debug.Log($"{sb} (Count = {list.Count})");
    }
}

실행 결과

=== AddFirst / AddLast ===
[ 10 20 30 40 ] (Count = 4)

=== AddAfter / AddBefore ===
[ 5 10 20 25 30 40 ] (Count = 6)

=== Remove(25) ===
[ 5 10 20 30 40 ] (Count = 5)

=== RemoveFirst / RemoveLast ===
RemoveFirst: 5
RemoveLast: 40
[ 10 20 30 ] (Count = 3)

=== Find / FindLast ===
Find(20):     20
FindLast(20): 20

=== Clear ===
[ ] (Count = 0)

---

마무리

이 글에서는 양방향 원형 LinkedList의 개념과 동작 방식, 실제 활용 사례, 그리고 C#으로 구현한 코드와 Unity 테스트 예제까지 단계적으로 살펴보았습니다.

• LinkedList는 노드 기반 연결 구조로, 배열 기반 List와 달리 중간 삽입/삭제에 강합니다.
• 양방향 + 원형 구조를 사용하면 현재 노드를 기준으로 앞/뒤 이동이 자연스럽고, 마지막 노드를 따로 저장할 필요가 없습니다.
• 배열 기반 List, Queue, Stack과 함께 기본 자료구조 라인업으로 꼭 익혀 두면, 이후 Deque, Tree, Graph 같은 복합 구조를 이해하는 데 큰 도움이 됩니다.

한 번 직접 구현해 보고, Unity에서 다양한 타입(int, string, 게임 오브젝트 참조 등)을 넣어 테스트해 보면 LinkedList의 장단점과 사용 시점을 훨씬 명확하게 체감할 수 있을 것입니다.

 

※ 다음 글에서는 Deque(덱) 구조를 살펴보며, 연결 리스트 기반 구조가 어떻게 양쪽 삽입·삭제가 가능한 형태로 확장되는지를 정리합니다.