파이썬으로 구현하는 자료구조 요약 정리 - 배열(Array), 큐(Queue), Stack, Linked List

Writer: Harim Kang

해당 내용은 코딩 테스트 및 기술 면접을 대비하기 위해서 자료구조를 공부하며 정리한 내용입니다. 각각 자료구조의 종류와 특성, 장단점, 파이썬을 이용한 간단한 구현 코드까지 작성하였습니다.

자료구조

정의

대량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터의 구조를 의미합니다.

데이터 특성에 따라서, 체계적인 데이터 구조화가 필요하며, 이러한 데이터 구조는 코드의 효율성, 성능을 결정합니다.

종류

대표적인 자료구조로는 배열(Array), 스택(Stack), 큐(Queue), 링크드 리스트(Linked List), 해쉬 테이블(Hash Table), 힙(Heap) 등이 존재합니다.

Python에서는 대표적으로 List, tuple, set, dictionary가 존재하며, 위의 자료구조 대부분을 모두 구현이 가능합니다.

---

배열(Array)

배열은 같은 종류의 데이터를 순차적으로 저장하는 자료구조입니다. python에서는 list로 구현이 되어있습니다.

• index를 통해 직접 접근이 가능합니다.

• 장점 : 빠른 접근이 가능하다는 점입니다.

• 단점 : 데이터 추가와 삭제에 비용이 많이 사용된다는 점입니다. 데이터 추가시, 공간이 많이 필요하며, 삭제 시 빈 공간이 생겨 이를 관리해주어야 합니다. 길이 조절이 어렵다는 단점이 있습니다.

# 1차원 배열 = 리스트
data = [1, 2, 3, 4, 5]
string1 = 'Hello World'
print(data[3]) # 4 출력
print(string1[3]) # l 출력

# 2차원 배열
data2 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(data[1][0]) # 4 출력

예제 : 특정 Alphabet의 빈도수 측정 함수

특정 데이터 세트에서 특정한 알파벳이 몇번이나 사용되었는지를 찾아보는 함수를 작성해보겠습니다.

def find_alphabet(dataset, alphabet):
    count = 0
    for data in dataset:
        for i in range(len(data)):
            if data[i] == alphabet:
                count += 1
    print(count)

---

큐(Queue)

먼저 넣은 데이터를 가장 먼저 꺼는 데이터 구조입니다.

FIFO(First-In, First-Out : 선입선출) 또는 LILO(Last-In, Last-Out) 방식을 사용합니다.

기능

• Enqueue : 큐에 데이터를 넣는 기능을 의미합니다. python list의 append() 메서드와 유사합니다.
• Dequeue : 큐에서 데이터를 꺼내는 기능을 의미합니다. python list의 pop(0) 메소드와 유사합니다.

종류

Python에서는 queue라이브러리를 제공합니다. 하지만 대부분의 큐와 관련된 자료구조는 list를 통해 구현이 가능합니다.

import queue

• Queue(): 일반적인 큐 자료구조

    data_queue = queue.Queue()
    data_queue.put(1) # 1
    data_queue.put(2) # 1 - 2
    data_queue.put(3) # 1 - 2 - 3
    data_queue.get() # 1 출력
    data_queue.get() # 2 출력

• LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(Stack과 동일)

    data_queue = queue.LifoQueue()
    data_queue.put(1) # 1
    data_queue.put(2) # 2 - 1
    data_queue.put(3) # 3 - 2 - 1
    data_queue.get() # 3 출력
    data_queue.get() # 2 출력

• PriorityQueue(): 데이터마다 우선순위를 지정하여, 정렬된 큐로, 우선순위 높은 순으로 출력하는 자료 구조

    data_queue = queue.PriorityQueue()
    data_queue.put((10, 1)) # (10,1)
    data_queue.put((5, 2)) # (5, 2) - (10,1)
    data_queue.put((15, 3)) # (5, 2) - (10, 1) - (15,3)
    data_queue.get() # (5,2) 출력
    data_queue.get() # (10, 1) 출력

큐는 멀티 테스킹을 위한 프로세스 스케쥴링 방식에 사용된다.

리스트로 Queue 구현

class ListQueue:
    def __init__(self):
        self.my_list = list()

    def put(self, element):
        self.my_list.append(element)

    def get(self):
        return self.my_list.pop(0)

    def qsize(self):
        return len(self.my_list)

간단하게 Enqueue기능을 가지는 put 메서드, Dequeue기능을 가진 get 메서드, 큐의 길이를 반환하는 qsize 메서드를 구현한 코드입니다.

리스트로 PriorityQueue 구현

class ListPriorityQueue:
    def __init__(self):
        self.my_list = list()

    def put(self, element):
        self.my_list.append(element)
        self.my_list.sort(key=lambda x: x[0])

    def get(self):
        return self.my_list.pop(0)

    def qsize(self):
        return len(self.my_list)

list의 메소드 중 하나인, sort를 이용하여 구현하였습니다. lambda함수를 사용하여 첫 번째 원소가 작은 순서로 우선순위를 정렬하였습니다.

---

스택 (Stack)

