[Algorithm] 18. 선형 자료 구조

재할당 전략을 쓸 때 i번 (i≥0) 재할당 시에 복사하는 원소의 수 : 2^i

처음부터 K-2번 재할당까지 복사하는 원소의 수의 합

= 마지막 K-1번 재할당에서 복사하는 원소의 수와 거의 같음

마지막 K번 재할당에서 복사하는 원소의수

= 2 x (마지막 K-1번 재할당에서 복사하는 원소의 수)

마지막 재할당에서 복사하는 원소의 수

⇒ O(N) 이므로 2번 하더라도 전체 복사의 양은 O(N)

⇒ append() 연산을 N번 수행하는 총 수행시간이 O(N) 이라면, append()에 드는 시간은 평균적으로 O(1)

시간복잡도 관련

시간복잡도에서 중요하게 보는것은 가장 큰 영향을 미치는 n의 단위이다.

1             O(1)   --> 상수
2n + 20       O(n)   --> n이 가장 큰영향을 미친다.
3n^2          O(n^2) --> n^2이 가장 큰영향을 미친다.

O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.

표준 라이브러리의 동적 배열 구현

내부적으로 배열을 사용 → 배열과 속도 비슷

동적 배열을 사용할 때 tip ) 배열 최종 크기가 얼마인지 미리 알 때, 동적 배열의 용량(capacity)을 미리 늘려둠 → 재할당 비용 제거

연결 리스트(Linked List)

• 배열 원소의 순서를 유지하는 자료 구조는 원소의 삽입, 삭제 시간이 오래 걸림
• 해당 위치의 원소들을 하나씩 옮겨야 하기 때문 (원소의 개수에 선형 비례하는 시간 소요)

• 이를 해결하기 위해 고안된 자료구조

• 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해줌
• 연결 리스트는 원소들이 메모리 여기저기 흩어져있음
• 각 원소들이 이전과 다음 원소를 가리키는 포인터를 가지고 있음

  struct ListNode{
    int element;
    ListNode *prev, *next; // 이전 노드, 다음 노드의 포인터
  };
  

  연결 리스트 종류

1. 양방향 연결 리스트 : 각 원소가 이전과 다음 원소에 대한 정보를 모두 가짐
2. 단방향 연결 리스트 : 각 원소가 다음 원소를 가리키는 포인터만 가짐