[알고리즘] Array와 linked-list

Array(배열)

# 처음 상태
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "**서현**"]

# 1번 이동 -> 써니와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "**서현**", "써니" ]

# 2번 이동 -> 태연과 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "**서현"**, "태연", "써니" ]

# 3번 이동 -> 유리와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "**서현**", "유리", "태연", "써니" ]

# 4번 이동 -> 효연과 서현 변경
rooms = ["윤아", "수영", "티파니", "**서현**", "효연", "유리", "태연", "써니" ]

# 5번 이동 -> 티파니와 서현 변경! 후! 드디어 도착!
rooms = ["윤아", "수영", "**서현**", "티파니", "효연", "유리", "태연", "써니" ]

1. 배열은 크기가 정해진 데이터의 공간 -> 한 번 정해지면 변경 불가
2. 배열은 각 원소에 즉시 접근가능 -> rooms[0]
   📌 배열의 인덱스의 순서는 0부터 시작
   📌 즉시접근가능 -> 상수시간내에 접근가능 : O(1)내에 접근 가능하다는 의미
3. 배열의 원소를 삽입/삭제하려면? 모든 원소를 다 이동해야함
   최악의 경우 배열의 N만큼 옮겨야 하므로 O(N)의 시간복잡도를 가짐
4. 배열의 원소를 새로 추가하려면? 새로운 공간을 할당해야하므로 매우 비효율적 자료구조

LinkedList

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

1. 리스트는 크기가 정해지지 않은 데이터의 공간 -> 연결고리로 이어주기만 하면 자유자재로 늘어날 수 있음
2. 리스트는 특정원소에 접근하려면? 연결고리를 따라 탐색해야함
   최악의 경우 모든 화물칸을 탐색해야하므로 O(N)의 시간복잡도를 가짐
   🚩 연결고리 = 포인터, 각 화물칸 = 노드
3. 리스트는 원소를 중간에 삽입/삭제하려면? 앞 뒤의 포인터만 변경하면 됨
   따라서 원소 삽입/삭제 O(1)의 시간 복잡도 안에 해결가능

📢 Array vs LinkedList

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