Data Structure_배열과 연결리스트
자료구조(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)
- 마지막 노드가 첫 노드를 가리킴 → 순환 구조
장점
- 순환 반복 작업에 유리
- 마지막 노드에서 바로 처음으로 이동 가능
단점
- 포인터 조작이 더 복잡해질 수 있음
- 삽입/삭제 시 연결 관계 유지 신경 써야 함