1. 배열
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다
대부분에 프로그램 언어에서 동일 타입의 데이터를 저장합니다. 예를 들어 배열이 "int"타입인 경우 정수 요소만 저장할 수 있으며 double, float, char 등과 같은 다른 타입의 요소는 저장할 수 없다.
배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.
데이터를 연속된 메모리 공간에 순차적으로 저장한다.
선언 시 배열의 크기를 정하기 때문에 배열의 크기는 고정되어 있으며 변경할 수 없다.
각 데이터와 인덱스는 1:1 대응하도록 구성되어 있다.
배열의 장점
장점 설명
| 빠른 인덱스 접근 | O(1) 시간 복잡도로 특정 위치의 요소에 즉시 접근 가능 (arr[5] 등) |
| 캐시 친화적 | 메모리가 연속적으로 할당되므로 CPU 캐시 효율이 좋음 |
| 구현이 단순 | 구조가 단순하여 구현 및 디버깅이 쉬움 |
| 읽기 작업에 강함 | 순차 탐색, 정렬 등 읽기 기반 연산에서 효율적 |
캐시에 친화적이다?
캐시 : CPU와 메인 메모리(RAM) 사이에 있는 아주 빠른 임시 저장소.
자주 사용하는 데이터를 빠르게 읽기 위해 사용하는 고속 메모리
현대 CPU는 메모리 접근 시 한 번에 여러 바이트를 캐시에 블록 단위(=캐시 라인)로 불러온다.
배열은 요소들이 연속된 주소에 위치하기 때문에,
한 번 접근하면 그 이후 요소들도 캐시에 같이 로딩되는 경우가 많습니다.
즉, arr[0]을 읽으면, arr[1], arr[2]도 이미 캐시에 있을 가능성이 큼 → 빠른 반복 접근 가능
읽기 작업에 강하다?
인덱스 기반 접근이 O(1) 이기 때문
배열은 arr[i] 식으로 곧바로 원하는 위치의 메모리 주소를 계산해 접근할 수 있다.
시간 복잡도는 O(1) – 매우 빠름
이는 정렬된 데이터 탐색, 조회, 순차 처리에서 특히 효율적.
배열의 단점
단점 설명
| 크기 고정 | 선언 시 크기를 정해야 하며, 중간에 변경이 불가능 |
| 삽입/삭제 비용이 큼 | 중간에 삽입하거나 삭제하려면 나머지 요소를 한 칸씩 이동해야 함 → O(n) |
| 공간 낭비 가능성 | 미리 크게 선언하면 메모리 낭비, 작게 선언하면 오버플로우 위험 |
| 연속된 메모리 필요 | 큰 배열은 연속된 공간이 필요하므로 메모리 단편화 문제 발생 가능 |
삽입/삭제 비용이 큰 이유
1: 배열은 메모리상에 연속적으로 저장됨
배열은 빈틈 없이 연속된 메모리 공간에 요소들이 저장.
따라서 중간에 값을 삽입하거나 삭제하려면 빈 공간을 만들거나 메워야 함 → 다른 요소들을 이동시켜야 함.
2. 연결 리스트(Linked List)
LinkedList는 Node라는 객체로 이루어져 있는데 Node는 데이터를 저장하는 field와 다음 노드를 가리킬 수 있는 next pointer field로 구성이 되어있다.
이말인 즉슨, 이 노드들이 연결된 형태의 자료구조를 바로 LinkedList라고 하는 것.
예를 들어, 학교에서 어느 반의 모든 학생들의 데이터를 저장한다고 했을 때, 학생 한명 한명의 신상정보 자료를 노드로 만들고, 1번 학생의 신상정보 자료에 2번 신상정보 자료가 어디 있는 지 표시를 해 놓는 방식
밑의 소세지 처럼 자료를 연결해놓은것
노드(Node)
- 연결 리스트의 기본 단위 (데이터 + 다음 노드를 가리키는 포인터 포함)
- 각 노드는 보통 값(value)과 다음 노드의 참조(next)로 구성됨
헤드(Head)
- 연결 리스트의 시작 노드
- 리스트 전체를 접근하려면 항상 head부터 따라가야 함
포인터 (Pointer) / 참조 (Reference)
- 다음 노드를 가리키는 변수
- Java에서는 포인터라는 표현 대신 "참조(reference)"를 사용
- 노드를 연결하는 끈 역할
테일(Tail)
- 연결 리스트의 마지막 노드
- tail.next == null (또는 tail.next == head in 원형 리스트)
테일 포인터(Tail Pointer)
연결 리스트에서 테일 노드를 따로 변수로 보관하면 얻는 이점:
- 맨 끝에 삽입이 빠름 (O(1))
- 일반적으로 맨 끝 삽입은 탐색 → O(n)
- 하지만 tail을 알고 있으면 즉시 붙일 수 있음
- 큐(Queue) 구현 시 필수
- 큐는 **뒤에 삽입(Enqueue)**하기 때문에 tail을 알아야 함
삽입
삽입은 제일 끝이 아니라 중간에 넣는 경우
LinkedList는 ArrayList와는 다르게 데이터를 뒤로 한 칸씩 전부 밀어줄 필요가 없습니다. 그냥 간단히 pointer만 바꿔주면 되기 때문에 논리는 간단하지만 삽입 위치를 찾기 위해서는 순회를 통해 찾아야 하기 때문에 시간복잡도는 O(n)
1. 먼저, 삽입을 원하는 노드를 생성
2. 해당 노드의 previous(이전의) node의 next 포인터를 본인 노드와 연결하고 previous node의 next pointer가 가리키고 있던 노드를 본인 노드의 next pointer로 가리킴로써 연결을 삽입을 마무리한다
삭제
LinkedList에서 삭제하고자 하는 노드가 있을 때는 그 위치를 찾아가야 하기 때문에 결정되는 시간복잡도는 O(N)입니다.
- head와 tail노드로 무작정 알아낼 수 없기 때문
ArrayList에서는 삭제할 위치를 찾고 뒤의 데이터들을 앞으로 한 칸씩 당기는데 또 시간이 O(N)만큼 소요가 됐다면,
LinkedList는 데이터를 당겨오지 않고 pointer만 조금 바꾸어 주면 삭제 과정이 자동으로 이루어지게 된다.
삭제하고자 하는 노드의 이전노드의 참조를 삭제하고자 하는 노드의 다음 노드를 가리키게 하며 삭제할 노드의 참조를 null로 해주면 삭제가 된다.
연결 리스트의 종류
1. 단일 연결 리스트
단일 연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터(링크)를 갖고 있고,
이 링크를 따라 한 방향으로만 연결되어 있는 자료구조입니다.
- 단방향 연결 구조 (앞 → 뒤)
- 마지막 노드는 null을 가리켜 리스트의 끝을 의미
장점
- 삽입/삭제가 빠름
- 배열처럼 요소를 이동하지 않고 링크만 바꾸면 됨
- 특히 맨 앞(head)에서의 삽입/삭제는 O(1)
- 메모리 효율적
- 배열은 고정 크기지만, 단순 연결 리스트는 필요할 때 노드를 생성하므로 공간 낭비 적음
단점
- 임의 접근 불가능
- 인덱스로 바로 접근할 수 없음 → 무조건 처음부터 순차 탐색
- 뒤에서부터 탐색 불가
- 이전 노드를 가리키는 포인터가 없어서, 뒤에서 앞으로 가는 연산은 불가능
이중 연결 리스트
이중 연결 리스트는 각 노드가 **두 개의 링크(포인터)**를 가지는 연결 리스트.
즉, 한 노드는 **앞 노드(prev)**와 **다음 노드(next)**를 모두 가리킨다.
양방향으로 탐색이 가능한 자료구조
장점
- 양방향 순회 가능
- 단순 연결 리스트는 한 방향(→)으로만 이동 가능하지만,
이중 연결 리스트는 ← → 양방향 모두 가능
- 단순 연결 리스트는 한 방향(→)으로만 이동 가능하지만,
- 삽입/삭제가 유연
- 현재 노드만 알고 있으면,
앞이나 뒤 노드를 쉽게 추가하거나 제거할 수 있음 - 양쪽 끝에서도 효율적인 삽입/삭제 가능 → Deque, LRU Cache 등에서 유용
- 현재 노드만 알고 있으면,
- 어느 위치에서도 앞뒤 접근 가능
- 노드 한 개만 알고 있어도 이전/다음 모두 접근 가능
- 중간 노드 기준으로도 자유롭게 연결 조작 가능
단점
- 메모리 사용 증가
- 각 노드가 prev와 next 두 개의 링크를 유지해야 하므로
단순 연결 리스트보다 메모리 소비가 많음
- 각 노드가 prev와 next 두 개의 링크를 유지해야 하므로
- 구현 복잡도 증가
- 삽입/삭제 시 두 방향의 링크를 모두 관리해야 해서
구현이 더 까다롭고 실수하기 쉬움
- 삽입/삭제 시 두 방향의 링크를 모두 관리해야 해서
활용 예시
- LRU Cache(가장 오래전에 사용된 데이터를 먼저 제거하는 캐시)
→ 최근 사용된 데이터를 앞쪽에, 오래된 데이터를 뒤로 배치하고 빠르게 제거/갱신
→ 이중 연결 리스트 + 해시맵 조합으로 구현 - 양방향 큐 (Deque)
→ 앞뒤에서 삽입/삭제가 가능한 큐 - 브라우저 방문 기록
→ "뒤로 가기 / 앞으로 가기"처럼 양방향 탐색이 필요한 경우
순환 연결 리스트
순환 연결 리스트는 마지막 노드가 다음 노드로 null이 아닌, 리스트의 첫 번째 노드(헤드)를 가리키는 원형 구조의 연결 리스트.
연결 리스트의 끝이 없고, 계속 순환됨
단일 연결 리스트 또는 이중 연결 리스트 형태 모두 가능
장점
- 원형 큐(Circular Queue) 구현에 적합
- 양 끝 삽입/삭제가 자유로움
- **순환적 작업(예: 라운드 로빈, 토큰링)**에 활용됨
단점
- 종료 조건을 명확히 처리하지 않으면 무한 루프 발생 가능
- 구현이 일반 연결 리스트보다 조금 더 복잡함
- 디버깅/순회 중 실수하기 쉬움
활용 사례
- 운영체제 스케줄링 (라운드 로빈 방식)
- 원형 큐 구조
- 음악/이미지 뷰어에서 "다시 처음부터 재생" 기능
- 게임에서 순차적 턴 관리
Array vs LinkedList vs ArrayList
여기서 잠깐 Array 랑 ArrayList의 차이는 배열의 길이가 고정이냐 가변이냐가 가장큰차이고 거의 다른점이 없으니 스킵하겠다.
특징비교
LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성한 이유는 ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었기 때문이다.
ArrayList의 문제점
- 배열 복사 비용 발생
- 용량(capacity)이 꽉 찰 경우, 새 배열로 전체 복사 필요 → 성능 저하
- 중간 삽입/삭제 시 요소 이동
- 중간에 삽입하거나 삭제하면 뒤 요소들을 한 칸씩 이동해야 함 → O(n)
- 메모리 낭비
- 삭제가 반복되면 빈 공간이 생기고도 메모리를 차지함
- 리사이징 비용
- 자동 크기 조절 과정에서 복사와 시간 소모 발생
LinkedList만 쓰면 효율이 더 좋나?
LinkedList도 만능은 아니다!
요소를 get 하는 과정에서 ArrayList와 굉장한 성능 차이를 보이는데, ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만이 가능하기 때문이다.
접근 속도 느림: 노드들이 메모리 곳곳에 흩어져 있어,
ArrayList보다 데이터 탐색 시 지연 시간이 큼
무작위 접근 불가: 특히 **단일 연결 리스트(Singly Linked List)**는
인덱스를 이용한 접근에 부적합
메모리 사용량 증가:
각 노드가 next, prev 같은 참조자를 추가로 저장하므로
배열보다 메모리 소모가 큼
시간 복잡도 비교
LinkedList의 삽입/삭제는 항상 O(1)이 아니다.
맨 앞이나 뒤에서는 O(1)이지만, 중간 위치에서는 탐색이 필요해 O(n)이 된다.
그러면 실제로는 뭐를 더 많이쓰는데?
LinkedList는 의외로 잘 사용되지 않는다
보통 ArrayList 와 LinkedList 중에 어느걸 사용하면 되냐고 묻는다면, 삽입 / 삭제가 빈번하면 LinkedList를, 요소 가져오기가 빈번하면 ArrayList를 사용하면 된다 라고들 가르쳐 주지만, 사실 성능면에서 둘은 큰 차이가 없다.
LinkedList를 사용하는 사례보다 그냥 ArrayList를 사용하는 사례가 많은데, 자바의 컬렉션 프레임워크 등 자바 플랫폼의 설계와 구현을 주도한 조슈아 블로치(Joshua Bloch) 본인도 자신이 설계했지만 사용하지 않는다고 말할 정도
= ArrayList 쓰자 그냥;
