[TIL] 96. 추상 자료형(Abstract Data Type ; ADT)

키워드

• ADT(추상자료형)
• 연결리스트
• 스택/큐

추상자료형(ADT)

• 파이썬에는 기본 자료형인 숫자, 문자열, 리스트, 딕셔너리 등이 존재
• ADT는 기본 자료형처럼 로직이 구성되어있는 자료가 아닌 필요한 기능만 사용자가 직접 구현한 로직
• 추상화 : 소프트웨어가 발전함에 따라 프로그램의 크기나 복잡도가 증가하였고 이런 부분을 간단하게 핵심만 설명하는 것

연결리스트(Linked-list)

• 연결리스트는 각 노드가 1. 본인의 값, 2. 다음 노드에 대한 정보 를 담고 있다.
• 데이터를 읽을 때는 헤드 노드부터 순차적으로 거쳐야하기 때문에 배열보다 시간복잡도가 크지만
  데이터를 추가/제거할 때, 노드 사이의 링크만 바꿔주면 되기 때문에 더 빠르다.(연결리스트의 장점)
• 단방향, 양방향, 환형 연결리스트가 존재

• 배열과 달리 참조의 기능으로 구현되고 그에 따라 리스트의 길이를 별도로 지정해줄 필요가 없음

예시(단방향 연결리스트)

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)


    def del_node(self,value):       
        if self.head == None:
            return None
        elif self.head.value == value:
            node = self.head
            self.head = self.head.next
            return node.value
        else:
            node = self.head
            while node.next:
                if node.next.value == value:
                    temp = node.next
                    node.next = node.next.next
                    return temp.value
                else:
                    node = node.next


    def ord_desc(self):        
        node = self.head
        arr = []
        while node:
            arr.append(node.value)
            node = node.next
        return arr


    def search_node(self,value):        
        node = self.head
        while node:
            if node.value == value:
                return node
            else:
                node = node.next

스택(stack)

• 컵 안에 과자를 담는 것과 같은 구조
• 즉, LIFO(Last In, First Out) ; 후입선출로 나중에 들어간 자료가 먼저 나가게 된다.

• 파이썬의 함수 또한 스택과 같은 구조로 호출된다.(함수의 콜스택)
• 파이썬 리스트의 내장 함수 append 와 pop 이 스택 구조를 이루고 있다.

큐(queue)

• 영화 매표소 줄을 선 것과 같은 구조
• 즉 FIFO(First In, First Out) ; 선입선출로 먼저 들어간 자료가 먼저 나가게 된다.

• 파이썬 리스트로 표현하자면 append와 pop(0)을 사용하면 된다. pop(0)이 가장 첫번째 인덱스 값을 꺼내는 것이기 때문