배열, 연결리스트 - algorithm[1]

배열

배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능

2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음

3. Cache hit rate가 높음

4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

시간복잡도

• 임의의 위치에 있는 원소를 확인/변경 = O(1)

• 원소를 끝에 추가 = O(1)

• 마지막 원소를 제거 = O(1)

• 임의의 위치에 원소를 추가/임의 위치의 원소 제거 = O(N)
• 추가의 경우 그 뒤의 원소들을 전부 한 칸씩 밀어야 함.
• 삭제의 경우 그 위의 원소들을 한 칸씩 땡겨와야 함.
 

연결 리스트

연결 리스트의 성질

1. k번째 원소를 확인/변경하기 위해 O(K)가 필요함

2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)

3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

연결 리스트의 종류

• 단일 연결 리스트
• 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트

• 이중 연결 리스트
• 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있음
• 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 쓴다

• 원형 연결 리스트
• 단일 연결 리스트 / 이중 연결 리스트 중 무엇을 사용하더라도 상관 없음
 

배열 vs 연결 리스트



• 배열과 연결 리스트는 선형 자료구조
 



 

Insert 함수



 

Erase 함수