파이썬 자료구조 (1)

자료구조란?

자료구조(Data Structure)는 데이터를 효율적으로 저장하고 처리하기 위한 구조입니다. 우리가 다루는 프로그램은 대부분 데이터를 처리합니다. 따라서 어떤 방식으로 데이터를 저장하고 접근할 것인가가 프로그램 성능을 결정짓습니다.

▶ 자료구조는 알고리즘과 함게 문제 해결의 핵심도구

자료구조의 필요성

• 대량의 데이터를 효율적으로 처리하기 위해
• 상황에 맞는 최적의 방법으로 데이터를 저장하기 위해
• 시간과 공간 자원을 절약하기 위해

대표적인 자료구조

배열	인덱스를 통한 빠른 접근	리스트, 튜플
스택	후입선출 (LIFO)	웹브라우저 뒤로가기, 괄호검사
큐	선입선출 (FIFO)	작업 스케줄링, BFS 탐색
연결 리스트	유연한 삽입/삭제	Undo/Redo 기능

 

배열(Array)

 

개념

• 연속된 메모리 공간에 동일한 타입의 데이터를 순차적으로 저장합니다.
• Python에선 list, tuple로 구현

장단점

• ✅ 빠른 인덱스 접근( 0(1) )
• ❌ 삽입/삭제가 느림( 0(n) )

# 1차원 배열
arr = [10, 20, 30, 40]
print(arr[2])  # 30

# 2차원 배열
matrix = [[1,2,3], [4,5,6]]
print(matrix[1][0])  # 4

 

 

큐(Queue)

 

개념

• 선입선출(FIFO)
• 먼저 들어온 데이터가 먼저 나감

주요 연산

• enqueue() : 데이터 삽입
• dequeue() : 데이터 제거

from queue import Queue

q = Queue()
q.put(1)
q.put(2)
print(q.get())  # 1

 

리스트로 구현한 큐

class ListQueue:
    def __init__(self):
        self.data = []

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

    def dequeue(self):
        return self.data.pop(0)

 

스택(Stack)

 

개념

• 후입선출(LIFO)
• 최근에 넣은 데이터가 가장 먼저 나옴

주요 연산

• push() : 데이터가 추가
• pop() : 마지막 데이터 제거

stack = []
stack.append('a')
stack.append('b')
print(stack.pop())  # 'b'

사용 예

• 웹 브라우저의 뒤로가기
• 함수 호출 기록

리스트로 스택 구현

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)

 

링크드 리스트(Linked List)는 배열과 다르게 메모리상에서 연속적으로 배치되지 않는 데이터 구조입니다. 각 데이터 요소(노드)가 다음 요소의 위치 정보를 포함하고 있어, 포인터를 통해 순차적으로 연결되어 있습니다.

파이썬의 내장 리스트는 내부적으로 동적 배열로 구현되어 있지만, 링크드 리스트와 유사한 동작을 수행할 수 있는 다양한 메서드를 제공합니다.

링크드 리스트 1

개념

• 노드들이 포인터를 통해 연결된 구조
• 배열과 달리 연속된 메모리 공간이 필요 없음

단일 연결 리스트(Singly Linked List)

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

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

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

 

링크드 리스트 2

 

사용법

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 출력
출처: https://davinci-ai.tistory.com/16 [DAVINCI - AI:티스토리]

 

이중 연결 리스트(Doubly Linked List)

링크드 리스트3

 

개념

이중 연결 리스트는 각 노드가 다음 노드 뿐만 아니라 이전 노드도 함께 가리키는 구조입니다. 즉, 양쪽 방향으로 연결이 되어 있어 순방향과 역방향 탐색이 모두 가능합니다. 삽입과 삭제가 더 유연하며, 리스트의 양끝을 기준으로 접근이 빠릅니다.

 

장점

• 양방향 순회가 가능하여 탐색이 더 유연함
• 양쪽 끝에서 삽입/삭제 시 성능 우수

단점

• 단일 연결 리스트에 비해 메모리 사용량 증가(prev 포인터 필요)
• 구현이 복잡함

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

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

    def append(self, data):
        new_node = DoubleNode(data)
        if not self.head:
            self.head = new_node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = new_node
            new_node.prev = cur

    def print_forward(self):
        cur = self.head
        while cur:
            print(cur.data, end=' ')
            cur = cur.next
        print()

    def print_backward(self):
        cur = self.head
        while cur and cur.next:
            cur = cur.next
        while cur:
            print(cur.data, end=' ')
            cur = cur.prev
        print()