단일연결리스트 (SinglyLinkedList) in c#

Data structure 2020. 10. 23. 08:31
반응형
using System;

public class App {
  //생성자 
  public App () {

    var list = new SinglyLinkedList ();

    for (int i = 0; i < 5; i++) {
      list.Add (new Node (i));
    }

    var node = list.GetNode (2);
    list.Remove (node);

    node = list.GetNode (1);
    list.AddAfter (node, new Node (100));

    int count = list.Count ();
    Console.WriteLine ("count: {0}", count);

    //0 1 100 3 4 
    for (int i = 0; i < count; i++) {
      var n = list.GetNode (i);
      Console.WriteLine (n.data);
    }
  }
}
public class Node {
    public int data;
    public Node next;
    //생성자 
    public Node (int data) {
        this.data = data;
    }
}
using System;

public class SinglyLinkedList {
    private Node head;
    //생성자 
    public SinglyLinkedList () {

    }

    public void Add (Node newNode) {
        if (head == null) {
            this.head = newNode;
        } else {
            var current = this.head;
            //마지막 노드로 이동후 추가 
            while (current != null && current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void AddAfter (Node current, Node newNode) {

        if (head == null || current == null || newNode == null) {
            throw new InvalidOperationException ();
        }

        newNode.next = current.next;
        current.next = newNode;

    }

    public void Remove (Node removeNode) {
        if (head == null || removeNode == null)
            return;
        //삭제할 노드가 첫 노드
        if (removeNode == head) {
            head = head.next;
            removeNode = null;
        } else {
            //첫 노드가 아니면 해당 노드 검색후 삭제
            var current = head;
            //단방향이므로 삭제할 노드의 바로 이전 노드를 검색 해야 함 
            while (current != null && current.next != removeNode) {
                current = current.next;
            }

            if (current != null) {
                //이전 노드의 next에 삭제 노드의 next를 할당 
                current.next = removeNode.next;
                removeNode = null;
            }
        }

    }

    public Node GetNode (int index) {
        var current = head;
        for (int i = 0; i < index && current != null; i++) {
            current = current.next;
        }

        return current;
    }

    public int Count () {
        int cnt = 0;

        var current = this.head;

        while (current != null) {
            cnt++;
            current = current.next;
        }

        return cnt;
    }
}
반응형

'Data structure' 카테고리의 다른 글

C# 으로 구현한 Deque (덱)  (0) 2020.11.19
배열로 구현한 Stack in C#  (0) 2020.10.23
Binary Search Tree  (0) 2020.05.29
이진 트리  (0) 2019.08.14
이진 탐색 (Binary Search)  (0) 2019.08.14
: