C# LinkedList 만들기 (Generic type)

C#으로 LinkedList 만들기

 

리스트의 type을 Generic화 시킨 LinkedList를 만들어 보도록 하겠다.

 

이전 글에서 C++로 LinkedList를 template화 하여 어느 타입의 데이터든 관리할 수 있도록 만들었는데 아래는 참고 링크이다.

https://suldenlion.tistory.com/90

 

C++의 템플릿과 C#의 제네릭은 내용상 결이 같다.

다만 C++와 C#, Java의 템플릿/제네릭은 약간의 차이가 있는데 조금 정리해 보겠다.

완전하게 이해하지 못한 부분도 있고 웹 서칭을 참고하여 정리해 보는 것이므로 내용에 오류가 있을 수 있다.

 

C++은 한번 컴파일이 되면 그 뒤로는 동일한 기계어 코드만 실행하게 된다 (컴파일 총 1번). 하지만 C# 같은 경우는 먼저 컴파일을 한번 하여 IL 코드(가상시스템을 실행하는 동안 바이트 코드로 변환되는 스택 기반 어셈블리 언어)로 컴파일이 된다. 이 컴파일 된 결과물이 CLR(프로그램 코드를 위한 실행 환경을 정의하는 마이크로소프트의 공통 언어 기반 표준의 기능)을 통해서 실행될 때, 현재 CLR이 실행되고 있는 환경에 맞춰서 다시 한번 기계어 코드로 컴파일이 진행되게 된다 (컴파일 총 2번).

 

Template은 실제로 사용하지 않으면 코드가 아예 생성되지 않고, C#의 Generic은 사용되지 않더라도 그에 관련된 정보를 저장하기 위한 메타데이터가 생성된다. (이러한 메타데이터를 통해 실제로 사용될 때, 관련 코드들을 생성)

 

Java도 바이트 코드에 generic과 관련된 메타데이터를 저장해두고 실행할 때, 이 바이트 코드를 기계어로 컴파일 한다는 점에서 C#과 비슷하다

 

윗 내용을 종합해보면 C++의 Template은 한번의 컴파일로 최종 결과물이 나온다. → 현재 컴파일하는 시점에 해당 코드가 유효한지 모두 확인 가능

반면 generic은 IL 이나 바이트 코드로 컴파일이 되어도 최종 결과물이 아니며 두번째 컴파일때 구현한다. → 첫번째 컴파일시에 결정할 수 없음

 

여기까지가 템플릿과 제네릭의 차이이고 C#의 제네릭과 Java의 제네릭의 차이도 보겠다.

 

C#은 제네릭의 도입으로 컴파일시에 에러를 검출할 수 있게 하고, 불필요한 캐스팅을 못하게 하여 성능이 제네릭을 사용하지 않을때에 비해서도 좋아졌다. 

Java는 제네릭을 사용할 때, 컴파일 시 에러를 검출할 수는 있지만, 실제로 동작하는 코드는 제네릭을 사용하지 않을때와 같아서 성능개선이 없다고 한다.

요약하자면, C#은 성능과 타입의 안정성을 확보하고 약간의 하위호환성을 포기한 것이고, Java는 호환성과 타입의 안정성을 확보하고 약간의 성능을 포기한 것이다.

 

그리고 자바의 제네릭은 한번 컴파일 된 바이트 코드는 타입 정보를 갖지 않는다고 한다. 그래서 자바는 제네릭 리스트에 담긴 객체의 타입을 유추해 낼 수 없다.

반면에 C#은 클래스를 로딩할 때 CLR이 동적으로 타입정보를 담은 클래스를 생성한다고 한다. 그로인해 C#은 타입 유추가 가능하다.

 

위의 이유가 정수형의 LinkedList가 있다고 치면, C#은 LinkedList<int> 변수형 그대로로, Java는 LinkedList<Integer> int의 wrapper 객체 형태로 쓰는 것인듯 하다. 

 

