자료구조(Data Structure)는 데이터를 효율적으로 저장하고 조작하기 위한 방법이나 구조를 의미합니다. 프로그램에서 사용자가 데이터를 관리하고 처리하는 데 기본적으로 활용되는 도구입니다. 자료구조는 다양한 상황에서 광범위하게 활용됩니다. 이러한 자료구조들은 데이터의 특성과 처리 방식에 따라 다양한 형태로 구현됩니다.

자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉩니다:

  • 선형 자료구조: 배열, 연결 리스트, 스택, 큐
  • 비선형 자료구조: 트리, 그래프, 해시 테이블

이번 포스트에서는 배열(Array) 과 연결 리스트(Linked List) 에 대해 다룹니다.

이 두 구조는 다른 고급 자료구조(트리, 그래프 등)의 기반이 됩니다.



1. 배열 (Array)

배열은 동일한 타입의 데이터를 인덱스를 기준으로 연속된 메모리 공간에 저장하는 정적인 자료구조입니다.

특징

  • 생성 시 크기가 고정되며, 런타임 중 변경 불가
  • 메모리 연속 배치: 캐시 효율성이 높아 Cache Miss가 적고 성능이 좋음
  • 랜덤 접근 가능 → O(1)
  • 삽입/삭제 시 데이터 이동이 필요 → O(n)
  • GC(가비지 컬렉션): 요소가 사라져도 메모리 블록은 유지되며, 한 번에 삭제되어 GC 효율적

활용 예시

  • 게임 렌더링 데이터
  • 이미지 처리
  • 수치 계산용 데이터 버퍼


2. 연결 리스트 (Linked List)

연결 리스트는 노드(Node) 들이 포인터로 연결된 자료구조로, 동적 메모리 할당을 통해 필요한 만큼만 공간을 사용하는 구조입니다.

기본 구성

  • 노드(Node): 데이터 + 다음 노드를 가리키는 포인터
  • 헤드(Head): 첫 번째 노드
  • 테일(Tail): 마지막 노드
  • 더미 노드(Dummy Node): 헤드 앞이나 테일 뒤에 존재하는, 비어있는 노드 → 구현 시 삽입/삭제 로직을 간결하게 만들어줌

특징

  • 메모리가 불연속적 → Cache Miss 발생 가능성 ↑
  • 삽입/삭제: 특정 위치에서 포인터만 조정하면 되어 빠름 → O(1)
  • 랜덤 접근 불가: 앞에서부터 순차 탐색 필요 → O(n)
  • 요소 삭제 시마다 GC 발생


연결 리스트의 종류

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

  • 각 노드가 다음 노드만 가리킴
  • 메모리 효율이 중요할 때 적합

장점

  • 삽입/삭제 연산 간단하고 빠름
  • 메모리 사용량이 적음

단점

  • 역방향 탐색 불가
  • 탐색 시 항상 처음부터 순회해야 함


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

  • 각 노드가 이전 노드와 다음 노드를 모두 가리킴
  • 양방향 탐색이 필요할 때 유용

장점

  • 양방향 탐색 가능
  • 삭제 연산 시 포인터 조정 간편

단점

  • 포인터 2개 → 메모리 사용량 증가
  • 삽입/삭제 시 포인터 조작이 더 복잡함


3.원형 연결 리스트 (Circular Linked List)

  • 마지막 노드가 첫 노드를 가리킴 → 순환 구조

장점

  • 순환 반복 작업에 유리
  • 마지막 노드에서 바로 처음으로 이동 가능

단점

  • 포인터 조작이 더 복잡해질 수 있음
  • 삽입/삭제 시 연결 관계 유지 신경 써야 함