루비 링크드 리스트 이해하기

링크드 리스트(Linked List)는 데이터 구조 중 하나로, 데이터를 노드(Node)라는 단위로 저장하고 각 노드가 다음 노드를 가리키는 방식으로 구성됩니다. 이 구조는 배열과는 다르게 동적으로 크기를 조절할 수 있어 유용합니다. 이번 글에서는 루비(Ruby)에서 링크드 리스트를 구현하고 사용하는 방법에 대해 알아보겠습니다.

링크드 리스트란?

링크드 리스트는 다음과 같은 특징을 가지고 있습니다:

각 노드는 데이터와 다음 노드에 대한 참조를 포함합니다.
노드의 수가 동적으로 변할 수 있습니다.
배열과 달리 메모리의 연속성을 요구하지 않습니다.

링크드 리스트는 크게 단일 링크드 리스트(Singly Linked List)와 이중 링크드 리스트(Doubly Linked List)로 나눌 수 있습니다. 단일 링크드 리스트는 각 노드가 다음 노드만을 가리키고, 이중 링크드 리스트는 이전 노드와 다음 노드 모두를 가리킵니다.

루비에서 링크드 리스트 구현하기

이제 루비를 사용하여 단일 링크드 리스트를 구현해보겠습니다. 먼저 노드 클래스를 정의하고, 링크드 리스트 클래스를 만들어 보겠습니다.

노드 클래스 정의하기

노드 클래스는 데이터와 다음 노드에 대한 참조를 포함해야 합니다. 아래는 노드 클래스를 정의하는 코드입니다:

class Node
  attr_accessor :data, :next_node

  def initialize(data)
    @data = data
    @next_node = nil
  end
end

위 코드에서 attr_accessor를 사용하여 data와 next_node 속성에 대한 getter와 setter를 생성했습니다. initialize 메서드는 노드가 생성될 때 데이터를 초기화하고, next_node는 기본적으로 nil로 설정합니다.

링크드 리스트 클래스 정의하기

이제 링크드 리스트 클래스를 정의해보겠습니다. 이 클래스는 노드를 추가하고, 삭제하고, 출력하는 메서드를 포함할 것입니다.

class LinkedList
  def initialize
    @head = nil
  end

  def append(data)
    new_node = Node.new(data)
    if @head.nil?
      @head = new_node
    else
      current = @head
      current = current.next_node while current.next_node
      current.next_node = new_node
    end
  end

  def display
    current = @head
    while current
      print "#{current.data} -> "
      current = current.next_node
    end
    puts "nil"
  end

  def delete(data)
    return if @head.nil?

    if @head.data == data
      @head = @head.next_node
      return
    end

    current = @head
    while current.next_node && current.next_node.data != data
      current = current.next_node
    end

    if current.next_node
      current.next_node = current.next_node.next_node
    end
  end
end

위 코드에서 LinkedList 클래스는 다음과 같은 메서드를 포함합니다:

initialize: 링크드 리스트의 헤드를 초기화합니다.
append(data): 리스트의 끝에 새로운 노드를 추가합니다.
display: 리스트의 모든 노드를 출력합니다.
delete(data): 특정 데이터를 가진 노드를 삭제합니다.

링크드 리스트 사용하기

이제 링크드 리스트를 사용하여 데이터를 추가하고 삭제하는 방법을 알아보겠습니다. 아래는 링크드 리스트를 사용하는 예제입니다:

list = LinkedList.new
list.append(1)
list.append(2)
list.append(3)

puts "리스트 출력:"
list.display

list.delete(2)
puts "2를 삭제한 후 리스트 출력:"
list.display

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:

리스트 출력:
1 -> 2 -> 3 -> nil
2를 삭제한 후 리스트 출력:
1 -> 3 -> nil

링크드 리스트의 장점과 단점

링크드 리스트는 여러 가지 장점과 단점을 가지고 있습니다. 이를 정리해보면 다음과 같습니다:

장점

동적 크기 조절: 링크드 리스트는 필요에 따라 크기를 조절할 수 있어 메모리 효율성이 높습니다.
삽입 및 삭제 용이: 노드를 삽입하거나 삭제하는 것이 배열보다 간단합니다.

단점

메모리 사용: 각 노드가 추가적인 포인터를 저장해야 하므로 메모리 사용량이 증가합니다.
접근 속도: 배열에 비해 특정 인덱스에 접근하는 속도가 느립니다.

결론

이번 글에서는 루비에서 링크드 리스트를 구현하고 사용하는 방법에 대해 알아보았습니다. 링크드 리스트는 동적 데이터 구조로서 유용하게 사용될 수 있으며, 다양한 알고리즘과 데이터 구조의 기초가 됩니다. 링크드 리스트의 장점과 단점을 이해하고, 필요에 따라 적절히 활용하는 것이 중요합니다. 앞으로도 다양한 데이터 구조를 학습하여 프로그래밍 능력을 향상시키길 바랍니다!