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