배열 or 리스트(정적 배열, 동적 배열, doubling, 분할 상환 시간 복잡도), 연결리스트(Linked List), 파이썬 리스트(특징, 메모리 구조, 주요 연산 시간 복잡도)

1. Array

• 미리 할당된 공간에 연관된 데이터를 연속적이며 순차적으로 저장하는 자료구조

1) 정적 배열(Static Array)

• 미리 할당된 크기를 가지며 연속적으로 순차적으로 데이터를 저장하는 자료구조
• 특징
  • 고정된 크기를 갖는다
  • 저장 공간을 미리 확보해야 한다
  • 메모리 상에 데이터가 서로 인접한(연속적인) 메모리 위치에 저장된다 → 논리적 저장 순서와 물리적 저장 순서가 같다
  • 시간 복잡도
    • 삽입과 삭제 → 삽입 및 삭제로 인해 데이터들이 한칸 씩 움직여야 하기 때문에 $O(N)$을 갖음
    • 탐색
      • 메모리 시작 주소에 + N 만 하면 되기 때문(랜덤 접근, Random Accesss)에 시간 복잡도 $O(1)$을 갖음
        • Random Access(Direct Access)
          • 데이터 접근 시, 어떤 순서로든, 어느 위치에 있는 데이터라도 동일한 시간 안에 접근할 수 있는 방식
          • 데이터를 순차적으로 접근할 필요 없이, 주소나 인텍스를 통해 바로 접근할 수 있다

 

 

2) 동적 배열(Dynamic Array)

• 선언 이후에도 배열의 크기가 필요에 따라 동적으로 변경되는 배열
• 기존에 할당된 Size를 추가하게 될 경우
  1. Size를 늘린 배열을 새로 선언한다
  2. 기존 배열을 새로 선언한 배열에 옴긴 후
  3. 기존 배열은 메모리에서 삭제(Free) 한다

 

Doubling

• 기존 배열의 용량 초과로 새로운 배열을 선언할 때 기존 배열 크기에서 2배 큰 크기로 Resize하는 기법
  • 배열을 한칸씩 늘리는 건 비효율적이기 때문에 일반적으로 2배 큰 크기로 Resize함
• 크기 조정 문제와 해결책
  • 문제
    • $2^k$에서 $2^{k+1}$로 늘리고 다시 $2^{k+1}$에서 $2^k$로 줄이는 작업이 반복되면 각 삽입/삭제에 대해 선형 시간이 소요되어 비효율적
    • 예를 들어
      • $n=8$ 상태에서 9번째 항목을 삽입하면 테이블 크기를 두 배로 늘려 $m=16$이 됨
      • 이후 9번째 항목을 삭제하면 테이블 크기를 다시 $m=8$로 줄임
      • 이런 삽입과 삭제가 반복되면, 테이블 크기를 조정할 때마다 선형 시간 비용이 발생
  • 해결책
    • 리스트 축소 조건 변경
      • 리스트 크기를 줄이는 조건을 "리스트의 사용량이 1/4 이하일 때"로 설정함
        • 예를 들어, 리스트 크기가 16일 경우, 요소가 4개 이하로 줄어들었을 때만 크기를 8로 축소함
      • 리스트가 다시 커지기 전까지 크기를 줄이지 않으므로, 크기 조정이 지나치게 빈번하게 일어나지 않음
    • 불변 조건 유지
      • 리스트의 크기 m은 항상 현재 항목 개수 n의 $n≤m≤4n$ 범위를 유지하도록 설계함
      • 이 조건을 통해 크기 조정이 적절히 제한되며 공간 효율성을 유지할 수 있음

 

분할 상환 시간복잡도

