선형 자료구조 - 연결 리스트(LinkedList) c#

리스트란?

---

C#의 리스트(List)는 System.Collections.Generic 네임스페이스의 List<T> 클래스를 사용하여 다양한 타입의 데이터를 순차적으로 저장하고 관리할 수 있는 유연한 제네릭 컬렉션입니다.

 

꼭 알아야 하는 지식!

 

리스트

• ArrayList - 내부적으로 배열을 사용
• LinkedList - 링크 포인터를 사용
• List<T> - 제너릭 타입

 

배열의 특징

• 생성 시 사용할 공간을 미리 할당한다.
• 인덱스를 사용 데이터 접근에 빠르다.
• 데이터의 크기를 변경하지 못한다.

 

리스트특징

• 데이터의 추가 삭제가 자유롭다.
• 생성 시 크기를 지정하지 않는다.
• 리스트를 다른 말로 Dynamic Array라고 부른다.

 

박싱(Boxing)

• 값 형식을 참조 형식으로 변환하는 것

 

언박싱(Unboxing)

• 참조  형식을 값 형식으로 변환하는 것

 

LinkedList 이론

---

ArrayList는 인덱스를 활용하여 데이터에 접근한다.

LinkedList는 헤드(head)와 꼬리(tail)로 추가 · 삭제를 한다.

 

그럼 이제 LinkedList를 사용하기 위해 몇 가지 지식을 알아야 합니다.

노드, 링크포인트, 헤드 이 세 가지 내용을 알고 있어야 아래 있는 사진을 이해할 수 있습니다.

 

단순 연결 리스트

위 사진 처럼 단순 연결 리스트는 헤드(head)가 다음 1번 노드를 가리키고 1번 노드는 2번 노드를 가리키는 것 단순 연결 리스트라고 말합니다.

 

그럼? 왜 사용하는 걸까?

 

아래 사진처럼 사용하기 위해 저희는 이 연결 리스트를 알아야 합니다.

 

1번째 이론 사진

10번 노드가 1번 노드와 2번 노드 사이에 넣고 싶습니다.

그럼 여기서 우린 어떻게 작업하면 될까요?

 

네 바로 다음 노드를 가리키는 링크포인터를 변경해주면 됩니다!

이게 무슨 소리인지 아래 사진을 확인해주세요!

2번째 이론 사진

 

이렇게 하면 정말 간단하죠? 그럼 왜 이걸 사용하는 걸까요?

 

연결리스트 특징

• 추가 데이터에 대한 연산 불필요
• 구현의 어려움
• 탐색 연산의 비용이 높음

 

전체 코드

---

단순 연결 리스트

using System;

public class Node
{
    public int data;
    public Node next;

    public Node(int d)
    {
        data = d;
        next = null;
    }
}

public class LinkedList
{
    public Node head;

    public void AddNode(int data)
    {
        Node newNode = new Node(data);

        if (head == null)
        {
            head = newNode;
            return;
        }

        Node lastNode = head;
        while (lastNode.next != null)
        {
            lastNode = lastNode.next;
        }

        lastNode.next = newNode;
    }

    public void PrintList()
    {
        Node currentNode = head;

        while (currentNode != null)
        {
            Console.Write(currentNode.data + " ");
            currentNode = currentNode.next;
        }
        Console.WriteLine();
    }
}


namespace MyCompiler {
    class Program {
        public static void Main(string[] args) 
        {
            LinkedList linkedList = new LinkedList();
    
            linkedList.AddNode(1);
            linkedList.AddNode(2);
            linkedList.AddNode(3);
            linkedList.AddNode(4);
    
            Console.WriteLine("Linked List: ");
            linkedList.PrintList();
        }
    }
}

 

연결리스트 2번 노드 3번 노드 사이에 10번 노드 추가

using System;

public class Node
{
    public int data;
    public Node next;

    public Node(int d)
    {
        data = d;
        next = null;
    }
}

public class LinkedList
{
    public Node head;

    public void AddNode(int data)
    {
        Node newNode = new Node(data);

        if (head == null)
        {
            head = newNode;
            return;
        }

        Node lastNode = head;
        while (lastNode.next != null)
        {
            lastNode = lastNode.next;
        }

        lastNode.next = newNode;
    }

    public void AddNodeBetween(int newData, int afterData, int beforeData)
    {
        Node newNode = new Node(newData);
        Node currentNode = head;

        while (currentNode != null)
        {
            if (currentNode.data == afterData && currentNode.next != null && currentNode.next.data == beforeData)
            {
                newNode.next = currentNode.next;
                currentNode.next = newNode;
                return;
            }
            currentNode = currentNode.next;
        }

        Console.WriteLine("The specified nodes not found in the list.");
    }

    public void PrintList()
    {
        Node currentNode = head;

        while (currentNode != null)
        {
            Console.Write(currentNode.data + " ");
            currentNode = currentNode.next;
        }
        Console.WriteLine();
    }
}

class Program
{
    static void Main(string[] args)
    {
        LinkedList linkedList = new LinkedList();

        linkedList.AddNode(1);
        linkedList.AddNode(2);
        linkedList.AddNode(3);
        linkedList.AddNode(4);

        Console.WriteLine("Original Linked List: ");
        linkedList.PrintList();

        linkedList.AddNodeBetween(10, 2, 3);

        Console.WriteLine("Modified Linked List: ");
        linkedList.PrintList();
    }
}