선형 연결리스트만들기

LinkedList.zip
스택기반 단순 연결리스트를 C#을 이용하여 만들어 보았다.
연결리스트란 쉽게 말해서 정적인 배열이 아닌 동적인 배열이라 할수있다.
C#에서의 Array라고 생각하면 되겠다.
연결리스트는 노드와 링크로 이루어져있으며 시작노드로 시작해서 끝노드로 종료된다.

예) head(시작)->노드->노드->노드->tail(끝) *끝의 링크는 끝을 가르킨다


1. 노드자료형은 노드클래스로 만든다.
심플하게 만들기위해 데이터와 링크(next)로 구성했다. next는 Node클래스를 가르킨다.
class Node
 {
  public int nKey;
  public Node next;
 }

2. 연결리스트 초기화
노드의 시작과 끝을 전역변수로 선언
노드의 시작점과 끝점을 초기화시켜준다

Node _head;
Node _tail;
public void Init_Link()
  {
   _head = new Node();
   _tail = new Node();
   _head.next = _tail;
   _tail.next = _tail;   *링크끝의 링크는 끝을 가르킨다
  }

3.노드 삽입
임시 노드를 생성하고 임시노드의 링크를 시작링크 다음에 연결된 링크로 바꾼후
시작노드의 다음노드에 임시노드를 넣는다(스택기반 연결리스트이기때문)
이렇게 되면 아래부터 Node클래스의 메모리가 차곡차곡 쌓이게 된다
public int InsertNode(int nKey)
  {
   Node tempNode;
   if ((tempNode = new Node()) == null)
   {
    Console.WriteLine("경고 : 메모리 부족");
    return -1;
   }
   try
   {
    tempNode.nKey = nKey;
    tempNode.next = _head.next;
    _head.next = tempNode;
    return nKey;
   }
   catch (Exception ex)
   {
    Console.WriteLine(ex.Message);
    return -1;
   }
  }

4.노드삭제
임시 노드를 생성하고 헤드다음노드를 임시노드에 넣구 헤드 다음노드를 임시노드 다음으로 연결하면
헤드 다음의 노드는 떨어져 나가서 닷넷 가비지컬렉터에 의해서 정리될것이다.
public int DeleteNode()
  {
   Node tempNode;
   int i;
   if (_head.next==_tail)
   {
    Console.WriteLine("경고 : 삭제할 메모리가 없습니다.");
    return -1;
   }

   try
   {
    tempNode = _head.next;
    i = tempNode.nKey;
    _head.next = tempNode.next;

    return i;
   }
   catch(Exception ex)
   {
    Console.WriteLine(ex.Message);
    return -1;
   }

  }

5. 출력
시작노드를 출발점으로 루프를 돌면 끝노드에 도달할때까지 화면에 뿌려준다

public void PrintNode()
  {
   Node tempNode;
   tempNode = _head.next;
   while (tempNode != _tail)
   {
    Console.WriteLine("{0}",tempNode.nKey);
    tempNode = tempNode.next;
   }
  }
출처: sun77.egloos.com