연결 리스트 구현 연습

전체 코드

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;

        // O(1)
        public MyLinkedListNode<T> AddLast(T data)
        {
            MyLinkedListNode<T> newMyLinkedListNode = new MyLinkedListNode<T>();
            newMyLinkedListNode.Data = data;
            // 만약에 아직 방이 아예 없었다면, 새로 추가한 방이 곧 Head
            if (Head == null)
            {
                Head = newMyLinkedListNode;
            }
            // 기존의 마지막 방과 새로 추가되는 방을 연결해준다
            if (Tail != null)
            {
                Tail.Next = newMyLinkedListNode;
                newMyLinkedListNode.Prev = Tail;
            }
            // 새로 추가되는 방을 마지막 방으로 인정한다.
            Tail = newMyLinkedListNode;
            Count++;
            return newMyLinkedListNode;
        }
        // O(1)
        // 중간 접근은 지원하지 않음
        public void Remove(MyLinkedListNode<T> MyLinkedListNode)
        {
            // 기존의 첫번째 방 다음 방을 첫번째 방으로 인정한다.
            if (Head == MyLinkedListNode)
            {
                Head = Head.Next;
            }
            // 기존의 마지막 방의 이전 방을 마지막 방으로 인정한다.
            if (Tail == MyLinkedListNode)
            {
                Tail = Tail.Prev;
            }
            if (MyLinkedListNode.Prev != null)
            {
                MyLinkedListNode.Prev.Next = MyLinkedListNode.Next;
            }

            if (MyLinkedListNode.Next != null)
            {
                MyLinkedListNode.Next.Prev = MyLinkedListNode.Prev;
            }

            Count--;

        }
    }
}

class Board
{
    //public LinkedList<int> _data3 = new LinkedList<int>(); // 연결 리스트 C++ list
    public MyLinkedList<int> _data3 = new MyLinkedList<int>(); // 연결 리스트 C++ list
    public void Initialize()
    {
        _data3.AddLast(101);
        _data3.AddLast(102);
        MyLinkedListNode<int> node = _data3.AddLast(103);
        _data3.AddLast(104);
        _data3.AddLast(105);

        _data3.Remove(node);
    }
}

✅ 연결 리스트(Linked List)란?

연결 리스트는 노드들이 이전/다음 노드 주소를 포함하여 서로 연결된 자료구조입니다.
이중 연결 리스트에서는 각 노드가 Prev(이전 노드), Next(다음 노드)를 포함하여 양방향 탐색이 가능합니다.

🔹 배열과 연결 리스트의 차이
| 비교 항목 | 배열 (Array) | 연결 리스트 (Linked List) |
|-----------|-------------|--------------------------|
| 메모리 할당 | 연속된 공간 | 불연속적, 필요할 때마다 할당 |
| 접근 속도 | O(1) (인덱스 접근) | O(N) (순차 탐색) |
| 삽입/삭제 속도 | O(N) (중간 삽입/삭제 시 이동 필요) | O(1) (포인터만 변경) |
| 메모리 효율 | 필요 없는 공간도 할당됨 | 필요할 때마다 동적 할당 |
| 구조 | 크기 고정 | 크기 변경 가능 |

---

📜 코드 분석

1️⃣ MyLinkedListNode<T> (노드)

class MyLinkedListNode<T>
{
    public T Data;
    public MyLinkedListNode<T> Next;
    public MyLinkedListNode<T> Prev;
}

• 데이터(Data)를 저장하는 구조체 역할.
• 포인터(Prev, Next)를 사용해 앞/뒤 노드와 연결.

---

2️⃣ MyLinkedList<T> (연결 리스트)

class MyLinkedList<T>
{
    public MyLinkedListNode<T> Head = null;  // 첫 번째 노드
    public MyLinkedListNode<T> Tail = null;  // 마지막 노드
    public int Count = 0; // 현재 저장된 노드 개수

• Head: 리스트의 첫 번째 노드 주소 저장.
• Tail: 리스트의 마지막 노드 주소 저장.
• Count: 현재 리스트의 총 노드 개수.

---

3️⃣ AddLast(T data) - 마지막에 원소 추가 (O(1))

public MyLinkedListNode<T> AddLast(T data)
{
    MyLinkedListNode<T> newRoom = new MyLinkedListNode<T>(); // 새로운 노드 생성
    newRoom.Data = data;

    // Case 1️⃣: 빈 연결 리스트일 때
    if (Head == null)
        Head = newRoom;

    // Case 2️⃣: 기존 마지막 노드가 존재할 때
    if (Tail != null)
    {
        Tail.Next = newRoom;  // 기존 Tail의 다음 노드를 새 노드로 연결
        newRoom.Prev = Tail;  // 새 노드의 이전 노드를 기존 Tail로 연결
    }

    // 새 노드를 마지막 노드로 설정
    Tail = newRoom;
    Count++;

    return newRoom;
}

✅ 동작 원리

1. 새로운 노드를 생성하여 데이터를 저장.
2. Case 1️⃣: 리스트가 비어 있다면 Head를 새 노드로 설정.
3. Case 2️⃣: 기존 Tail의 Next를 새 노드로 연결, 새 노드의 Prev를 기존 Tail로 연결.
4. Tail을 새 노드로 업데이트.

🔹 시간 복잡도

• O(1) → 노드를 리스트 끝에 추가할 때 이동할 필요 없음 (참조값만 변경).

---

4️⃣ Remove(MyLinkedListNode<T> node) - 특정 노드 삭제 (O(1))

public void Remove(MyLinkedListNode<T> node)
{
    // Case 1️⃣: 삭제할 노드가 첫 번째 노드일 때
    if (node == Head)
        Head = Head.Next;

    // Case 2️⃣: 삭제할 노드가 마지막 노드일 때
    if (node == Tail)
        Tail = Tail.Prev;

    // Case 3️⃣: 삭제할 노드의 이전 노드가 존재할 때
    if (node.Prev != null)
        node.Prev.Next = node.Next;

    // Case 4️⃣: 삭제할 노드의 다음 노드가 존재할 때
    if (node.Next != null)
        node.Next.Prev = node.Prev;

    Count--;
}

✅ 동작 원리

1. Case 1️⃣: 삭제할 노드가 Head이면 Head = Head.Next로 변경.
2. Case 2️⃣: 삭제할 노드가 Tail이면 Tail = Tail.Prev로 변경.
3. Case 3️⃣: 삭제할 노드의 이전 노드가 존재하면 다음 노드를 연결.
4. Case 4️⃣: 삭제할 노드의 다음 노드가 존재하면 이전 노드를 연결.
5. Count--로 노드 개수 감소.

🔹 시간 복잡도

• O(1) → 특정 노드를 삭제할 때 단순히 포인터만 변경하면 되므로 빠름.

---

📌 시간 복잡도 비교

연산	시간 복잡도	설명
추가(AddLast)	O(1)	끝에 추가 시 Tail 참조 변경
삭제(Remove)	O(1)	특정 노드 제거 시 포인터 변경
검색(Search)	O(N)	원하는 값을 찾으려면 순차 탐색
접근(Index Access)	O(N)	인덱스가 없으므로 순차 탐색 필요

---