총 5명이 숙박 가능한 캡슐 호텔을 만들어보자
rooms = ["손흥민", "케인", "시몬스", "무아니", 쿠두스"]
그런데, 쿠두스가 손흥민과 케인 사이에서 자고 싶어 한다.
1. 쿠드스와 무아니의 방을 바꾼다.
rooms = ["손흥민", "케인", "시몬스", "쿠두스", "무아니"]
2. 쿠두스와 시몬스의 방을 바꾼다.
rooms = ["손흥민", "케인", "쿠두스", "시몬스", "무아니"]
3. 쿠두스와 케인의 방을 바꾼다.
rooms = ["손흥민", "쿠두스", "케인", "시몬스", "무아니"]
-> 총 **3번**의 이동이 필요하다.만약, 여기서 다른 선수가 누군가의 사이에 숙박을 원한다면 어떻게 될까?
6명의 인원을 받기 위해서 6명이 숙박 가능한 새로운 호텔을 지어야한다.
여기서, 캡슐호텔이 바로 Array, 배열이다.
- 배열은 크기가 정해진 데이터의 공간으로, 한 번 정해지면 바꿀 수 없다.
- 배열은 인덱스로 O(1)로 접근이 가능하다.
- 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다. 최악의 경우 배열의 길이만큼 옮겨야 하므로 O(N)의 시간 복잡도를 가진다.
- 배열의 크기를 벗어나서, 새로운 원소를 추가하려면 새로운 공간을 새로 할당해야 하므로 매우 비효율적인 자료구조이다.
이번에는 화물 열차를 만들어보자.
화물칸은 다음 칸을 연결짓는 연결고리로 이어져 있다.
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]기관실에 있는 나는 우편실에 우편을 가지러가기 위해서는 총 4번의 이동이 필요하다.
# 현재 상태
내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
목적지
# 1번 이동
내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
목적지
# 2번 이동
내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
목적지
# 3번 이동
내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
목적지
# 4번 이동
내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
목적지
이번에는, 자갈칸과 밀가루 칸 사이에 흑연 칸을 넣기로 했다. 간단하게 자갈 칸의 연결고리를 흑연 칸에 연결하고, 흑연 칸의 연결고리를 밀가루 칸의 연결하면 된다.
# 처음 상태
["자갈"] -> ["밀가루"] -> ["우편"]
# 1. 자갈 칸의 연결 고리를 흑연 칸에 연결한다.
["자갈"] -> ["흑연"] ["밀가루"] -> ["우편"]
# 2. 흑연 칸의 연결 고리를 밀가루 칸에 연결한다.
["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]
밀가루가 상해서 밀가루 칸을 버리기로 했다.
# 현재 상태
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]
# 흑연 칸의 연결 고리를 때서, 우편 칸으로 연결한다.
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["흑연"] -> ["우편"]여기서 화물 열차가 바로 Linked List, 리스트입니다.
다시 특징을 생각해보면,
-
각 화물칸은 다음 칸을 연결짓는 연결고리로 이루어져 있다.
-> 리스트는 크기가 정해지지 않은 데이터의 공간이다. 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있다. -
특정 칸을 가기 위해서는 연결 고리를 따라서 칸을 이동해야 한다.
-> 리스트의 특정 원소에 접근하기 위해서는 연결 고리를 따라 이동해야 한다. 최악의 경우 전체를 탐색해야하므로 O(n)의 시간 복잡도를 가진다. 여기서 화물칸은 노드, 연결 고리를 포인터라고 부르겠다 -
특정 칸을 넣기로 한다면, 앞에 칸과 넣을 칸을 연결하고, 넣을 칸의 뒤를 뒤에 칸과 연결하면 된다. 또한 특정 칸을 버린다면, 특정 칸의 앞 칸의 뒤를 특정 칸 뒤와 연결하면 된다.
-> 리스트는 특정 원소를 삽입, 삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 따라서 시간 복잡도는 O(1)을 가진다.
Array vs Linked List
경우 Array LinkedList 특정 원소 조회 O(1) O(n) 중간에 데이터 삽입, 삭제 O(n) O(1) 데이터 추가 새로운 메모리 공간 할당 맨 뒤에 노드만 동적으로 추가 정리 데이터에 접근하는 경우가 빈번하다면 Array 사용 삽입과 삭제가 빈번하다면 Linked List 사용
Python list = 링크드 리스트 + 배열?
Python list는 링크드 리스트처럼 요소를 쉽게 추가/삭제할 수 있는 유연성과, 배열처럼 인덱스로 빠르게 접근할 수 있는 장점을 모두 갖춘 효율적인 자료구조라고 생각하면 됩니다.
실제로 내부 구현은 완전히 배열 기반(dynamic array)이지만, 사용자는 마치 “배열과 링크드 리스트의 장점을 혼합한 구조”처럼 편리하게 사용할 수 있습니다.
링크드 리스트 구현
