[알고리즘] 배열 / 리스트

배열

메모리상의 원소를 연속하게 배치한 자료구조

index를 이용해 참조

 

배열의 성질

1. k번째 원소를 확인 변경 가능 - O(1)
2. 추가적으로 소모되는 메모리의 양이 거의 없음(overhead)
3. Cache hit rate가 높음
4. 메모리상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

배열의 시간 복잡도

O(1)

• 임의의 위치에 있는 원소를 확인 변경
• 원소를 끝에 추가하는 경우
• 마지막 원소 제거

O(N)

• 임의의 위치의 원소를 제거 / 추가

 

리스트

값과 포인터를 묶은 노드 라는것을 포인터로 연결하는 자료구조

값 : 데이터
포인터 : 다음 노드를 가르키는 포인터
노드(Node) : 값 + 포인터

 

리스트의 특징

1. 인덱스가 없음 , header 포인트의 순서대로 접근 -> 접근 속도가 느림
2. 삭제, 삽입 연산 속도가 빠름 ( 포인터만 수정해 주면 됨)
3. 크기 지정 x (데이터가 변하는 것에 사용 적합)
4. 포인터를 저장할 공간이 필요 (구조 복잡)

=> ArrayLst / LinkedList

 

 

배열과 리스트의 시간복잡도

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가 삭제	O(n)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간(overhead)	-	O(N)