Ruby의 실용적인 연결 리스트

"Ruby의 컴퓨터 공학 실용" 시리즈의 세 번째 항목입니다! 오늘은 연결 리스트에 대해 알아보겠습니다.

그렇다면 연결 목록이란 무엇입니까?

이름에서 알 수 있듯이 연결 목록은 데이터를 목록 형식으로 저장하는 방법입니다(감사합니다, Captain Obvious!).

"연결된" 부분은 데이터가 노드에 저장되고 이러한 노드가 서로 순차적으로 연결된다는 사실에서 비롯됩니다.

배열과 어떻게 다릅니까?

연결된 목록과 배열

연결 목록은 배열과 성능 특성이 다릅니다. 이것이 다른 것보다 하나를 선택하려는 이유 중 하나입니다.

이것은 연결 목록이 배열보다 특정 작업에 더 효율적일 수 있음을 의미합니다.

연결 목록에는 인덱싱이나 임의 액세스가 없습니다. 즉, 목록 중간에 있는 항목에 접근할 수 없습니다. .

목록의 "머리"에서 시작하여 원하는 노드를 찾거나 목록이 끝날 때까지 링크를 따라가야 합니다.

연결 목록 중간에서 항목을 제거(또는 추가)하는 것이 훨씬 빠릅니다. .

한 노드의 "다음" 포인터를 변경하기만 하면 됩니다.

그러나 배열의 중간에서 요소를 삭제하려면 공백을 남겨두고 해당 공백을 닫으려면 삭제된 요소의 오른쪽에 있는 모든 요소를 ​​이동해야 합니다.

이 작업을 자주 수행해야 하는 경우 매우 효율적이지 않습니다!

배열 중간에 삽입하려면 모든 배열 요소를 이동하여 빈 공간을 만들어야 합니다.

코드 예를 살펴보겠습니다. :

a = [1,2,3,4,5,6,7,8]

def insert(arr, item, pos)
  tmp      = arr[pos]
  arr[pos] = item

  arr.replace(arr[0..pos] + [tmp] + arr[pos+1..-1])
end

insert(a, 99, 3)
p a

참고 :내장된 Array#insert 메소드도 있지만 이 메소드가 어떻게 작동하는지 보여드리고 싶었습니다.

목록 중간에 항목을 삽입하면 성능에 어떤 영향을 미치나요?

다음은 벤치마크입니다.

Comparison:
   LinkedList:  1815407.9 i/s
   Array:       18090.3 i/s - 100.35x  slower

여기서 큰 차이가 있지만 LinkedList의 크기에 따라 많이 달라집니다. 노드를 검색해야 하기 때문입니다.

두 데이터 구조를 비교하는 또 다른 방법은 시간 복잡도 테이블을 보는 것입니다(이는 삽입 및 삭제를 위해 노드를 검색할 필요가 없다고 가정함):

실제 애플리케이션을 찾고 계십니까?

다음은 연결 목록을 사용하여 Ruby Gems의 속도를 높이는 Aaron Patterson의 풀 리퀘스트입니다.

https://github.com/rubygems/rubygems/pull/1188

연결 목록 구현

Ruby에는 LinkedList가 포함되어 있지 않습니다. 클래스를 생성해야 합니다.

다음 작업을 사용할 수 있기를 바랍니다.

• 추가(목록 끝에)
• append_after
• 삭제
• 찾기

가능한 구현은 다음과 같습니다.

class LinkedList
  def initialize
    @head = nil
  end

  def append(value)
    if @head
      find_tail.next = Node.new(value)
    else
      @head = Node.new(value)
    end
  end

  def find_tail
    node = @head

    return node if !node.next
    return node if !node.next while (node = node.next)
  end

  def append_after(target, value)
    node           = find(target)

    return unless node

    old_next       = node.next
    node.next      = Node.new(value)
    node.next.next = old_next
  end

  def find(value)
    node = @head

    return false if !node.next
    return node  if node.value == value

    while (node = node.next)
      return node if node.value == value
    end
  end

  def delete(value)
    if @head.value == value
      @head = @head.next
      return
    end

    node      = find_before(value)
    node.next = node.next.next
  end

  def find_before(value)
    node = @head

    return false if !node.next
    return node  if node.next.value == value

    while (node = node.next)
      return node if node.next && node.next.value == value
    end
  end

  def print
    node = @head
    puts node

    while (node = node.next)
      puts node
    end
  end
end

이 특정 구현은 꼬리를 추적하지 않고 새 항목을 추가할 때 꼬리를 찾습니다. 이것은 추가 작업을 선형 시간으로 만듭니다(O(n) ). 아래 비디오에서는 요소를 앞에 추가하는 또 다른 구현을 보여줍니다.

다음은 노드 클래스입니다.

class Node
  attr_accessor :next
  attr_reader   :value

  def initialize(value)
    @value = value
    @next  = nil
  end

  def to_s
    "Node with value: #{@value}"
  end
end

다음과 같이 사용할 수 있습니다.

list = LinkedList.new

list.append(10)
list.append(20)
list.append(30)

list.append_after(10, 15)
list.append_after(20, 25)

list.print

이것은 기본적인 "Singly-Linked List" 구현입니다.

다른 유형의 연결 목록도 있습니다. :

• 이중 연결 목록
• 순환 연결 목록

이중 연결 목록에서 모든 노드에는 두 개의 포인터가 있습니다. 하나는 다음 노드에 대한 것입니다. &다른 이전 노드에 .

이렇게 하면 목록을 검색할 때 더 많은 유연성을 얻을 수 있지만 목록을 변경할 때 추가 작업이 필요합니다.

순환 연결 목록은 이중 연결 목록과 같지만 마지막 노드가 헤드 노드에 연결됩니다.

동영상

요약

배열 중간에 요소 추가 및 제거를 많이 수행하는 경우 고려할 수 있는 데이터 구조인 연결 목록에 대해 배웠습니다.

코딩 면접에서도 나올 수 있으니 그것만으로도 충분히 배울 가치가 있습니다.

이 게시물을 공유하는 것을 잊지 마세요. 더 많은 사람들이 이 지식의 혜택을 받을 수 있도록 아래 버튼을 사용하세요 🙂