배열(Array)
배열은 같은 타입(혹은 같은 성격)의 데이터를 연속된 칸에 나란히 놓은 자료구조.
각 칸은 인덱스(index) 라는 번호(보통 0부터)를 가지고 있어서, 인덱스로 바로 접근할 수 있음.
비유: 책장에 칸마다 책을 꽂아놓는 것 — "3번째 칸"을 바로 집어볼 수 있음.
구조(간단한 그림)
[10 | 20 | 30 | 40]
인덱스 : 0 1 2 3
주요 연산과 시간복잡도
인덱스로 접근: O(1) (즉시 접근)
탐색(search, 값 찾기): O(n) (하나씩 확인)
맨 끝에 추가(push): O(1) (동적 배열의 경우 amortized O(1))
중간에 삽입/삭제: O(n) (뒤에 있는 요소들을 한 칸씩 옮겨야 함)
메모리: 연속된 블록(contiguous), 미리 연속공간을 확보하거나 필요시 재할당(크기 늘리기) 함
const arr = [10, 20, 30];
console.log(arr[1]); // 20 -> 접근 O(1)
arr.push(40); // 끝에 추가, 보통 빠름
arr.splice(1, 0, 15);// 인덱스 1 위치에 15 삽입 -> 내부적으로 O(n)
연결 리스트(Linked List)
연결 리스트는 노드(node) 라는 작은 박스들이 있고, 각 노드는 값(value)과 다음 노드를 가리키는 포인터(또는 참조)를 가지고 있음
노드들이 메모리상에 연속적으로 붙어있을 필요는 없고, 포인터로 연결되어 있음
비유: 각 노드가 한 장의 종이(값)이고, 종이에 다음 종이의 위치를 적어 연결하는 편지 전달 줄 같은 느낌
단방향 싱글링크드 리스트
[10 | next] -> [20 | next]-> [30 | next ] -> null
type
Singly (단방향) : 각 노드가 다음(next)만 가리킴
Doubly (이중) : 각 노드가 이전(prev)과 다음(next)을 가리킴 — 앞뒤 이동 가능
Circular : 마지막 노드가 다시 첫 노드를 가리켜 원형 구조
주요 연산과 시간복잡도(대략)
인덱스로 접근: O(n) (앞에서부터 순차 탐색)
탐색(search): O(n)
맨 앞(head)에 삽입/삭제: O(1) (빠름)
특정 위치(노드 포인터 알고 있을 때)에서 삽입/삭제: O(1) (포인터만 바꾸면 됨)
메모리: 각 노드마다 포인터(주소)를 추가로 저장해야 해서 약간 더 많은 메모리가 필요함
코드 예시(간단한 삽입 - JavaScript 형태)
class Node {
constructor(value){ this.value = value; this.next = null; }
}
class LinkedList {
constructor(){ this.head = null; }
insertAtHead(val){
const node = new Node(val);
node.next = this.head;
this.head = node; // O(1)
}
}
Array vs LinkedList — 비교
접근 속도: Array O(1) vs LinkedList O(n)
삽입/삭제(중간): Array O(n) vs LinkedList O(1) (단, 위치를 찾는 비용 제외)
메모리: Array는 연속 블록, LinkedList는 노드+포인터(추가 메모리)
구현/사용 편의성: Array가 사용하기 쉬움(언어에서 기본 지원), LinkedList는 포인터 조작 필요
🛜 언제 쓰나?
Array: 인덱스로 빠르게 접근해야 할 때, 빈번한 랜덤 접근
LinkedList: 빈번한 삽입/삭제(특히 앞부분) 또는 크기 불확실시(하지만 현대에는 동적 배열이 더 자주 쓰임)
간단한 사용 예시(언제 어떤 걸 선택?)
웹에서 이미지 리스트를 인덱스로 빠르게 불러올 때 → Array
중간에 항목을 자주 추가/삭제해야 하고, 포인터 관리가 필요할 때(특정 low-level 구현) → LinkedList
정리
Python 의 list 는 array 로 구현되어 있음.
