[딩코딩코 2025 코딩테스트 필수 알고리즘] - 4. Array & LinkedList

본 글에 사용된 코드와 이미지의 일부는
딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp

---

Array(배열)

배열이란?

배열은 크기가 정해진 데이터의 공간이다. 원소의 순서는 0부터 시작하고, 이를 인덱스라고 부른다.

배열 특징

예시를 통해 배열의 특징을 알아보자. 캡슐 호텔을 만들었는데, 총 5명이 잘 수 있는 호텔이다.

1. 오늘 A,B,C,D,E 5명이 숙박을 한다고 한다.

rooms = ["A","B","C","D","E"]

이처럼 배열은 크기가 정해진 데이터의 공간이며, 한 번 정해지면 바꿀 수 없다.

2. 각 방에 방문해 웰컴 드링크를 전달했다.
   • 배열은 각 원소(호텔방)에 즉시 접근할 수 있다.
   • 즉시 접근이 가능하다는 말은 상수 시간 내에 접근 할 수 있음을 의미한다. → O(1) 내에 접근
3. 제일 끝 방의 E 가 A,B 사이에서 자고 싶다고 한다. 다른 손님들이 모두 이동해야 한다.
   • 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다.
   • 최악의 경우 배열의 길이 N 만큼을 옮겨야 한다. → O(N) 의 시간복잡도
4. 갑자기 호텔 프론트에 전화가 와 손님 F 가 도착할 예정이니, 방 하나를 더 준비해달라고 연락이 와, 방 6개인 호텔을 지었다.
   • 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조이다.

---

Linked List

Linked List 란?

리스트라고 불리며, 크기가 정해지지 않은 데이터의 공간이다. 연결 고리로 이어주기만 하면 크기를 자유자재로 늘릴 수 있다. 각 노드를 포인터(연결 고리) 로 연결한다.

Linked List 특징

Linked List 의 특징을 예를 통해 알아보자.

화물 열차가 있는데, 칸은 5칸, 각 화물칸은 다음 칸을 연결짓는 연결고리로 이어져 있다.

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

1. 우편 칸에 잠시 일이 생겨, 시멘트 칸을 지나, 자갈칸을 지나, 밀가루 칸을 지나 겨우 우편칸에 도착했다.
   • 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 한다.
   • 최악의 경우 모든 화물 칸을 탐색해야 하므로 O(N) 의 시간 복잡도를 가진다.
2. 시멘트 칸과 자갈 칸 사이에 흑연이라는 칸을 넣기로 했고 , 가던 도중 밀가루가 상해서 밀가루 칸을 버리기로 했다. 화물칸의 연결고리를 연결하고 , 떼서 연결했다.
   • 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다.
   • 원소 삽입/삭제를 O(1) 의 시간 복잡도 안에 할 수 있다.

---

Array vs LinkedList

경우 Array LinkedList

특정 원소 조회	O(1)	O(N)
중간에 삽입/삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당 받아야 한다.	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번할 때 사용	삽입과 삭제가 빈번할 때 사용