자료구조 - Linked List (예제) - C#

 

 

Single Linked List 를 구현하는 예제 클래스와 메소드 예제이다.

 

 

 

우선 데이터와 포인터를 담아둘 Class를 정의하고 (Node)

 

이 Node들을 연결해 LinkedList로 만들기 위한 메소드들이 포함된 Class도 만들어주자.

 

 

LinkedList Class에는 Node의 시작 노드를 담아둘 head를 따로 정의해주고 

 

새로운 Node를 앞에 붙일 것인지, 뒤에 붙일 것인지에 따라 해당 기능을 구현 할 함수를 따로 만들었다.

 

 

그리고 특정 값을 가진 데이터를 삭제하는 노드, 지금까지의 노드들을 확인 할 Print 함수까지 구현하면 

 

Single Linked List를 구현할 수 있는 기능들이 완성된다.

 

 

 

 

Node Class

 public class Node // 단일 노드 클래스
 {
     public int data; // 노드의 데이터 값
     public Node next; // 다음 노드 포인터

     public Node(int d) // 노드 생성자
     {
         data = d;
         next = null;
     }
 }

 

 

 

 

LinkedList Class

  public class LinkedList // 연결 리스트 정의하는 클래스
  {
      public Node head; // 리스트의 시작 노드
     
      public void AddFront(int data) // 해당 리스트 앞에 새로운 노드 추가
      {
          Node newNode = new Node(data); // 새 노드 생성
          newNode.next = head; // 새 노드의 다음 노드가 현재의 노드
          head = newNode; // 현재 노드의 헤드를 갱신
      }

      public void AddEnd(int data)
      {
          Node newNode = new Node(data);
          
          if(head == null)
          {
              head = newNode;
              return;
          }

          Node lastNode = GetLastNode(); // 마지막 노드를 찾음
          lastNode.next = newNode;       // 마지막 노드의 다음 노드를 새 노드로 설정
      }


      private Node GetLastNode() // 리스트에서 마지막 노드를 반환하는 메소드
      {
          Node temp = head;
          while(temp.next != null) 
          {
              temp = temp.next; // 다음 노드로 이동
          }

          return temp;
      }

      public void DeleteNodeByKey(int key) // 특정 key를 가진 노드를 삭제하는 메소드
      {
          Node temp = head;
          Node prev = null;

          // 삭제할 노드가 헤드인 경우
          if (temp != null && temp.data == key)
          {
              head = temp.next; // 헤드를 다음 노드로 이동
              return;
          }

          // 삭제할 노드를 찾을 때까지 이동
          while (temp != null && temp.data != key)
          {
              prev = temp;      // 현재 노드를 이전 노드로 설정
              temp = temp.next; // 다음 노드로 이동
          }

          // 키를 가진 노드를 찾지 못한 경우
          if (temp == null) 
              return;

          // 이전 노드의 다음 노드를 삭제 노드의 다음 노드로 설정
          prev.next = temp.next;
      }

      public void PrintAllNodes() // 모든 노드를 콘솔에 출력하는 메소드
      {
          Node current = head;
          while (current != null)
          {
              Console.WriteLine(current.data);
              current = current.next; // 다음 노드로 이동
          }
      }
  }

 

 

 

 

잘 돌아가는지 예제를 돌려보자.

 

  public static void Main()
  {
      LinkedList linkedlist = new LinkedList();

      Console.WriteLine("Add Front");

      linkedlist.AddFront(10);
      linkedlist.AddFront(20);
      linkedlist.AddFront(30);

      linkedlist.PrintAllNodes();

      Console.WriteLine("-----------------------");


      Console.WriteLine("Add End");
      linkedlist.AddEnd(100);
      linkedlist.AddEnd(200);
      linkedlist.AddEnd(300);

      linkedlist.PrintAllNodes();

      Console.WriteLine("-----------------------");

      Console.WriteLine("Add Front 800, Delete 30");

      linkedlist.AddFront(800);

      linkedlist.DeleteNodeByKey(30);

      linkedlist.PrintAllNodes();

  }

 

 

 

 

Front와 End 모두 잘 돌아가고

 

중간 삭제도 잘 동작하는것 같다.