250207 TIL - Array와 Linked-List

Array

 

각 칸에 Index란 고유 번호가 부여돼있다는 특성이 장점이자 단점으로 작용합니다!!

조회

원하는 값의 인덱스 번호만 알면 그 값에 바로 접근 할 수 있어서 압도적으로 빠름다!! 복잡도는 O(1)

삽입 또는 삭제

배열의 마지막 값에 대한 처리는 조회와 마찬가지로 빠름다!! 복잡도는 O(1)

하지만 문제는 중간 위치에 대한 처리를 할 때인디, 바로 기존 요소가 위치한 칸들도 조정해줘야 한다는,

즉 위치가 변하는 값들에 대한 인덱스 매칭을 하나하나 새로이 해줘야한다는 불상사가 발생합니다...! 

최악의 경우인 배열의 0번째 인덱스에 대한 처리라면 기존 모든 요소들의 인덱스 매칭을 다시 해야하니 복잡도 O(N)

---

Linked-List

매 값마다 포인터가 부착돼있어서, 그 포인터를 통해 다음 값을 식별할 수 있슴다!

꼬리에 꼬리를 물고 값들이 이어진 형태라고 생각하시면 쉽습니다!!

조회 

머리 정보만 알기 때문에, 머리에서 출발해 원하는 값이 나올 때까지 타고타고 이동해야함다!!

찾는 값이 꼬리에 있다면 연결된 칸을 전부 확인해야하는 불상사가 생깁니다...!!

복잡도는 최악의 경우 칸 개수만큼을 돌게 되기 때문에 O(N)!!

삽입 또는 삭제

삽입의 경우 원하는 위치의 이전 포인터와 넣으려는 값의 포인터만 바꿔준다면 어디든 수월하게 가능하고,

삭제의 경우 원하는 위치의 이전 포인터만 바꿔주면 가능합니다!!

Linked-List 구조의 특장점 기능이라 할 수 있겄습니다!!

Doubly Linked-List
포인터가 두 개라서 앞 뒤를 각각 가리킴, 머리 뿐 아니라 꼬리 정보도 알고 있기 때문에, 양방향 탐색이 가능
Circular Linked-List
꼬리의 포인터가 머리를 가리킴. 단방향일 수도, 양방향일 수도 있음!! Linked-List를 순환해야하는 로직에 유리