Sandor의 개발 일지

Make real your dreams

3 분 소요

Description

자료구조 중 하나인 양방향 LinkedList를 C#으로 구현해 볼것이다.
Unity에 연동하여 출력하였다.

Desc

Arr와 LinkedList의 차이

  • 주소의 연속성 (Arr O, List X)
  • Arr는 접근 속도가 빠름
  • List는 추가, 삽입, 삭제에 용이함

Cord

Class

// 제네릭 형식의 Node Class 선언
public class Node<T>
{
    // Node가 가지는 값
    public T data;
    // 다음 Node의 주소
    public Node<T> next = null;
    // 이전 Node의 주소
    public Node<T> prev = null;
}


// 제네릭형식으로 class 선언
public class LinkedList<T>
{
    // 리스트의 첫 번째 Node 
    public Node<T> head = null;

    // List의 길이
    public int Count { get; private set; }
}

LinkedList class와 Node class 제네릭 형식으로 선언한다.
Node에는 (값, 다음 Node, 이전 Node)를 가지게 한다.

LinkedList에는 (첫 번째 Node가 되는 head, 현재 길이를 나타내는 Count)를 프로퍼티로 선언하였다.

Add() & PrintAll()

// 노드 넣기
public void Add(T _data)
{
    if (Count == 0)
    {
        // 맨 처음 Add할때 Head 지정
        head = new Node<T>();
        head.data = _data;
    }
    else
    {
        // 두번째 부터 다음 Node와 연결 시켜주기
        Node<T> mid = head;

        // next 2 (count >= 3) 부터 for문을 통해 Node를 찾는다
        for (int idx = 0; idx < Count - 1; idx++)
        {
            mid = mid.next;
        }
        mid.next = new Node<T>();
        mid.next.data = _data;  // 다음 Node 연결
        mid.next.prev = mid;    // 이전 Node 연결
    }

    Count++;
}

// List의 모든 Node 출력하기
public void PrintAll()
    {
        // 예외처리
        if (Count == 0)
        {
            Debug.LogError("Empty List");
            return;
        }

        Node<T> mid = head;

        while (mid != null)
        {
            Debug.Log(mid.data);
            mid = mid.next;
        }
    }

이제 List에 요소들을 추가하기 위한 Add()와 출력을 위한 PrintAll()을 만들어 보았다



Result0

물론, 조사식에서 list 내부를 들여다 보면 데이터들이 이렇게 잘 들어와 있다.

GetData()

if (Count <= _idx)  // 예외처리
{
    Debug.LogError("list index out of range"); 
    return default(T);  // 0을 반환
}
else // 지정 _idx의 data 반환
{
    Node<T> mid = head;

    // _idx의 Node 찾기
    for (int idx = 0; idx < _idx; idx++)
    {
        mid = mid.next;
    }

    // 해당 Node의 data 반환
    return mid.data;
}



Result3-2

예외처리도 아주 잘 되었다.

RemoveLast() & Remove()

// 마지막 Node 제거
public void RemoveLast()
{
    // 예외처리
    if (Count <= 0) 
    {
        Debug.LogError("List index out of range"); 
        return;
    }

    if (Count == 1) // Node(Head) 가 단 하나 있을 경우
    {
        head.data = default(T);
        head = null;
    }
    else // Node가 2개 
    {
        Node<T> last = head;

        // 3개이상이면 for문으로 Node 탐색
        for (int idx = 0; idx < Count - 2; idx++)
        {
            last = last.next;
        }

        last.next.data = default(T);
        last.next.prev = null;
        last.next = null;
    }

    Count--;
}

// 지정 Node 제거
public void Remove(int _idx)
{
    if (_idx == 0)  // 제거할 Node가 첫 번째 Node 일경우
    {
        // head 제거 전 다음 Node를 미리 저장
        Node<T> headNext = head.next;

        head.data = default(T);
        head = null;

        // 저장한 다음 Node를 head에 대입
        head = headNext;
        head.prev = null;
    }
    else
    {
        Node<T> target = head;  // 제거할 Node
        Node<T> targetNext;     // 제거할 Node의 다음 Node
        Node<T> targetPrev;     // 제거할 Node의 이전 Node

        if (_idx < Count - 1) // head와 끝 Node 사이
        {
            // 제거할 Node 탐색
            for (int idx = 0; idx < _idx - 1; idx++)
            {
                target = target.next;
            }
            targetNext = target.next.next;
            targetPrev = targetNext.prev;

            // target Node 제거
            target.next.data = default(T);
            target.next.prev = null;
            target.next = null;

            // 끊어진 Node 재연결
            target.next = targetNext;
            target.next.prev = targetPrev;
        }
        else // 끝에 있는 Node 일때
        {
            for (int idx = 0; idx < _idx - 1; idx++)
            {
                target = target.next;
            }
            target.next.data = default(T);
            target.next.prev = null;
            target.next = null;
        }
    }

    Count--;
}



이번에 추가한 것은 마지막 Node제거와 지정 index의 Node 제거 이다.

Insert()

// _idx에 Node 추가하기
public void Insert(int _idx, T _value)
{
    // 예외 처리
    if ( Count < _idx) 
    { 
        Debug.LogError("List index out of range"); 
        return; 
    }

    if (_idx == 0)   // 맨 처음 idx에 삽입 할때
    {
        // 새로운 Node 생성
        Node<T> newHead = new Node<T>();
        newHead.data = _value;

        // 기존의 head를 temp에 저장
        Node<T> temp = head;
        temp.prev = newHead;

        // 새로 추가된 Node를 head로 대입하고 temp와 연결
        head = newHead;
        newHead.next = temp;
    }
    else  // _idx가 1 이상일 경우
    {
        Node<T> mid = head;
        Node<T> newNode;

        for (int idx = 0; idx < _idx - 1; idx++)
        {
            mid = mid.next;
        }

        // 새로운 Node와 value 추가
        newNode = new Node<T>();
        newNode.data = _value;
        newNode.prev = mid;

        // 새로 추가된 Node와 뒷 Node 연결
        newNode.next = mid.next;
        newNode.next.prev = newNode;

        // 새 Node와 앞 Node 연결
        mid.next = newNode;        
    }

    Count++;
}

지정 Index에 Node 추가하기 완성 ~!
전체 코드는 다른 Repository에 업로드 할 것이다.
다음은 LinkedList를 이용한 HashTable을 포스팅 할거다 .

참고