파이썬[Python] 038 Double Linked list(이중 연결 리스트)

이번 포스팅은 앞서서 Linked List의 진보판인 Double Linked List에 대해서 명시해보고자 합니다. 앞서서 포스팅한 Linked List에는 다음오는 객체를 지칭하는 부분만 있는 반면에 Dobule Linked List에서는 전후에 대한 지칭하는 포인트가 존재합니다. 그래서 한번 간단히 Node를 구성해보는 것은 다음과 같습니다.

Node과 Head 부분에 대해서 구성해보겠습니다.

class Node:
   def __init__(self, value):
      self.val = value
      self.next = None
      self.prev = None

class dlinked_list:
   def __init__(self):
      self.head = None

 

앞부분 추가하기

   def push(self, NewVal):
      NewNode = Node(NewVal)
      NewNode.next = self.head
      if self.head is not None:
         self.head.prev = NewNode
      self.head = NewNode

먼저 간단히 설명을 드리고, Node를 하나 추가하시고, Next를 self.head가 지칭하는 부분으로 바꿉니다. 그런 후 self.head.prev를 방금 만들어 추가한 NewNode로 지칭합니다. 그리고 self.head를 NewNode로 바꾸어 주시면 됩니다. 

 

끝에 추가하기 

   def append(self, NewVal):

      NewNode = Node(NewVal)
      NewNode.next = None
      if self.head is None:
         NewNode.prev = None
         self.head = NewNode
         return
      last = self.head
      while (last.next is not None):
         last = last.next
      last.next = NewNode
      NewNode.prev = last
      return

먼저, 안에 맴버가 없는 경우 self.head is None의 경우 Node가 하나도 없는 경우입니다. 그럴 경우, NewNode.prev = None으로 지정하고, self.head는 NewNode로 지칭하고 return 합니다. 

* return를 하면 함수를 끝내버립니다. 

 

맴버가 있는 경우에 추가하는 방법은 last = self.head로 놓고 last.next가 None이 경우까지 돌고, last.next에 새로 생성한 NewNode를 추가하고, NewNode.prev를 앞서서 last(기존 마지막 맴버)로 지칭해줍니다. 

 

간단하게 전체 코드를 작성해봤습니다. 

class Node:
   def __init__(self, value):
      self.val = value
      self.next = None
      self.prev = None
       
class dlinked_list:
   def __init__(self):
      self.head = None

   def push(self, NewVal):
      NewNode = Node(NewVal)
      NewNode.next = self.head
      if self.head is not None:
         self.head.prev = NewNode
      self.head = NewNode

   def append(self, NewVal):
      NewNode = Node(NewVal)
      NewNode.next = None
      if self.head is None:
         NewNode.prev = None
         self.head = NewNode
         return
      last = self.head
      while (last.next is not None):
         last = last.next
      last.next = NewNode
      NewNode.prev = last
      return

   def printlist(self, node):
      while (node is not None):
         print(node.val),
         node = node.next

dllist = dlinked_list()
dllist.push(100)
dllist.append(1000)
dllist.push(200)
dllist.push(300)
dllist.append(900)
dllist.printlist(dllist.head)

위의 예제를 실행하니 다음과 같은 결과를 얻었습다. 

300
200
100
1000
900

이번 포스팅에서 앞서 포스팅에서 했던 것에 이어 Double linked list를 가지고 포스팅을 해봤습니다. 몇가지는 이글을 보시는 분들께서 직접 작성하실 수 있게 모든 부분에 대해서는 하지 않았습니다. 혹 질문이나 문의 사항 있으시면 언제든지 댓글 및 방명록에 글 부탁드립니다.