이번 알고리즘 주차에 배운 Array와 Linked List 자료구조에 대해 간략하게 정리해보려한다.

Array (배열)

특징

• 순차적으로 저장
• 배열의 크기는 정해진 데이터의 공간 (한번 정하면 바꿀 수 없어!)

장점

• 인덱스를 이용하여 원소에 즉시 접근 가능 (그러므로 O(1)내에 접근 썝가능~)
  

단점

• 중간에 삽입, 삭제를 위해서는 모든 원소들의 위치를 다 옮겨줘야함..경우에 따라 배열의 길이만큼 옮겨야 할 수 있으므로 최악의 경우 O(N) 이라고 할 수 있다.

결론

• 원소를 추가 시 새로운 공간을 할당해야하므로 비효율적인 자료구조지만 즉시 접근이 가능한 만큼 데이터 접근 빈번 시 사용하기 좋다.

Linked List (aka list)

특징

• 노드로 구성된 자료구조
• 크기가 정해지지 않은 데이터 공간
• 연결고리(pointer) 만 이어준다면 자유자재로 늘어난다.

장점

원소를 중간 삽입, 삭제를 위해서 앞뒤 포인터만 변경하면 됨으로 O(1) 타입, 즉 상수시간내에 할 수 있음
공간이 차더라도 맨뒤에 노드로 동적으로 쉽게 추가가능~

단점

• 하지만 특정 원소에 접근하기 위해서는 연결고리에 따라 탐색해야함..그래서 최악의 상황때는 O(N)의 시간복잡도를 가짐

결론

삽입, 삭제 빈번할 때 사용하기 좋당!

*파이썬 배열은 array지만 내부적으로 동적 배열을 사용하기 때문에 일반 리스트처럼 마지막에 데이터 추가가능