Home > Algorithm > 2024 > ๐Ÿ“ฆ[DS,Algorithm] ๋…ธ๋“œ(Node)

๐Ÿ“ฆ[DS,Algorithm] ๋…ธ๋“œ(Node)
DataStructure Algorithm

1๏ธโƒฃ Node(๋…ธ๋“œ).

Node(๋…ธ๋“œ) ๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ, ํŠธ๋ฆฌ, ๊ทธ๋ž˜ํ”„ ๋“ฑ์˜ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ๊ธฐ๋ณธ์ ์ธ ๋‹จ์œ„ ์š”์†Œ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

๋…ธ๋“œ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋ฉฐ, ๋‹ค๋ฅธ ๋…ธ๋“œ์™€์˜ ์—ฐ๊ฒฐ์„ ๋‚˜ํƒ€๋‚ด๋Š” ํฌ์ธํ„ฐ(์ฐธ์กฐ)๋ฅผ ํฌํ•จํ•ฉ๋‹ˆ๋‹ค.

1๏ธโƒฃ Node์˜ ๊ตฌ์„ฑ ์š”์†Œ.

  1. ๋ฐ์ดํ„ฐ(Data) : ๋…ธ๋“œ๊ฐ€ ์ €์žฅํ•˜๋Š” ์‹ค์ œ ๊ฐ’์ž…๋‹ˆ๋‹ค. ์ด๋Š” ์ˆซ์ž, ๋ฌธ์ž, ๊ฐ์ฒด ๋“ฑ ๋ชจ๋“  ๋ฐ์ดํ„ฐ ํƒ€์ž…์ด ๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  2. ํฌ์ธํ„ฐ(์ฐธ์กฐ, Pointer) : ๋‹ค์Œ ๋…ธ๋“œ(๋˜๋Š” ๋‹ค๋ฅธ ๊ด€๋ จ๋œ ๋…ธ๋“œ)๋ฅผ ๊ฐ€๋ฆฌ์ง€๋Š” ์ฐธ์กฐ์ž…๋‹ˆ๋‹ค. ํฌ์ธํ„ฐ์˜ ์ˆ˜์™€ ์ข…๋ฅ˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์— ๋”ฐ๋ผ ๋‹ค๋ฆ…๋‹ˆ๋‹ค.

    • Singly Linked List : ํ•˜๋‚˜์˜ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.
    • Doubly Linked List : ์ด์ „ ๋…ธ๋“œ์™€ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋‘ ๊ฐœ์˜ ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.
    • ํŠธ๋ฆฌ(Tree) : ๋ถ€๋ชจ ๋…ธ๋“œ, ์ž์‹ ๋…ธ๋“œ ๋“ฑ ์—ฌ๋Ÿฌ ๋ฐฉํ–ฅ์˜ ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๊ทธ๋ž˜ํ”„(Graph) : ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์ธ์ ‘ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Singly Linked List์˜ Node
Singly Linked List์—์„œ์˜ ๋…ธ๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.

public class Node {
  int data; // ๋…ธ๋“œ๊ฐ€ ์ €์žฅํ•˜๋Š” ๋ฐ์ดํ„ฐ
  Node next; // ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ

  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}

Doubly Linked List์˜ Node
Doubly Linked List์—์„œ์˜ ๋…ธ๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.

public class DoublyNode {
  int data; // ๋…ธ๋“œ๊ฐ€ ์ €์žฅํ•˜๋Š” ๋ฐ์ดํ„ฐ
  DoublyNode next; // ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ
  DoublyNode prev; // ์ด์ „ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ

  public DoublyNode(int data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

2๏ธโƒฃ Node๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ์˜ˆ์ œ.

Singly Linked List

Singly Linked List๋Š” ๊ฐ ๋…ธ๋“œ๊ฐ€ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ตฌ์กฐ๋กœ ์—ฐ๊ฒฐ๋œ ๋ฆฌ์ŠคํŠธ ์ž…๋‹ˆ๋‹ค.

์•„๋ž˜๋Š” Singly Linked List๋ฅผ ๊ตฌํ˜„ํ•œ ์˜ˆ์ œ์ž…๋‹ˆ๋‹ค.

//SinglyLinkedList
public class SinglyLinkedList {
  private Node head;

  public SinglyLinkedList() {
    this.head = null;
  }

  // ๋ฆฌ์ŠคํŠธ์˜ ๋งจ ์•ž์— ๋…ธ๋“œ ์ถ”๊ฐ€
  public void addFirst(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
  }

  // ๋ฆฌ์ŠคํŠธ์˜ ๋งจ ๋์— ๋…ธ๋“œ ์ถ”๊ฐ€
  public void addLast(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = newNode;
  }

  // ๋ฆฌ์ŠคํŠธ์˜ ํŠน์ • ๊ฐ’ ์‚ญ์ œ
  public void delete(int data) {
    if (head == null) {
      return;
    }

    if (head.data == data) {
      head = head.next;
      return;
    }

    Node current = head;

    while (current.next != null && current.next.data != data) {
      current = current.next;
    }

    if (current.next != null) {
      current.next = current.next.next;
    }
  }

  // ๋ฆฌ์ŠคํŠธ ์ถœ๋ ฅ
  public void printList() {
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " ");
      current = current.next;
    }
    System.out.println();
  }
}

// Main
public class Main {

  public static void main(String[] args) {
    // Singly Linked List ์ƒ์„ฑ
    SinglyLinkedList singlyLinkedList = new SinglyLinkedList();

    singlyLinkedList.addFirst(1);
    singlyLinkedList.addLast(2);
    singlyLinkedList.addLast(3);
    singlyLinkedList.printList(); // 1 2 3

    singlyLinkedList.delete(2);
    singlyLinkedList.printList(); // 1 3
  }
}