• 한 번의 연산에 대한 최악의 경우 시간 복잡도가 아니라, 여러 번의 연산에 대해 평균적으로 걸리는 시간 복잡도를 계산하는 방식
• append(추가)할 때 시간이 얼마나 걸릴까?
  1. 크기가 충분할 때: 배열에 여유 공간이 있으면, 데이터는 배열의 끝에 바로 추가되기 때문에 $O(1)$이다.
  2. 크기가 꽉 찼을 때: Doubling하여 새로운 배열에 옴기는 과정의 시간복잡도는 $O(N)$이지만 아주 가끔 발생하는 일이기 때문에, 전체적으로 봤을때 $O(1)$임 → 정확히는 $amortized~O(1)$

 

 

 

2. 연결 리스트(Linked List)

• 데이터 값(Value)와 다음 노드 주소를 가르키는 포인터로 구성된 노드들이 연결되어 있는 자료구조
• 각각의 노드가 다음 노드의 메모리 주소값을 가르킴으로써 논리적으로 연속적이지만, 메모리상으로 비연속적으로 저장됨→ 메모리에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유로운 대신, Next address를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커지게 됨 → 논리적 연속적, 물리적 비연속적
• 삽입과 삭제
  • 노드를 삽입할 위치를 알고 있고 그 위치가 현재 노드라면, 포인터만 수정하면 될 경우 → $O(1)$
  • 삽입할 위치를 찾기 위해 링크드 리스트를 탐색해야 할 경우 → $O(N)$
• 탐색
  • 시간 복잡도 $O(N)$ → 저장된 순서대로 검색해야 하기 때문(순차적 접근, Sequential Access)
• 추가적인 연결리스트
  1. 싱글연결리스트
     • next 포인터 밖에 존재하지 않으며 한 방향으로만 데이터가 연결된 리스트
  2. 이중연결리스트(Doubly Linked List)
     • prev, next 두 개의 포인터가 존재하여 양방향으로 데이터가 연결된 리스트
  3. 원형연결리스트
     • 마지막 노드와 첫번째 노드가 연결된 리스트
     • 싱글연결리스트와 이중연결리스트로 이뤄진 2가지 타입의 원형연결리스트가 있다
• 구현

연결리스트 level 1

 

연결리스트 level 2 (Dummy Head Linked List)

 

연결리스트 level 3 (Doubly Linked List)

 

 

 

 

3. 파이썬 리스트(Python List)

1) 파이썬 리스트의 특징

• 동적 배열
  • 파이썬의 리스트는 동적 배열임
  • 크기가 가변적이며, 필요할 때마다 자동으로 크기를 조절할 수 있음
• 다양한 자료형
  • 파이썬 리스트는 같은 리스트 내에 서로 다른 자료형의 값을 저장할 수 있음
• 슬라이싱 기능
  • 파이썬 리스트는 슬라이싱(slicing) 기능을 제공함
  • 리스트의 특정 부분을 잘라내는 기능으로, 배열과 마찬가지로 리스트에서도 사용할 수 있음

 

 

2) 메모리 구조

• 파이썬에서 리스트는 객체의 주소를 저장하는 방식으로 구현
• 즉, 리스트에 저장된 값들은 실제 값이 아니라, 값이 저장된 객체의 메모리 주소를 가리키고 있음
  • 예를 들어, arr = [1, "a", ("가", "나")]에서 리스트는 1, "a", ("가", "나")라는 객체의 주소를 연속된 메모리 공간에 저장함
  • 이 메모리 주소들은 배열처럼 연속적으로 저장되지만, 각 객체(정수, 문자열, 튜플)의 실제 데이터는 메모리 상의 다른 위치에 있을 수 있음
• 인덱스로 접근 가능: 리스트는 배열처럼 인덱스를 사용하여 각 객체에 접근할 수 있음

 

 

3) 주요 연산 시간 복잡도

연산	시간 복잡도
len(list)	$O(1)$
list[i]	$O(1)$
list[i:j]	$O(k)$
a in list	$O(n)$
list.count(elem)	$O(n)$
list.index(elem)	$O(n)$
list.append(elem)	$O(1)$
list.pop()	$O(1)$
list.pop(0)	$O(n)$
del list[i]	$O(n)$
list.sort()	$O(n \log n)$
min(list), max(list)	$O(n)$
list.reverse()	$O(n)$