250924

자료구조

수많은 데이터를 효율적으로 관리하는 기법

 

List<>

순서가 중요하거나 크기가 가변적인 데이터 관리에 유리

배열을 쓸법한 상황은 보통 다 List 도 어울린다

인덱스로 한번에 특정 요소를 가져올 때 좋다

중간에 삽입/삭제가 일어나면 연속성을 유지하기 위해 연산 부하가 생김

static void Main(string[] args)
{
    List<string> inven = new List<string>();

    inven.Add("철삽");
    inven.Add("다이아곡괭이");
    inven.Add("구리");

    //                   ↓Capacity 가 아닌 Count 를 사용한다
    for (int i = 0; i < inven.Count; i++)
    {
        Console.WriteLine(inven[i]);
    }

    inven[0] = "이렇게도 접근 가능";
    Console.WriteLine(inven[0]);
}

 

Linked List

 

노드라는 단위로 이루어진 자료구조

1. 데이터 ( Data )

2. 다음 노드를 가리키는 포인터 ( Next )

체인처럼 노드들이 연결되어 있는 구조

 

데이터와 데이터가 연결은 되어있지만 연속적으로 연결되어있지 않고,

데이터는 각각 다음 혹은 이전 데이터가 어디에 있는지 주소를 들고 있는 방식이다.

장점으로는 중간 삽입 삭제가 빠르다

단점으로는 특정 요소를 검색할 때 느리다.

애니팡처럼 잦은 삽입삭제가 이루어지는 게임류

NPC 가 특정 위치까지 이동할 때의 이동 경로

 

1. Node

값과 다음 노드의 위치를 기억하는 참조로 이루어져 있음

시작점을 Head 라고 부름

 

단일 방향 리스트

HEAD -> [ Data | Next ] -> [ Data | Next ] -> [ Data | Next ] -> null

Data : 저장할 값

Next : 다음 노드 주소 정보

// Data , 즉 실제 데이터
// Next , 다음 노드 주소 정보

public class Node
{
    public ??? Data { get; set; }
    public Node Next { get; set; }

    public Node(??? Data)
    {
        Data = data;
        Next = null;
    }
}

public class Node <T>
{
    public T Value { get; set; } // 제네릭으로 나중에 결정될 Data
    public Node<T> Next { get; set; } //

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

배열은 하나의 타입만 담을수 있다

링크드 리스트도 결국은 노드들의 연속이라 노드끼리 서로 같은 타입이어야 한다

Next 는 다음 노드를 참조해야 하므로 타입이 Node 자신이어야 한다

제네릭을 썼으니 Node<T> 로 작성해야 현재 노드와 같은 타입을 이어줄 수 있다.

 

 

링크드 리스트라는 자료구조가 내부적으로 어떻게 작동하는지 원리를 Node<T> 선언 후 구현하기

class LinkedList2<T>
{
    public int Count { get; set; }  // 노드 갯수

    public Node<T> Head { get; private set; } // 헤드라는 이름의 빈 공간, Node<T> 형식의 주소를 기억할 수 있다

    public LinkedList2()
    {
        Head = null; // 명시적으로 비움
        Count = 0; // 링크드리스트 만들어질 때 0
    }

    // Add Last
    // 만약 Head 가 null 이면? 
    // 맨처음 추가된 노드가 시작과 동시에 Head
    // 그렇지 않다면 현재 마지막 노드를 찾아서 뒤에 연결

    public void AddLast (T value)
    {
        Node<T> newNode = new Node<T>(value); // Add 지시 받았으니 새 노드 생성

        if ( Head == null ) // 최초 실행시, Head 가 Null 일것
        {
            Head = newNode; // 처음 추가된 노드를 Head 에도 주소 복사해서 담는다
        }
        else
        {
            Node<T> current; // 노드의 주소를 임시로 기억할 빈 공간 생성
            current = Head; // else 문에 들어왔다는 뜻은, Head 에 무언가 값이 있다는 뜻
            // 그러므로 이걸 임시 current 에 복사했음

            // 1. 맨 처음엔 헤드가 들어있다
            // 2. 헤드의 Next가 만약 Null 이 아니라면?
            // 3. 반복 수행
            // 아니라면 아래 내용 수행
            while (current.Next !=null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
        Count++;
    }

 

 

링크드 리스트의 작동 원리

using System;

public class Node<T>
{
    public T Value { get; set; }
    public Node<T> Next { get; set; }

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

public class LinkedList2<T>
{
    public Node<T> Head { get; private set; }
    public int Count { get; private set; }

    public LinkedList()
    {
        Head = null;
        Count = 0;
    }

    public void AddLast(T value)
    {
        Node<T> newNode = new Node<T>(value);

        if (Head == null)
        {
            Head = newNode;
        }
        else
        {
            Node<T> current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }

        Count++;
    }

    public bool Remove(T value)
    {
        if (Head == null) return false;

        if (Head.Value.Equals(value))
        {
            Head = Head.Next;
            Count--;
            return true;
        }

        Node<T> current = Head;
        while (current.Next != null && !current.Next.Value.Equals(value))
        {
            current = current.Next;
        }

        if (current.Next == null) return false;

        current.Next = current.Next.Next;
        Count--;
        return true;
    }

    public Node<T> Find(T value)
    {
        Node<T> current = Head;
        while (current != null)
        {
            if (current.Value.Equals(value))
            {
                return current;
            }
            current = current.Next;
        }
        return null;
    }
}

 

마지막 검증 단계

static void Main(string[] args)
{
    // 마지막 검증단계
    LinkedList2<int> myList = new LinkedList2<int>();

    myList.AddLast(1);
    myList.AddLast(2);
    myList.AddLast(13);

    // 출력 테스트
    Node<int> current; // 빈공간 생성
    current = myList.Head; // Head 에 기억된 주소를 current 에 복사

    while (current != null)
    {
        Console.WriteLine(current.Value);
        current = current.Next;
    }

    // 제거 테스트
    myList.Remove(2);

    Console.WriteLine("---구분선---");

    current = myList.Head;
    while (current != null)
    {
        Console.WriteLine(current.Value);
        current = current.Next;
    }
    
}