연결 리스트에서 노드(Node)란?

연결 리스트에서 노드(Node)는 리스트의 기본 단위로, 데이터와 다음 노드에 대한 참조(포인터)를 포함하는 객체나 구조체입니다. 연결 리스트는 이러한 노드들이 서로 연결되어 있는 구조로, 각 노드는 다음 노드를 가리키는 방식으로 연결됩니다. 연결 리스트의 각 요소를 노드라고 부르며, 각 노드는 최소 두 부분으로 구성됩니다:

1. 데이터(Data): 노드가 저장하고 있는 실제 값이나 정보입니다. 이 데이터는 정수, 문자열, 또는 복잡한 객체와 같은 어떤 타입도 될 수 있습니다.
2. 참조(Next Pointer): 다음 노드를 가리키는 포인터나 참조입니다. 이를 통해 연결 리스트의 다음 요소와 연결됩니다. 마지막 노드의 경우, 이 포인터는 일반적으로 null이나 리스트의 끝을 나타내는 특별한 값을 가집니다.

연결 리스트는 이러한 노드들이 서로 연결된 형태로 데이터를 저장하며, 배열과 달리 노드들이 연속적인 메모리 위치에 저장될 필요가 없습니다. 이 특성 때문에 연결 리스트는 동적인 크기 조정이 가능하고, 요소의 삽입과 삭제가 용이하지만, 임의 접근(random access)의 성능은 배열보다 떨어집니다.

연결 리스트는 크게 세 가지 기본 유형으로 나뉩니다:

1. 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만을 가리키는 가장 간단한 형태의 연결 리스트입니다.
2. 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드 양쪽을 가리키는 포인터를 가지고 있어, 양방향으로 순회할 수 있는 형태입니다.
3. 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 형태로, 연결 리스트가 원형으로 연결되어 있습니다. 단일 연결 리스트나 이중 연결 리스트 모두 원형 형태를 가질 수 있습니다.

연결 리스트는 데이터의 동적 관리에 유용하며, 스택, 큐, 그래프와 같은 다른 추상 자료형의 구현에도 사용됩니다.

 

 

JavaScript에서 단일 연결 리스트와 노드를 구현하는 예시는 다음과 같습니다. 이 예제에서는 간단한 연결 리스트를 만들고, 노드를 추가하며, 리스트를 순회하여 모든 노드의 데이터를 출력합니다.

노드 클래스 정의

먼저, 연결 리스트의 각 요소인 노드를 정의하는 Node 클래스를 만듭니다. 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)를 멤버로 가집니다.

class Node {
  constructor(data) {
    this.data = data; // 노드에 저장될 데이터
    this.next = null; // 다음 노드를 가리키는 포인터, 초기값은 null
  }
}

연결 리스트 클래스 정의

이제 연결 리스트를 관리할 LinkedList 클래스를 정의합니다. 이 클래스는 리스트의 첫 번째 노드를 가리키는 head 포인터를 가지며, 노드를 추가하고 리스트를 출력하는 메소드를 포함합니다.

class LinkedList {
  constructor() {
    this.head = null; // 리스트의 첫 번째 노드를 가리키는 포인터
  }

  // 연결 리스트의 끝에 새 노드 추가
  append(data) {
    const newNode = new Node(data);
    if (this.head === null) {
      this.head = newNode; // 리스트가 비어있으면 새 노드를 head로 설정
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next; // 마지막 노드를 찾기 위해 리스트를 순회
      }
      current.next = newNode; // 마지막 노드의 next로 새 노드를 설정
    }
  }

  // 연결 리스트의 모든 노드를 순회하며 데이터 출력
  printList() {
    let current = this.head;
    while (current !== null) {
      console.log(current.data);
      current = current.next; // 다음 노드로 이동
    }
  }
}

연결 리스트 사용 예

아래의 코드는 LinkedList 클래스를 사용하여 노드를 추가하고, 연결 리스트의 내용을 출력하는 예제입니다.

const list = new LinkedList();

// 노드 추가
list.append(1);
list.append(2);
list.append(3);

// 연결 리스트 출력
list.printList(); // 출력: 1 2 3

이 예제에서는 먼저 **LinkedList**의 인스턴스를 생성하고, append 메소드를 사용하여 세 개의 노드(데이터가 각각 1, 2, **3**인)를 리스트의 끝에 추가합니다. 마지막으로 printList 메소드를 호출하여 연결 리스트에 저장된 모든 데이터를 순서대로 출력합니다.

JavaScript에서 연결 리스트를 구현하는 방법은 다양한 데이터 구조와 알고리즘 문제를 해결하는 데 유용한 기초를 제공합니다.