Lesson 8 of 20
연결 리스트 — 다음 사람의 손을 잡은 줄
칸 번호를 버리고 화살표를 얻다
2강의 사물함(리스트)은 칸이 딱 붙어 있어서 번호만 알면 즉시 열 수 있었습니다. 대신 중간에 하나 끼워 넣으면 뒤가 전부 밀렸죠.
정반대 발상이 있습니다. 자리는 아무 데나 흩어 두고, 대신 각자 다음 사람을 손으로 가리키게 하는 겁니다. 이게 연결 리스트(linked list)예요.
🗄️ 배열 · 리스트
칸이 붙어 있음✅ 3번 칸을 즉시 열기
❌ 중간 삽입 시 전부 밀림
🔗 연결 리스트
칸이 흩어져 있음❌ 3번째를 보려면 처음부터 세 번 따라가기
✅ 중간 삽입은 화살표 두 개만 고치기
둘 중 무엇이 더 좋은가라는 질문에는 답이 없습니다. 무엇을 자주 하느냐에 따라 답이 갈릴 뿐이에요.
노드 세 개를 손으로 이어 봅니다.
Python
Runs in your browser
🎮 손을 잡고 놓아 보세요
노드를 중간에 끼워 넣어 보세요. 화살표 두 개만 바뀌고 나머지는 그대로입니다. 아래 배열 그림과 비교하면 차이가 확 보입니다.
중간에 끼워 넣기 — 화살표 두 개면 끝
민준과 서연 사이에 하윤을 넣는다면? 민준의 손을 놓고 하윤을 잡게 하고, 하윤이 서연을 잡게 하면 됩니다. 뒤에 100만 명이 서 있어도 하는 일은 똑같이 두 번이에요.
삽입도 삭제도 화살표 조작 두 번. 뒤가 아무리 길어도 똑같습니다.
Python
Runs in your browser
같은 값을 꺼내는데 드는 노력이 다릅니다.
Python
Runs in your browser
끝을 처음에 이으면 원이 됩니다. 게임 순서 돌리기에 쓰이죠.
Python
Runs in your browser
🤔 Check yourself
연결 리스트에서 중간에 값 하나를 끼워 넣을 때 하는 일은?
Answer 앞 노드가 새 노드를, 새 노드가 원래 다음 노드를 가리키게 하면 끝입니다. 뒤에 몇 개가 있든 하는 일은 똑같이 두 번이에요.
🤔 Check yourself
배열(리스트)이 연결 리스트보다 확실히 나은 점은?
Answer 칸이 붙어 있어서 시작 주소 + 번호 × 칸크기로 계산 한 번에 위치를 알아냅니다. 연결 리스트는 처음부터 세어 가야 해요.
🤔 Check yourself
파이썬의
deque 가 list 보다 앞쪽 작업이 빠른 근본적인 이유는?Answer
list는 칸이 붙어 있어 앞을 건드리면 전부 밀립니다. deque는 덩어리들을 화살표로 이어 둔 구조라서 양 끝은 언제나 즉시 처리돼요.