자료구조의 개념과 동작 원리

자료구조의 정의

 

자료구조(Data Structure)란 쉽게 말해 "컴퓨터에서 데이터를 효율적으로 다루기 위해 데이터를 메모리에 저장, 조직, 관리하는 구조적인 방법을 뜻한다. 단순히 데이터를 쌓아두는 것이 아니라, 우리가 원하는 작업을 가장 빠르고 메모리를 적게 쓰면서 처리할 수 있도록 정리하는 규칙 체계이다.

---

자료구조가 필요한 이유

 

컴퓨터의 핵심 자원은 CPU와 메모리이다. 데이터의 특성에 맞는 적절한 자료구조를 선택하면 효율성과 추상화라는 두 가지의 이점을 얻을 수 있다.

---

자료구조의 분류

1. 단순 구조 (Primitive Data Structure)

프로그래밍 언어에서 제공하는 가장 기본적인 데이터 타입.

• int, float, str, bool 등

2. 선형 구조 (Linear Data Structure)

데이터를 한 줄로 차례대로 나열한 구조. 데이터 간의 관계가 1:1이다.

 

2 - 1 배열 (Array)

 

여러 원소들을 순차적으로 메모리에 저장(contiguous memory locations)하는 구조. 기본적으로 배열은 모든 원소가 같은 자료형이어야 하며, 배열의 크기를 변경할 수 없다. Array를 담은 변수에는 배열의 첫 원소의 메모리 주소를 담고 있기 때문에 index를 사용하여 원소에 빠르게 접근할 수 있다. 배열의 원소가 모두 같은 자료형이기 때문에, 원소의 자료형이 무엇인지에 따라 다음 index의 원소가 위치한 물리적인 위치로 얼마만큼 이동해야 하는지 알 수 있다.

 

장점

• 구현이 쉽다.
• Index를 활용하면 랜덤으로 원소에 접근(Random access)이 가능하여 검색에서 성능이 좋다.
• 순차 탐색에서도 배열은 연속된 메모리 공간에 할당하므로 연결 리스트보다도 빠른 성능을 보인다.
• 운영체제의 캐시 지역성을 활용할 수 있다.

단점

• (원소를 이동해야 하는 연산작업이 필요하므로) 삽입, 삭제 시 비효율적.
• 초기에 선언한 크기를 변경할 수 없다. (사용안한 만큼의 메모리가 낭비될 수 있다.)
• (배열 요소를 삭제했더라도 변수의 선언이 해제되지 않는 이상 점유하고 있는 메모리이므로) 메모리의 재사용이 불가능하다.

Array와 List의 차이

 

Python의 List 자료형도 Array처럼 index를 사용하여 원소에 접근할 수 있지만,

1. 서로 다른 자료형을 원소로 가질 수 있으며,

2. 동적 배열(Dynamic Array)로써 Array와는 다르게 자유롭게 크기를 확장할 수 있다.

3. 리스트 안의 원소들은 그 값들을 자유롭게 변경도 가능(Mutable)하다.

---

2 - 2 스택 (Stack)

 

한쪽이 막힌 통처럼, 늦게 들어간 데이터가 먼저 나오는 구조 (LIFO). 데이터의 삽입과 삭제가 저장소의 맨 윗부분에서만 일어나는 자료구조. Stack은 연속으로 저장된 데이터 구조를 가지고 있고 맨 위 요소에 대한 포인터(주소값)를 가지고 있는 Array로 구현할 수 있다.

 

장점

• 참조 지역성(한번 참조된 곳은 다시 참조될 확률이 높다)을 활용할 수 있다.

단점

• 데이터를 탐색하기가 어렵다.

LIFO 구조를 사용하는 이유

 

'가장 최근에 했던 작업'이나 '현재 맥락'을 기억하고 되돌아 가야하기 때문. 컴퓨터가 어떤 작업을 하다가 잠시 다른 작업을 하러 갈 때, 방금 전까지 무엇을 하고 있었는지를 기억해야 돌아올 수 있다. 이때 가장 최근에 중단한 작업이 항상 맨 위에 쌓여 있어야 바로 꺼내서 이어 할 수 있기 때문에 LIFO 구조를 사용한다.

→ 히스토리(이력) 관리와 되돌리기(Undo), 그리고 함수 호출 시 이전 메모리 상태를 복구하기 위함.

---

2 - 3 큐 (Queue)

 

목록 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 자료를 빼낼 수 있는 자료구조. 먼저 집어넣은 데이터가 먼저 나오는 (FIFO : First In, First Out) 구조로 데이터를 저장한다. 데이터가 입력한 순서대로 처리되어야 할 경우에 사용한다. Queue에 새로운 데이터가 들어오면 Queue의 끝에 데이터가 추가되며(enqueue), 반대로 삭제될 때는 첫 번째 위치의 데이터가 삭제된다(dequeue).

 