가장 나중에 쌓은 데이터를 가정 먼저 뺄 수 있는 데이터 구조입니다. LIFO(Last-In, First-Out)방식을 사용하는 구조입니다.

스택은 내부 프로세스 구조 함수의 동작 방식으로 사용됩니다.

기능

• push(): 데이터를 스택에 쌓는 기능을 의미합니다. python list의 append 메소드와 같습니다.

• pop(): 데이터를 스택에서 꺼내는 기능을 의미합니다. python list에 같은 기능이 있습니다.

  data_stack = list()
  data_stack.append(1) # [1]
  data_stack.append(2) # [1 2]
  data_stack.pop() # 2 출력

장단점

• 장점
  • 구조가 단순하고, 구현이 쉽습니다.
  • 데이터 저장/불러오는 속도가 빠릅니다.
• 단점
  • 데이터 최대 갯수를 사전에 정해주어야 합니다. (python 재귀 함수는 1000번까지 가능)
  • 저장 공간 낭비가 발생할 수 있습니다. (미리 최대 갯수를 넣을 공간을 확보하기 때문)

단점이 상당히 크기때문에 보통 배열로 대체하여 사용합니다.

리스트로 스택 구현하기

class ListStack:
    def __init__(self):
        self.my_list = list()

    def push(self, data):
        self.my_list.append(data)

    def pop(self):
        return self.my_list.pop()

---

Linked List

연결 리스트라고도 불리는 링크드 리스트는 배열과 달리 연결되지 않고, 떨어진 곳에 존재하는 데이터를 경로로 지정하여 관리하는 데이터 구조입니다. 파이썬에서는 리스트 자료구조가 링크드 리스트 기능을 모두 지원합니다.

링크드 리스트 1

기능

• Node: 데이터 저장 단위로, 데이터 값 + 포인터로 구성되어있습니다.
• Pointer: 각 노드 안에서, 다음이나 이전의 노드의 주소를 가지는 값을 의미합니다.

장단점

• 장점
  • 미리 데이터 공간을 미리 할당할 필요가 없습니다.
• 단점
  • 연결을 위한 별도 데이터 공간 (아래 예제에서는 next변수)가 필요하므로 효율이 낮습니다.
  • 데이터를 찾는데 접근성이 안 좋아서 속도가 느립니다.
  • 중간 데이터 삭제시, 앞 뒤를 모두 고려하여 재구성하는 코드를 작성해야 합니다.

파이썬으로 Node의 구현

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

노드는 data를 저장하는 변수와 다음 노드를 가리키는 포인터가 있습니다. 해당 코드에서는 next라는 변수로 두었습니다.

파이썬으로 Linked List의 구현

해당 링크드 리스트에서는 간단한 코드 구현만을 하여, 중간 데이터 삽입 코드는 작성하지 않았습니다.

링크드 리스트 2

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, data):
                new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = new_node

    def delete(self, data):
        node = self.head
        if node.data == data:
            self.head = node.next
            del node
        else:
            while node.next:
                next_node = node.next
                if next_node.data == data:
                    node.next = next_node.next
                    del next_node
                else:
                    node = node.next

    def find(self, data):
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

    def print(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

링크드 리스트에서는 head인 첫 번째 노드 정보만 알면 됩니다. 그리고 데이터들을 받아서 Node를 만들어서 리스트에 추가시켜줄 add함수, node의 data값을 통해 리스트에서 제거하는 delete함수, data값으로 Node를 찾아주는 find함수, 현재 링크드 리스트의 모든 노드의 데이터 값을 출력하는 print함수를 간단하게 구현하였습니다.

사용법

ll = LinkedList() # 링크드 리스트 ll선언
ll.add(1) # 노드 1 리스트에 추가
ll.add(2) # 노드 2 리스트에 추가
ll.add(3) # 노드 3 리스트에 추가
ll.print() # 1 2 3 출력

ll.delete(2) # 노드 2 삭제
ll.print() # 1 3 출력

ll.delete(1) # 노드 1 삭제
ll.print() # 3 출력
ll.delete(3) # 노드 3 삭제
print(ll.head) # None 출력

Doubly Linked List

링크드 리스트 3

이중 연결 리스트라고도 하는 더블 링크드 리스트는 양방향의 노드 주소 값을 모두 가지고 있어서 양 방향으로 탐색이 가능하다는 장점을 가진 링크드 리스트입니다.

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

기존의 링크드 리스트에서 prev라는 이전의 노드를 가리키는 변수를 추가하면 됩니다.

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = self.head

    def add(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new_node.prev = node
            node.next = new_node
            self.tail = new_node

이전의 링크드 리스트 클래스에서 init에 tail변수가 추가된 점과 add시, tail변수를 고려해주는 점이 다른 코드입니다. 나머지는 같습니다.

다음 포스팅에서는 해쉬 테이블, 트리, 힙에 관한 내용으로 정리하겠습니다.

Reference

링크드 리스트 1 : wikipedia, https://en.wikipedia.org/wiki/Linked_list

링크드 리스트 2 : wikipedia, https://en.wikipedia.org/wiki/Linked_list

링크드 리스트 3 : wikipedia, https://en.wikipedia.org/wiki/Linked_list