반응형

Linked List, 참으로 필요한 것이죠.

그러나 lua 코딩을 하다보면 별 필요는 없습니다.

그 이유는 루아를 사용하여 그렇게 큰 데이터 리스트를 만들 이유가 많지 않고 또한 table 자체를 사용하면

제한 없이 정보를 보관할 수 있기 때문입니다.

 

하지만, 이론은 알고 넣어가야죠..

 

루아에서 Linked List 의 구현은 매우 쉽습니다. 그 이유는 루아의 table 이 dynamic entity (동적 요소??) 를 다루고 있기 때문이죠. 배열과 같이 정적인 메모리를 잡아서 사용하는 것이 아니라는 것이죠.

 

흔히 linked list 는 next 와 value 가 있습니다. next 는 해당 요소의 뒤에 따라오는 요소이고 value는 해당 요소에 저장하는 값이 되겠죠.

 

일단 list 는 root 가 있어야 합니다.

 

list = nil

 

이제 리스트의 가장 앞에 값 v 를 추가하는 것을 생각해 봅시다.

 

list = {next=list, value = v}

 

위와 같이 하면 list.next 가 있을 것이고, list.value 가 있을 것입니다.

list.next 는 추가되기 전의 가장 마지막의 위치가 되겠죠.

 

이렇게 계속 넣다보면 리스트의 구조를 가지게 됩니다. 마지막에 들어간 것이 물론 root 가 되어지는 것이니,

reverse list 라고나 할까요?

 

이제 이러한 list 를 순회해 봅시다. 여기서 순회란 리스트의 모든 요소를 한번 훓어서 본다 라고 생각하시면 됩니다.

iterator 에 대해서 살펴본적이 있습니다. 그와 유사한 개념 입니다.

 

    local l = list
    while l do
      print(l.value)
      l = l.next
    end

 

이들을 합쳐서 다음과 같이 테스트 해 봅니다.

 

list = nil

list = {next=list, value=10}
list = {next=list, value=20}

 

local l = list
   while l do
      print(l.value)
      l = l.next
   end

 

 

결과

20
10

앞서 말했듯이 뒤에 추가된것이 먼저 나오게 되었습니다. reverse 된 리스트라 생각하시면 됩니다.

이러한 응용에 의하여 순방향 리스트도 쉽게 구현이 가능합니다.

+ Recent posts