ADT(추상자료형)와 자료구조 (1) (연결리스트,큐)

핵심 : ADT(Abstract Data Type)와 연결리스트, 큐, 스택

 

앞 장에서는 파이썬의 기본자료형(숫자, 문자열, 리스트, 딕셔너리 등)에 대해 배움

ADT는 추상적으로 필요한 기능을 나열한 일종의 명세서(로직)

ADT는 기본자료형(대표적으로 리스트, 숫자, 문자열)을 활용하여 사용자에 의해 구현

(즉 프로그래머의 설계에 따라 자유롭게 구성됨)

 

---

linked-list(연결리스트)

 

 

연결은 프로그래밍에서 참조의 기능으로 구현됨

연결리스트는 리스트의 길이를 별도로 지정해줄 필요없다.

연결리스트는 별도의 인덱스를 지정할 필요없이 연결되는 구조

연결리스트의 각 요소는 참조하는 노드에 저장

 

 

# 연결리스트의 노드를 저장하는 첫 단계

class Node:
  def __init__(self,value,next=None):
    self.value = value  # 노드의 값을 나타내는 value
    self.next = next  # 노드의 다음위치를 가리키는 next의 초기값은 None

class linked_list:
  def __init__(self,value):
    self.head = Node(value) # 초기 클래스에 head노드선언

  def add_node(value):
    node = head           # 첫번째 위치에 해당하는 head를 생성하고, node 변수에 저장해둔다.
    while head.next:      # head노드의 다음위치에 노드가 생성될 때까지 반복문 진행한다.
      node = head.next    # head노드의 다음위치에 노드가 있는 경우(두번째 노드라고 가정),
      print(head.next)
                          # 두번째 노드부터 node변수에 저장
    node.next = Node(value)# 데이터를 노드 다음위치에 저장

# 리스트를 연결해보자.

node1 = Node(3)
node2 = Node(4)

node3 = Node(5)
node4 = Node(6)

node1.next = node2
node2.next = node3
node3.next = node4

node = node1        # 첫번째노드부터 시작한다.
while node:         # 노드별로 반복문을 수행
  print(node.value) 
  node = node.next  # 다음노드를 현재노드에 저장하면서 위치를 바꾼다.

출력값
3
4
5
6

# 새로운 노드를 중간에 넣는 경우
node2 -> node3
node2 -> node5 -> node3

node5 = Node(7)   # 5번노드에 값 저장

node2.next = node5

node5.next = node3 

node = node1
while node:
  print(node.value)
  print(node.)
  node = node.next

출력값
3
4
7
5
6

 

연결리스트도 리스트의 메소드와 같은 기능들 구현 가능
삽입 , 삭제 , 검색

 

# 클래스에 연결리스트 구현
class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

class linked_list:
  def __init__(self, value):
    self.head = Node(value)

  def add_node(self, value):
    if self.head == None:
      self.head = Node(value)

    else:
      node = self.head
      while node.next:
        node = node.next
      node.next = Node(value) # init함수의 value

  # 연결리스트의 삭제구현
  def del_node(self,value):
    if self.head == None:
      print("해당 값에 대한 노드는 없다.")
      return  # 의미없는 조건에서 함수는 아무것도 반환하지 않는다. 
    elif self.head.value == value:
      temp_node = self.head
      self.head = self.head.next
      del temp_node
    else:
      node = self.head
      while node.next:
        if node.next.value == value:
          temp_node = node.next
          node.next = node.next.next
          del temp_node
        else : 
          node = node.next

  # 연결리스트의 노드출력을 위한 기능
  def ord_desc(self):
    node = self.head
    while node:
      print(node.value)
      node = node.next 

 

# 연결리스트에서 검색구현
class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

class linked_list:
  def __init__(self, value):
    self.head = Node(value)

  def add_node(self, value):
    if self.head == None:
      self.head = Node(value)

    else:
      node = self.head
      while node.next:
        node = node.next
      node.next = Node(value) # init함수의 value

  # 연결리스트의 삭제구현
  def del_node(self,value):
    if self.head == None:
      print("해당 값에 대한 노드는 없다.")
      return  # 의미없는 조건에서 함수는 아무것도 반환하지 않는다. 
    elif self.head.value == value:
      temp_node = self.head
      self.head = self.head.next
      del temp_node
    else:
      node = self.head
      while node.next:
        if node.next.value == value:
          temp_node = node.next
          node.next = node.next.next
          del temp_node
        else : 
          node = node.next

  # 연결리스트의 노드출력을 위한 기능
  def ord_desc(self):
    node = self.head
    while node:
      print(node.value)
      node = node.next 
          
  # 연결리스트 검색함수
  def search_node(self,value):
    node = self.head
    while node:
      if node.value == value:
        return node
      else:
        node = node.next

 

---

Queue(큐)

 

큐는 항목을 FIFO(선입 선출) 순서로 저장하는 자료구조

deque : 양방향으로 데이터를 처리한다는 의미

 

# 리스트 메소드를 사용해서 큐를 만들어보기

from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           
queue.append("Graham")          
print('queue.popleft() ',queue.popleft())

print('queue.popleft() ',queue.popleft())

print('queue ', queue)

출력값
queue.popleft()  Eric
queue.popleft()  John
queue  deque(['Michael', 'Terry', 'Graham'])

 

Queue 클래스의 경우 , init 먼저 정의

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

 

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
    def enqueue(self, item):
        new_node = LinkedListNode(item)
        # 큐가 비어있는지 체크
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            # 새로운 노드를 rear 다음에 삽입
            self.rear.next = new_node
            # 새로운 노드를 rear 재할당
            self.rear = new_node
    def dequeue(self):
        # 큐가 비어있는지 체크
        if self.front is not None:
            # front값을 old front에 삽입
            old_front = self.front
            # old front 다음 값을 front값에 삽입
            self.front = old_front.next

        # 큐가 비어있는지 체크
        if self.front is None:
            # rear를 None으로 지정한다.
            self.rear = None

        return old_front