[자료구조와 알고리즘] DataStructure Fundamenta

추상자료형 ( Abstract Data Type, ADT ) 이란?

연결리스트 ( Linked - List ) 이란?

- 연결리스트는 말 그대로 리스트들을 "연결" 해줌

- 연결은 프로그래밍에서 참조의 기능으로 구현되고, 리스트의 길이를 별도로 지정해줄 필요없음

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


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:
            temp = self.head
            self.head = self.head.next
            return temp.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
        answer = []
        while node:
            answer.append(node.value)
            node = node.next
        return answer

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

큐 ( Queue ) 란?

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

- ex) 놀이기구 줄서기, 식료품점 계산대 등

▶ Deque ( Double - Ended - Queue )

- 큐에서 양방향으로 데이터를 처리한다는 의미

▶ 큐의 Time and Space Complexity ( 시간, 공간 복잡도 )

- Enqueue ( 대기열에 넣기 ) : Q( 1 )

- Dequeue ( 대기열에서 빼기 ) : Q ( 1 )

class Queue():
    def __init__(self):
        self.queue = []

    def enqueue(self,item):
        self.queue.append(item)

    def dequeue(self):
        if len(self.queue) == 0:
            return None
        else:
            return self.queue.pop(0)

    def return_queue(self):
    
        return self.queue

스택 ( Stack ) 이란?

- ex ) 윈도우 프로그램 등

class Stack():
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if len(self.stack) == 0:
            return None
        else:
            return self.stack.pop()

    def return_stack(self):

        return self.stack