C# 링크드 리스트

링크드 리스트(LinkedList)란?

• 데이터를 저장하는 노드들이 서로 연결되어 있는 선형 데이터 구조이다.
  각 노드들은 데이터 값과 다음 노드를 가르키는 포인터를 가지고 있고, 배열과 달리 메모리 공간이 연속적으로 할당될 필요가 없어 메모리 효율성이 높고, 중간에 데이터를 삽입하거나 삭제하기 용이한 자료구조이다.

• 링크드 리스트 도식
  

• C#에서 System.Collections.Generic 네임스페이스에 있는 LinkedList 클래스를 통해 링크드 리스트를 사용할 수 있다.

• 주요 메서드
  ㄴ AddFirst(T value): 리스트의 맨 앞에 노드 추가
  ㄴ AddLast(T value): 리스트의 맨 뒤에 노드 추가
  ㄴ AddAfter(LinkedListNode node, T value): 특정 노드 뒤에 노드 추가
  ㄴ AddBefore(LinkedListNode node, T value): 특정 노드 앞에 노드 추가
  ㄴ RemoveFirst(): 리스트의 맨 앞 노드 삭제
  ㄴ RemoveLast(): 리스트의 맨 뒤 노드 삭제
  ㄴ Remove(T value): 특정 값을 가진 첫 번째 노드 삭제
  ㄴ Find(T value): 특정 값을 가진 노드 검색

• 예시 코드

internal class Program
{
    private static void Main(string[] args)
    {
        LinkedList<string> list = new LinkedList<string>();
        // AddFirst(T value) 리스트 시작 부분에 새로운 노드 추가
        list.AddFirst("A"); // A
        list.AddFirst("B"); // B -> A
        // AddLast(T value) 리스트 끝 부분에 새로운 노드 추가
        list.AddLast("B");  // B -> A -> B
        list.AddLast("C");  // B -> A -> B -> C

        LinkedListNode<string> node = list.Find("C");
        // AddBefore(LinkedListNode<T>, T value) 지정된 노드 앞에 새로운 노드 추가
        list.AddBefore(node, "F");  // B -> A -> B -> F -> C

        LinkedListNode<string> node2 = list.Find("C");
        // AddAfter(LinkedListNode<T>, T value) 지정된 노드 뒤에 새로운 노드를 추가
        list.AddAfter(node2, "F");  // B -> A -> B -> F -> C -> F

        list.Remove("B");   // 첫 번째로 일치하는 요소를 리스트에서 제거  A -> B -> F -> C -> F

        list.RemoveFirst(); // 첫번째 노드를 리스트에서 제거 B -> F -> C -> F

        list.RemoveLast();  // 마지막 노드를 리스트에서 제거 B -> F -> C

        foreach (string item in list)
        {
            Console.WriteLine(item);
            //Console.WriteLine(list.Find(item).Value);
        }

        LinkedListNode<string> node3 = list.Find("C");    // node값이 C인 노드를 가르킴
        Console.WriteLine(node3.Value);
        //Console.WriteLine(list.Find("A").Value);  // 없는 값을 검색할 경우 null 반환

        // Contains(T Value) 리스트에 특정 값이 포함되어 있는지 여부를 확인
        bool contains = list.Contains("A");
        Console.WriteLine(contains);
        contains = list.Contains("B");
        Console.WriteLine(contains);

        // Clear() 리스트의 모든 노드를 제거
        list.Clear();
        foreach (string item in list) 
        {
            Console.WriteLine(item); 
        }
    }
}

• C#에서 링크드 리스트를 라이브러리를 사용하지 않고 구현해 보았다.
  ㄴ 값을 추가할때는 재귀 함수를 이용하여 next(Address)가 비어있는 노드를 순차적으로 탐색해 찾은 다음 새로운 노드를 생성해 연결되도록 구현
  ㄴ 데이터를 삭제할때에는 head 노드부터 시작해 삭제할 노드(data)를 탐석해 삭제할 노드를 찾고 찾은 다음
  삭제할 노드의 이전 노드의 next를 삭제할 노드의 다음 노드의 주소로 변경해 삭제 한다.

using Microsoft.VisualBasic;
using System.ComponentModel;
using static System.Net.Mime.MediaTypeNames;
using static System.Runtime.InteropServices.JavaScript.JSType;

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

        // 데이터 추가
        list.Add(8);
        list.Add(5);
        list.Add(3);
        list.Add(1);

        // 출력
        list.Print();

        // 리스트에서 5 값 삭제
        list.Remove(5);
        Console.WriteLine();
        list.Print();

        // 리스트에서 3 값 삭제
        list.Remove(3);
        Console.WriteLine();
        list.Print();
    }
}

// 노드 기본 틀(data값, next다음 노드)
public class Node
{
    // 노드가 저장하는 데이터
    public int data;

    // 다음 노드를 가리키는 포인터
    public Node next;

    // 생성자 - 데이터를 받아 노드 생성
    public Node(int data)
    {
        this.data = data;
        next = null;
    }

    // 연결 리스트 내용 출력 (재귀 함수 사용)
    public void Print()
    {
        Console.Write(data + "->");

        if (next != null)
        {
            next.Print();
        }
    }

    public void Add(int data)
    {
        if (next == null)
        {
            next = new Node(data);
        }
        else
        {
            // 재귀 함수 사용
            next.Add(data);
        }
    }
}

public class LinkedList
{
    // 헤드 노드 = 첫 번째 노드
    public Node head;

    // 리스트에 데이터 추가
    public void Add(int data)
    {
        if (head == null)
        {
            head = new Node(data);
        }
        else
        {
            head.Add(data);
        }
    }

    // 출력
    public void Print()
    {
        if (head != null)
        {
            head.Print();
        }
    }

    // 리스트에서 특정 데이터값 노드 삭제
    public void Remove(int data)
    {
        Node cur = head;

        while (cur.next != null && cur.next.data != data)
        {
            cur = cur.next;
        }

        if (cur.next != null)
        {
            cur.next = cur.next.next;
        }
    }
}