이제 제네릭을 담는 LinkedList 코드를 보겠다.

using System;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSLinkedList
{
    class Node<T>
    {
        T data;
        Node<T> next;
        public Node()
        {
            data = default(T);
            next = null;
        }
        public Node(T data)
        {
            this.data = data;
            this.next = null;
        }
        public T Data
        {
            get { return data; }
            set { data = value; }
        }
        public Node<T> Next
        {
            get { return next; }
            set { next = value; }
        }
    }
    class LinkedList<T>
    {
        Node<T> header;
        int count;
        public LinkedList()
        {
            header = null;
            count = 0;
        }
        public void addFirst(T data)
        {
            Node<T> newNode = new Node<T>(data);
            newNode.Next = header;
            header = newNode;
            count++;
        }
        public void add(T x)
        {
            Node<T> tmp = header;
            Node<T> newNode = new Node<T>(x);

            if (count == 0)
            {
                addFirst(x);
                return;
            }
            while (tmp.Next != null)
            {
                tmp = tmp.Next;
            }
            count++;
            tmp.Next = newNode;
        }
        public void remove(T x)
        {
            Node<T> tmp;
            Node<T> follow;

            tmp = header;
            follow = tmp;
            if (count == 0)
            {
                Console.WriteLine("List is empty");
                return;
            }
            if (header.Data.Equals(x))
            {
                header = header.Next;
                count--;
                return;
            }
            while (tmp != null)
            {
                if (tmp.Data.Equals(x))
                {
                    follow.Next = tmp.Next;
                    count--;
                    return;
                }
                follow = tmp;
                tmp = tmp.Next;
            }
            Console.WriteLine("Cannot find element");
        }
        public void addAt(int index, T x)
        {
            Node<T> tmp = header;
            Node<T> newNode = new Node<T>(x);

            if (index == 0)
            {
                addFirst(x);
                return;
            }
            if (index > count)
            {
                Console.WriteLine("Incorrect index");
                return;
            }
            for (int i = 0; i < index-1; i++)
            {
                tmp = tmp.Next;
            }
            newNode.Next = tmp.Next;
            tmp.Next = newNode;
            count++;
        }
        public T this[int index]  //indexer
        {
            get
            {
                Node<T> tmp = header;
                T value;

                if (count == 0)
                {
                    Console.WriteLine("List is empty");
                    Environment.Exit(-1);
                }
                if (index == 0)
                {
                    value = header.Data;
                    return value;
                }
                if (index > count - 1)
                {
                    Console.WriteLine("Incorrect index");
                    Environment.Exit(-1);
                }
                for (int i = 0; i < index; i++)
                {
                    tmp = tmp.Next;
                }
                value = tmp.Data;
                return value;
            }
            set
            {
                Node<T> tmp = header;

                if (count == 0)
                {
                    Console.WriteLine("List is empty");
                    return;
                }
                if (index > count - 1)
                {
                    Console.WriteLine("Incorrect index");
                    return;
                }
                for (int i = 0; i < index; i++)
                {
                    tmp = tmp.Next;
                }
                tmp.Data = value; // value = property
            }
        }
        public T get(int index)
        {
            Node<T> tmp = header;
            T value;

            if (count == 0)
            {
                Console.WriteLine("List is empty");
                Environment.Exit(-1);
            }
            if (index == 0)
            {
                value = header.Data;
                return value;
            }
            if (index > count-1) 
            {
                Console.WriteLine("Incorrect index");
                Environment.Exit(-1);
            }
            for (int i = 0; i < index; i++)
            {
                tmp = tmp.Next;
            }
            value = tmp.Data;
            return value;
        }
        public void set(int index, T x)
        {
            Node<T> tmp = header;

            if (count == 0)
            {
                Console.WriteLine("List is empty");
                return;
            }
            if (index > count - 1)
            {
                Console.WriteLine("Incorrect index");
                return;
            }
            for (int i = 0; i < index; i++)
            {
                tmp = tmp.Next;
            }
            tmp.Data = x;
        }
        public override string ToString()
        {
            String s;
            Node<T> tmp = header;

            s = "[";
            while (tmp != null)
            {
                s = s + tmp.Data;
                if (tmp.Next != null)
                {
                    s += ", ";
                }
                tmp = tmp.Next;
            }
            s = s + "]";

            return s;
        }

    }

    class Student
    {
        public String name;
        public int grade;
        public Student()
        {
            name = null;
            grade = 0;
        }
        public Student(String name, int grade)
        {
            this.name = name;
            this.grade = grade;
        }
        public override string ToString()
        {
            String s = name + ", " + grade + " ";
            return s;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            LinkedList<Student> xList = new LinkedList<Student>();
            xList.add(new Student("Kim", 20));
            xList.addFirst(new Student("Lee", 30));
            xList.addFirst(new Student("Park", 50));
            Console.WriteLine(xList);

            LinkedList<String> sList = new LinkedList<string>();
            sList.addFirst("Kim");
            sList.addFirst("Lee");
            sList.addFirst("Park");
            sList.addFirst("Kwon");
            Console.WriteLine(sList);

            LinkedList<int> list = new LinkedList<int>();
            list.addFirst(10);
            list.addFirst(20);
            list.addFirst(30);
            list.add(100);
            list.remove(30);
            list.addAt(3, 200);
            int p = list[2];
            Console.WriteLine(p);
            Console.WriteLine(list.get(3));
            Console.WriteLine(list);
            //list.set(3, 1000);
            list[2] = 1000;
            Console.WriteLine(list);
        }
    }
}

 

