Python-고급 연결 목록

우리는 이전 장에서 앞으로 만 이동할 수있는 연결 목록을 이미 보았습니다. 이 장에서는 앞뒤로 이동할 수있는 또 다른 유형의 연결 목록을 볼 수 있습니다. 이러한 연결 목록을 이중 연결 목록이라고합니다. 다음은 이중 연결 목록의 기능입니다.

이중 연결 목록에는 첫 번째와 마지막이라는 링크 요소가 있습니다.
각 링크에는 데이터 필드와 next 및 prev라는 두 개의 링크 필드가 있습니다.
각 링크는 다음 링크를 사용하여 다음 링크와 연결됩니다.
각 링크는 이전 링크를 사용하여 이전 링크와 연결됩니다.
마지막 링크는 목록의 끝을 표시하기 위해 링크를 null로 전달합니다.

이중 연결 목록 생성

Node 클래스를 사용하여 이중 연결 목록을 만듭니다. 이제 우리는 Singly Linked List에서 사용 된 것과 동일한 접근 방식을 사용하지만 노드에있는 데이터 외에 각 노드에 두 개의 링크를 생성하기 위해 적절한 할당을 위해 head 및 next 포인터가 사용됩니다.

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

class doubly_linked_list:

   def __init__(self):
      self.head = None

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

# Print the Doubly Linked list		
   def listprint(self, node):
      while (node is not None):
         print(node.data),
         last = node
         node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.listprint(dllist.head)

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

62 8 12

이중 연결 목록에 삽입

여기서는 다음 프로그램을 사용하여 이중 링크 목록에 노드를 삽입하는 방법을 살펴 보겠습니다. 이 프로그램은 이중 연결 목록의 헤드에서 세 번째 위치에 새 노드를 삽입하는 insert라는 이름의 menthod를 사용합니다.

# Create the Node class
class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None

# Create the doubly linked list
class doubly_linked_list:

   def __init__(self):
      self.head = None

# Define the push method to add elements		
   def push(self, NewVal):

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

# Define the insert method to insert the element		
   def insert(self, prev_node, NewVal):
      if prev_node is None:
         return
      NewNode = Node(NewVal)
      NewNode.next = prev_node.next
      prev_node.next = NewNode
      NewNode.prev = prev_node
      if NewNode.next is not None:
         NewNode.next.prev = NewNode

# Define the method to print the linked list 
   def listprint(self, node):
      while (node is not None):
         print(node.data),
         last = node
         node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

62  8  13  12

이중 연결 목록에 추가

이중 연결 목록에 추가하면 끝에 요소가 추가됩니다.

# Create the node class
class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None
# Create the doubly linked list class
class doubly_linked_list:

   def __init__(self):
      self.head = None

# Define the push method to add elements at the begining
   def push(self, NewVal):
      NewNode = Node(NewVal)
      NewNode.next = self.head
      if self.head is not None:
         self.head.prev = NewNode
      self.head = NewNode

# Define the append method to add elements at the end
   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

# Define the method to print
   def listprint(self, node):
      while (node is not None):
         print(node.data),
         last = node
         node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

62 8 12 9 45

추가 작업을 위해 요소 9 및 45의 위치를 확인하십시오.