[알고리즘] Array와 linked-list
Array(배열)
# 처음 상태
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "**서현**"]
# 1번 이동 -> 써니와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "**서현**", "써니" ]
# 2번 이동 -> 태연과 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "**서현"**, "태연", "써니" ]
# 3번 이동 -> 유리와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "**서현**", "유리", "태연", "써니" ]
# 4번 이동 -> 효연과 서현 변경
rooms = ["윤아", "수영", "티파니", "**서현**", "효연", "유리", "태연", "써니" ]
# 5번 이동 -> 티파니와 서현 변경! 후! 드디어 도착!
rooms = ["윤아", "수영", "**서현**", "티파니", "효연", "유리", "태연", "써니" ]
- 배열은 크기가 정해진 데이터의 공간 -> 한 번 정해지면 변경 불가
- 배열은 각 원소에 즉시 접근가능 -> rooms[0]
📌 배열의 인덱스의 순서는 0부터 시작
📌 즉시접근가능 -> 상수시간내에 접근가능 : O(1)내에 접근 가능하다는 의미 - 배열의 원소를 삽입/삭제하려면? 모든 원소를 다 이동해야함
최악의 경우 배열의 N만큼 옮겨야 하므로 O(N)의 시간복잡도를 가짐 - 배열의 원소를 새로 추가하려면? 새로운 공간을 할당해야하므로 매우 비효율적 자료구조
LinkedList
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
- 리스트는 크기가 정해지지 않은 데이터의 공간 -> 연결고리로 이어주기만 하면 자유자재로 늘어날 수 있음
- 리스트는 특정원소에 접근하려면? 연결고리를 따라 탐색해야함
최악의 경우 모든 화물칸을 탐색해야하므로 O(N)의 시간복잡도를 가짐
🚩 연결고리 = 포인터, 각 화물칸 = 노드 - 리스트는 원소를 중간에 삽입/삭제하려면? 앞 뒤의 포인터만 변경하면 됨
따라서 원소 삽입/삭제 O(1)의 시간 복잡도 안에 해결가능
📢 Array vs LinkedList
항목 | Array | Linked-List |
---|---|---|
특정 원소 조회 | O(1) | O(N) |
중간에 삽입/삭제 | O(N) | O(1) |
데이터추가 | 데이터추가시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 함 | 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 됨 |
정리 | 데이터에 접근하는 경우가 빈번하다면 Array사용! | 삽입과 삭제가 빈번하다면 Liked-list 사용! |
Author And Source
이 문제에 관하여([알고리즘] Array와 linked-list), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@g0garden/알고리즘-Array와-linked-list저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)