간단하게 add(), remove(), get(), set() 등의 작업만 하는 LinkedList이다. 메인함수에서는 LinkedList에 Student 객체를 넣어서도 테스트해보고 String, int에 대해서도 테스트 한다.

Student 객체는 String 이름과 int 등급을 데이터 멤버로 가지고, 생성자와 toString이 있다. toString()은 Object 클래스에서 상속받아 오는 것이므로 override를 적어 재정의 해줄수 있게 한다. 

 

코드의 위에서 부터 보자면 Node 클래스를 제네릭 타입으로 정의해 주고 data의 변수는 Type, 다음 노드를 가리킬 Node<Type> next가 노드를 구성한다. 

노드의 빈 생성자에서는

data가 default(Type)으로 명시되어 있는데, 값이 없다는 것을 모호하게 표현해주는 것(혹은 생략시켜주는것)인것 같다. 데이터의 타입을 모르기 때문에 NULL이 될수도 있고 0이 될수도 있음을 뜻하는 syntax인듯하다.

 

노드의 data와 next는 private으로 정의되어 있으므로, getters와 setters를 만들어준다.

 

다음으로 LinkedList를 보면, add()와 remove(), get()과 set() 등은 제네릭 타입을 다루도록 T를 잘 붙이며 정의해 주고 인덱서에 해당하는 부분을 보고 마무리 짓겠다.

 

메인의 마지막 부분을 보면 int 타입의 LinkedList를 만들어 쓴다.

30,20,10,100 넣고 30 빼고 3번 인덱스에 200을 넣으면서 리스트에는 [20, 10, 100, 200]이 있게 된다.

 

정수 p를 만들어 list[2]에 해당하는 100을 넣어줄 것인데, C#은 인덱서를 통해 객체내의 데이터에 접근할 수 있다. 자바의 Iterator인 셈이다.

인덱서의 get은 'int p = list[2];' 해주는 부분과 같고, set은 'list[2] = 1000;' 해주는 부분과 같다.

내용은 이제 Node들을 traverse 하면서 원하는 위치의 값을 가져다 주거나 그 위치의 값을 바꿔주는 일을 한다.

Exception이 생기면 Environment.Exit(-1);을 하여 프로그램을 종료시켜준다.