LinkedList의 구현

List<T>나 LinkedList<T> 클래스는 C#에서 컬렉션으로 제공하고 있다. 하지만 자료구조를 직접 만드는 것이 프로그램 공부에 도움이 된다는 설명으로 책에서 시킨다.

 

LinkedList에 대한 자세한 설명은 검색

 

LinkedList 클래스를 별도의 파일로 만들어 놓고 계속 쓸 예정이다.

 

Node 클래스의 필드와 메소드

필드 또는 메소드	내용
int data	노드에 저장되는 값
Node next	리스트에서 디음에 연결되는 노드입니다.
Node(int data)	Node클래스의 생성자. data를 저장하는 Node를 생성

LinkedList 클래스의 필드와 메소드

 

필드 또는 메소드	내용
Node head	리스트의 첫 번째 노드
void InsertFront(int data)	리스트의 맨 앞에 data를 추가한다.
void InsertLast(int data)	리스트이 맨 뒤에 data를 추가한다.
Node GetLastNode()	리스트의 맨 뒤 노드의 레퍼런스를 리턴
void DeleteNode(int key)	리스트에서 key가 저장된 노드를 삭제한다.
void Reverse()	리시트의 노드 순서를 거꾸로 만든다.
void Print()	리스트의 노드들을 순서대로 출력한다.
void InsertAfter(int p, int d)	p가 저장된 노드 뒤에 d를 추가한다.

using System;
using System.ComponentModel;

namespace CPractice
{
    class Node //노드 클래스의 선언
    {
        internal int data; //링크드리스트 의 데이터
        internal Node next; //다음을 가리키는 노드
        public Node(int data)//생성자
        {
            this.data = data;
            next = null;
        }
    }
    class LinkedList
    {
        Node head; //첫번째 노드를 가리키는 head

        internal void InsertFront(int data) //data를 갖는 노드를 새로만들어 리스트의 맨 앞에 추가
        {
            Node node = new Node(data);
            node.next = head;
            head = node;
        }
        internal void InsertLast(int data) //data를 갖는 노드를 새로만들어 리스트의 맨뒤에 추가
        {
            Node node = new Node(data);
            if(head ==null)
            {
                head = node;
                return;
            }
            Node lastNode = GetLastNode(); //마지막 노드를 알기 위함
            lastNode.next = node;
        }
        internal Node GetLastNode()
        {
            Node temp = head;
            while (temp.next !=null)//노드의 끝에 도달
            {
                temp = temp.next;  //temp에 마지막 노드 저장
            }
            return temp; //리턴
        }

        internal void InsertAfter(int prev, int data)
        {
            Node prevNode = null;

            for (Node temp = head; temp != null; temp = temp.next)
                if (temp.data == prev) //노드를 앞에서 부터 훝어서 값이 prev인 곳을 찾는다.
                    prevNode = temp;
            if(prevNode == null)
            {
                Console.WriteLine("{0} data is not in the list");
                return;
            }
            Node node = new Node(data); 
            node.next = prevNode.next; //사이에 낑겨넣기
            prevNode.next = node;
        }
        internal void DeleteNode(int key)
        {
            Node temp = head; 
            Node prev = null;
            if(temp != null && temp.data ==key)
            {//key값을 data로 저장하고 있는 부분 찾기
                head = temp.next;
                return;
            }
            while(temp ==null)
            {
                prev = temp;
                temp = temp.next;
            }
            prev.next = temp.next;
        }
        internal void Reverse()
        {
            Node Prev = null;
            Node current = head;
            Node temp = null;
            while(current !=null)
            {
                temp = current.next;
                current.next = Prev;
                Prev = current;
                current = temp;
            }
            head = Prev;
        }
        internal void Print()
        {
            for (Node node = head; node != null; node = node.next)
                Console.Write(node.data + " -> ");
            Console.WriteLine();
        }

    }

    
    class Program
    {
        static void Main(string[] args)
        {
            

        }
       

    }
}

 

internal은 같은 어셈블리 내부에서는 public, 외부에서는 private과 같은 역할을 한다. 

 

 

기본적인 형태

 

InsertFront

InsertLast

InsertAfter