C# 자료구조 :: 링크드리스트, 더블링크드리스트 직접 작성해보기

 

링크드리스트의 개념

 

 

노드로 링크드리스트 구현하기

 

링크드리스트 코드 예제

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class MyNode<T> 
{
    // 노드 안에 있는 데이터
    public T Data;
    
    // 내가 가리키는 다음 노드
    public MyNode<T> Next = null;

    public MyNode(T data)
    {
        Data = data;
    }
}

public class MyLinkedList<T>
{
    //맨 앞을 가리키는 노드
    private MyNode<T> HeadNode;
    
    
    public void Add(bool isFront, T data)
    {
        MyNode<T> newNode = new MyNode<T>(data);
        if (isFront)    //isFront == true : 앞에서 추가
        {
            newNode.Next = HeadNode;
            HeadNode = newNode;
        }
        else    //isFront == false : 뒤에 추가
        {
            if (HeadNode == null)   // 리스트가 빈 경우 헤드노드=새노드
                HeadNode = newNode;
            else
            {
                MyNode<T> iterator = HeadNode;  //헤드노드부터 시작
                while (iterator.Next != null)   //마지막노드(Next가 null)까지 반복
                {
                    iterator = iterator.Next;
                }

                iterator.Next = newNode;//마지막노드의 Next에 새 노드 추가
            }
        }
    }

    public void PrintIteration()    //링크드리스트 전체를 돌면서 프린트
    {
        var curNode = HeadNode;
        while (curNode != null) //마지막(null)일때까지 while문을 돈다.
        {
            Debug.Log(curNode.Data);
            curNode = curNode.Next;
        }
    }

    public void RemoveAt(int removeIndex)
    {
        if (HeadNode == null)   //빈노드면 return;
            return;
        
        
        if (removeIndex == 0)   //지우고자 하는 노드인덱스가 0이면 
        {
            HeadNode = HeadNode.Next;   //헤드노드를 다음으로 넘겨줌
            return;
        }

        int currentIndex = 0;
        MyNode<T> curNode = HeadNode;
        
        while (curNode.Next != null)
        {
            if (currentIndex == removeIndex - 1)    //지우고자하는 노드보다 한칸 앞의 노드에서
            {
                if (curNode.Next != null)
                {
                    curNode.Next = curNode.Next.Next;   //Next에 지우려는 노드의 Next를 넣어준다.
                }
                else
                {
                    curNode.Next = null;
                }
                
                break;
            }
            curNode = curNode.Next; //curNode를 한칸씩 옮겨감
            currentIndex++;
        }
    }
    
}

 

 

 

★★★

더블링크드리스트 코드 직접 작성하기

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class DoubleNode<T> 
{
    // 노드 안에 있는 데이터
    public T Data;
    
    // 내가 가르킬 다음 노드
    public DoubleNode<T> Prev = null;
    public DoubleNode<T> Next = null;
    
    public DoubleNode(T data)
    {
        Data = data;
    }
}

public class MyDoubleLinkedList<T>
{
    private DoubleNode<T> HeadNode=null;
    private DoubleNode<T> TailNode=null;
    private int listLength = 0;

    public void AddFirst(T data)
    {
        DoubleNode<T> newNode = new DoubleNode<T>(data);
        if (HeadNode == null)   
        {   //리스트가 비어있으면 새노드를 가리키도록 함
            HeadNode = newNode;
            TailNode = newNode;
        }
        else
        {   //앞에 추가
            HeadNode.Prev = newNode;
            newNode.Next = HeadNode;
            HeadNode = newNode;
        }
        Debug.Log("AddFirst: "+HeadNode.Data);
        listLength++;
    }

    public void AddLast(T data)
    {
        DoubleNode<T> newNode = new DoubleNode<T>(data);
        if (TailNode == null)   
        {   //리스트가 비어있으면 새노드를 가리키도록 함
            HeadNode = newNode;
            TailNode = newNode;
        }
        else
        {   //뒤에 추가
            TailNode.Next = newNode;
            newNode.Prev = TailNode;
            TailNode = newNode;
        }
        Debug.Log("AddLast: "+TailNode.Data);
        listLength++;
    }

    public void Print()
    {
        //헤드노드부터 뒤로 가면서 프린트
        DoubleNode<T> printer = HeadNode;
        while (printer != null)
        {
            Debug.Log(printer.Data);
            printer = printer.Next;
        }
    }
    
    public void PrintReverse()
    {
        //테일노드부터 앞으로 가면서 프린트
        DoubleNode<T> printer = TailNode;
        while (printer != null)
        {
            Debug.Log(printer.Data);
            printer = printer.Prev;
        }
    }

    public void RemoveAt(int indexToRemove)
    {
        //삭제할 인덱스는 리스트크기보다 작아야함.
                if (indexToRemove >= listLength)
                {
                    Debug.Log("RemoveAt ERROR : Out of Index");
                    return;
                }
        
        //빈 리스트에서는 노드삭제 불가
        if (listLength == 0)
        {
            Debug.Log("RemoveAt ERROR : List is Empty.");
            return;
        }
        
        //삭제할 인덱스가 리스트 길이의 절반보다 작으면 앞에서부터 인덱스를 찾고
        //절반 이상이면 뒤에서부터 탐색하여 효율적으로 삭제한다.
        if (indexToRemove <= (listLength-1) / 2)
        {
            if (indexToRemove == 0) //맨 앞 요소 삭제시
            {
                Debug.Log("RemoveAt First Node: "+HeadNode.Data);
                if (listLength == 1)        //리스트 요소가 1개일 때
                {
                    Debug.Log("Clear the List.");
                    HeadNode = null; 
                    TailNode = null;
                    return;
                }
                HeadNode.Next.Prev = null;
                HeadNode = HeadNode.Next;
            }
            else
            {
                int index = 0;
                DoubleNode<T> iterator = HeadNode;  //HeadNode에서 시작해서 뒤로감
                
                while (index < indexToRemove)   //indexToRemove번째 노드를 찾는다.
                {
                    iterator = iterator.Next;
                    index++;
                }
                //지워야 할 요소의 앞과 뒤를 연결
                Debug.Log("RemoveAt(" + index + "): "+iterator.Data);
                iterator.Next.Prev = iterator.Prev;
                iterator.Prev.Next = iterator.Next;
            }    
        }
        else
        {   
            if (indexToRemove == listLength-1) //마지막 요소 삭제시
            {
                Debug.Log("RemoveAt Last Node: "+TailNode.Data);
                TailNode.Prev.Next = null;
                TailNode = TailNode.Prev;
            }
            else
            {
                int index = listLength - 1;
                DoubleNode<T> iterator = TailNode; //TailNode에서 시작해서 앞으로감
                
                while (index > indexToRemove) //indexToRemove번째 노드를 찾는다.
                {
                    iterator = iterator.Prev;
                    index--;
                }
                //지워야 할 요소의 앞과 뒤를 연결
                Debug.Log("RemoveAt(" + index + "): "+iterator.Data);
                iterator.Next.Prev = iterator.Prev;
                iterator.Prev.Next = iterator.Next;
            } 
        }
        listLength--;
    }
}