FIFO 구조를 사용하는 이유

 

'공평함'과 '순서 보장'이 필요한 문제를 해결하기 위함. 컴퓨터가 처리해야 할 명령이 한꺼번에 몰릴 때, 먼저 들어온 명령을 먼저 처리해주지 않으면 나중에 들어온 명령이 먼저 처리되어 순서가 뒤죽박죽 꼬이거나, 먼저 온 명령이 영원히 처리되지 못하는 문제 (기아 현상)가 발생할 수 있다.

→ 요청이 들어온 시간 순서대로 데이터를 안전하게 버퍼링(대기)하고 처리하기 위함.

---

 

2 - 4 연결 리스트 (Linked List)

 

데이터와 다음 노드의 주소를 담고 있는 노드들이 한 줄로 연결되어 있는 방식의 자료 구조.

연결되는 방향에 따라, Singly linked list (단일 연결 리스트), Doubly linked list (이중 연결 리스트), Circular linked list (환형 연결 리스트) 가 있다.

3. 비선형 구조 (Non-Linear Data Structure)

데이터를 일렬로 나열하지 않고 복잡한 관계(1:N 또는 N:N)로 연결한 구조.

• 트리(Tree) : 회사 조직도나 컴퓨터의 폴더 디렉토리처럼 계층적 구조를 가진다 (1:N 관계)
• 그래프(Graph) : 지하철 노선도처럼 데이터들이 거미줄처럼 복잡하게 연결된 구조 (N:N 관계)

4. 파일 구조 (File Organization)

메모리가 아닌 하드디스크나 SSD같은 보조기억장치에 데이터를 대량으로 저장할 때 사용하는 구조.

• 순차파일, 인덱스 파일 등

---

자료구조의 동작 방식

 

대부분의 자료구조는 목적과 형태는 다르지만, 공통적으로 다음과 같은 4가지 기본 동작(연산)을 수행하며 작동한다. 이를 흔히 CRUD 연산 또는 자료구조의 기본 연산이라고 부른다.

• 접근 / 조회 (Access / Search) : 특정 위치에 있는 데이터를 읽거나, 원하는 데이터가 어디에 있는지 찾는 동작
• 삽입 (Insert) : 새로운 데이터를 자료구조 안에 집어넣는 동작
• 삭제 (Delete) : 기존에 있던 데이터를 자료구조에서 제거하는 동작
• 수정 (Update) : 기존 데이터를 새로운 데이터로 변경하는 동작

---

자료구조의 장점과 단점

 

각 자료구조는 트레이드오프(Trade-off, 하나를 얻으면 하나를 잃는 관계)를 가진다.

 

장점

• 프로그램 성능 최적화 : 상황에 맞는 자료구조를 쓰면 데이터 처리 속도가 비약적으로 빨라진다.
• 메모리 절약 : 데이터를 규칙성 있게 저장하므로 낭비되는 메모리 공간을 최소화할 수 있다.
• 코드의 재사용성과 가독성 : 정형화된 구조를 사용하므로 다른 개발자가 코드를 봐도 구조를 쉽게 이해할 수 있다.

 

단점

• 설계의 복잡도 증가 : 데이터 구조가 복잡해질수록 이를 구현하고 관리하는 코드가 어려워진다.
• 특정 연산의 비효율성 : 예를 들어 데이터 조회가 빠른 자료구조는 데이터 삽입 / 삭제가 느릴 수 있고, 반대로 삽입 / 삭제가 빠른 구조는 조회가 느릴 수 있다.

---

자료구조의 실제 활용 사례

• Array : 주소록의 연락처 목록, 음악 재생 목록 등 순서가 중요하고 자주 꺼내 보는 데이터
• Stack : 인터넷 브라우저의 '뒤로가기' (가장 최근 방문한 페이지로 이동), 문서 편집기의 되돌리기 (Ctrl + Z)
• Queue : 프린터의 인쇄 대기열 (먼저 인쇄를 누른 문서부터 출력), 수강신청이나 티켓팅의 디지털 대기 시스템
• Tree : 컴퓨터의 파일 탐색기 (폴더 구조), 회사의 조직도, 데이터베이스의 인덱스 검색
• Graph : 네이버 지도나 구글 맵의 길 찾기 (최단 경로), 페이스북이나 인스타그램의 추천 친구 (인맥 네트워크)

---

배열, 큐, 스택의 차이

