선형 자료 구조는 뭘까?

18.2 동적 배열

• 배열을 이용해 만들어낸 별도의 자료 구조이기 때문에 배열의 특징을 그대로 받는다.
  • 원소들은 메모리의 연속된 위치에 저장된다.
    • 캐시의 효율성과 직결되어 중요한 포인트
  • 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.

O(1)?

• 시간복잡도 개념에서 상수를 의미한다.
• 입력에 관계없이 복잡도가 동일하게 유지된다.

• 동적 배열만의 특징은 아래와 같다.
  • 배열의 크기를 변경하는 resize() 연산이 가능하다.
    • 이 동작을 수행하는 데는 배열의 크기 N에 비례하는 시간이 걸린다.
  • 주어진 원소의 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원한다.
    • 이 동작을 수행하는 데는 상수 시간이 걸린다.
• 동적 배열의 크기가 바뀌는 과정은 아래와 같다.
  • 새 배열을 동적으로 할당 받는다.
  • 기존 원소들을 복사한다.
  • 새 배열을 참조하도록 바꿔치기 한다.
• 동적 배열의 내부에서는 배열의 크기가 커지는 것에 대한 여유분의 메모리를 확보하고 있고, 실제로 동적 배열을 사용하는 프로그램에서는 실제 사용 중인 배열의 크기만 인식한다.
  • 그렇기 때문에 현재 배열의 크기와 배열이 현재 저장된 메모리 내의 위치 외에 용량을 저장해야한다

동적 배열 A

• A 같은 경우엔 append() 연산으로 size만 1 늘리면 된다.

동적 배열 B

• B 의 경우처럼 더 늘릴 크기가 없다면? → 재할당 과정
  • 더 큰 새 배열을 동적으로 할당 받는다.
  • 새 배열에 기존 배열의 내용을 모두 복사한다.
  • 복사한 다음 배열에 대한 포인터를 바꿔치기 한다.
• 동적 배열은 직접 구현할 일이 거의 없다.

18.3 연결 리스트

• 특정 위치에서 삽입과 삭제를 상수 시간에 할 수 있게 해준다.
• 배열은 메모리의 연속된 위치에 원소들이 저장되어 있지만 연결 리스트는 원소들이 흩어져 있고, 각 원소들이 이전과 다음 원소를 가리키는 포인터를 가지고 있다.
  • 양방향 연결 리스트

양방향 연결 리스트
각 원소가 이전과 다음 원소에 대한 정보를 모두 가지고 있다. 

단방향 연결 리스트
각 원소가 다음 원소를 가리키는 포인터만 가지고 있다.

• 노드들이 흩어져 있기 때문에 특정 위치의 값을 찾는 것은 쉽지 않다.
• 반면 순서를 유지하며 노드를 추가하거나 삭제하는 것은 간단하다.
  • 다른 노드들은 유지한 채, 삽입 또는 삭제할 노드와 이전과 이후 포인터만 변경한다.

 

ref

• 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략