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의 위치를 ​​확인하십시오.