비교 항목	배열 (Array / List)	스택 (Stack)	큐 (Queue)
구조적 형태	데이터가 일렬로 연속 배열됨	한쪽 끝만 뚫려 있는 통 모양	양쪽 끝이 모두 뚫려 있는 파이프 모양
데이터 접근	임의 접근 가능 (인덱스로 바로 접근)	제한적 접근 (가장 위쪽 데이터만 가능)	제한적 접근 (가장 앞쪽 / 뒤쪽만 가능)
핵심 원칙	순서 지정 및 인덱싱	LIFO (후입선출 - 마지막이 먼저 나옴)	FIFO (선입선출 - 처음이 먼저 나옴)
데이터 삽입 / 삭제위치	아무 위치나 가능 (단, 중간은 밀어내기 필요)	오직 한쪽 끝(Top)에서만 삽입 / 삭제	한쪽 끝(Rear)에서 삽입, 반대쪽(Front)에서 삭제

---

코드 구현

1. 배열 (Array)

# 데이터 삽입

test1 = ['a', 'b', 'c']

# 맨 뒤에 삽입
test1.append('d')     # append 메서드로 맨뒤에 데이터 추가
print(test1)

# index의 위치에 삽입 (list 범위를 초과하는 index는 맨 뒤에 삽입)
test1.insert(0, 'f')  # insert 메서드로 원하는 위치에 데이터 추가
print(test1)

# 결과값
# ['a', 'b', 'c', 'd']
# ['f', 'a', 'b', 'c', 'd']

# 데이터 삭제

test2 = ['a', 'b', 'c']

# del 키워드를 통한 index의 데이터 삭제
del test2[0]
print(test2)

# remove 메서드로 데이터를 찾아서 삭제 (데이터가 없다면 ValueError 발생)
test2.remove('b')
print(test2)

# pop() 메서드로 데이터를 꺼내서 삭제 (데이터가 없다면 IndexError 발생)
test2.pop(0)
print(test2)

# 결과값
# ['b', 'c']
# ['c']
# []

# 데이터 조회

test3 = ['a', 'b', 'c']

# index() 메서드를 통한 인덱스 검색
test3.index('b')
print(test3.index('b'))

# []를 이용한 인덱스 조회
target_data = test3[0]
print(target_data)

# enumerate() 함수를 통한 데이터 전체 조회
for idx, data in enumerate(test3):
    print(f'{idx}번 데이터 : {data}')
    
# 결과값
# 1
# a
# 0번 데이터 : a
# 1번 데이터 : b
# 2번 데이터 : c

 

👉 배열이 없었을 때는 모든 데이터의 메모리 주소를 기억하거나 메모리 전체를 뒤져서 데이터를 찾았어야 했지만, 데이터를 메모리에 배열로 저장하면 첫 번째 데이터의 주소와 인덱스만 알고 있다면 빠르게 데이터에 접근할 수 있게 된다.

2. 큐 (Queue)

class Queue:
    def __init__(self):
        self.queue = []                # 데이터를 저장할 빈 리스트 생성

    def enqueue(self, data):
        self.queue.append(data)        # .append()를 이용해 리스트 가장 뒤에 데이터 추가

    def dequeue(self):
        if len(self.queue) == 0:       # 큐가 비어있다면 None을 리턴
            print('큐가 비어있습니다.')
            return None
        
        Take_data = self.queue.pop(0)  # FIFO에 맞춰 0번 인덱스 데이터를 제거하고 반환
        return Take_data
    
    def display(self):
        print(self.queue)

q = Queue()

q.enqueue('a')
q.enqueue('b')
q.enqueue('c')
q.display()

q.dequeue()
q.display()

# 결과값
# ['a', 'b', 'c']
# ['b', 'c']             # 가장 먼저 들어온 데이터가 가장 먼저 나간다.

 

👉 프린터의 대기열이나 티켓팅 시스템과 같이 수많은 요청이 한번에 몰려드는 상황에 가장 먼저 들어온 요청을 가장 먼저 출력해 주는 순서(FIFO)로 진행하면서 데이터가 깨지거나 순서가 뒤섞이지 않고 처리할 수 있게 되었다.

3. 스택(Stack)

class Stack:
    def __init__(self):
        self.stack = []                  # 데이터 저장용 빈 리스트 생성
    
    def push(self, data):                # 스택의 맨 위에 데이터 추가
        self.stack.append(data)

    def pop(self):
        if len(self.stack) == 0:         # 스택이 비어있다면 None 리턴
            print('스택이 비어있습니다.')
            return None
        return self.stack.pop()          # 스택의 위쪽 데이터를 제거하고 반환 (LIFO)

    def display(self):
        print(self.stack)

s = Stack()

s.push('a')
s.push('b')
s.push('c')
s.display()

s.pop()
s.display()

# 결과값
# ['a', 'b', 'c']
# ['a', 'b']          # 가장 나중에 들어온 데이터가 가장 먼저 나간걸 알 수 있다.

 

👉 홈페이지 뒤로가기나 Ctrl+Z를 누르면 삭제취소가 돼 듯, 가장 나중에 들어온 데이터를 가장 먼저 출력해 주면서 데이터의 손실 없이 역순으로 안전하게 돌아갈 수 있게 되었다.