CHOI

Array (배열)

정적배열 (Static Array)

• 메모리상에서 연속적이다.
• 메모리에 선언하는 시점에 각각의 인덱스가 어느 메모리에 할당되는지 정해진다.

동적배열 (Dynamic Array)

• 원소가 추가, 삭제 됨에 따라 메모리가 늘어났다가 줄어들어야함으로 연속한 메모리에 들어있지 않다.
• 다만, 내부적으로 O(1)의 시간 복잡도로 원소를 조회할 수 있다.

배열의 시간복잡도

삽입

• [최악의 경우] 맨 앞에 새로운 값을 삽입하는 경우, 다른 값들을 모두 한칸씩 이동해야 하므로 -> O(N)
• 맨 뒤에 새로운 값을 삽입하는 경우, 다른 값들의 이동이 존재하지 않으므로 -> O(1)

삭제

• [최악의 경우] 맨 앞의 값을 삭제하는 경우, 다른 값들을 모두 한칸씩 이동해야 하므로. -> O(N)
• 맨 뒤의 값을 삭제하는 경우, 다른 값들의 이동이 존재하지 않으므로 -> O(1)

탐색

• 배열은 index 기반으로 이루어져 있기 때문에 다른 위치를 참조하여 바로 원하는 index의 원소를 구할 수 있다. -> O(1)

LinkedList (연결리스트)

• 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조
• 노드들로 구성되어 있다.
• 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있다.
• 첫 노드인 헤드(Head)로 부터 시작해, 포인터를 사용해 리스트를 순회할 수 있다.

Single Linked List (단일 연결리스트)

• 포인터가 한 방향(다음 노드)을 가리키면 Single Linked List

Doubly Linked List

• Single Linked List에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 된다.

Circular Linked List

• Linked List의 마지막 노드인 테일(Tail)과 헤드(Head)를 이으면 Circular Linked List이다.

연결리스트의 시간복잡도

삽입

• 새로운 노드를 만들어 포인터로 연결 하면 되므로 -> O(1)

삭제

• 노드를 삭제하고 이전 이후 노드를 포인터로 연결 하면 되므로 -> O(1)

탐색

• [최악의 경우] 맨 뒤의 원소를 조회하는 경우, 헤드에서부터 순차적으로 탐색을 하므로 -> O(N)
• 맨 앞의 원소를 조회하는 경우, 바로 탐색가능 하므로 -> O(1)

장단점 비교 및 정리

배열은 인덱스로 O(1)로 조회에 효율적이지만, 연결리스트에 비해 삽입/삭제가 비효율 적인 부분이 있다.

연결리스트는 순차적으로 탐색해야 함으로 배열에 비해 조회에 비효율적이며, 노드를 통해 삽입/삭제 효율성이 좋다.