Data Structure_#3 순차적 자료구조(list)
배열 vs 리스트
**<공통점>**
★가장 기본적인 순차적(sequential) 자료구조★
★데이터를 연속적인 메모리 공간에 저장★
-차이점
배열 리스트
연산 제한적 연산 VS 다양한 연산(append, pop…)
저장 배열의 셀에는 실제 값 저장 VS 리스트의 셀에는 데이터 주소가 저장
(용량 자동 조절)(=동적 배열)
연산
1) 배열
: 인덱스로 배열의 특정위치 값을 상수시간 내에 읽기 쓰기 연산만 제공하는 자료구조
★데이터를 연속적인 메모리 공간에 저장, 저장된 곳의 주소(address, reference)를 통해 빠른 시간에 접근 가능
=>연산: 읽기, 쓰기
Ex) int A[4]={2,4,0,5};
A[2] = A[2] +1
쓰기/ 대입 /읽기 /산술
2) 리스트
Ex) A=[2,4,0,5] -> 각각 따로 메모리 차지함
->★연산 시 따로 객체가 생김(=메모리 낭비가 큼)★
-> 효율을 위해선 compact array type 사용하기
-연산
-
A.append(a): 맨 뒤에 a 삽입 => 평균적으로 O(1)시간
-
A.pop(): 맨 뒤의 값을 지우고 해당 값 리턴 => 평균적으로 O(1)시간
-
A.pop(a): A[a] 제거하고 리턴 => 값이 왼쪽으로 한 칸씩 이동하는 시간 필요
=> 최악인 경우는 A.pop(0)으로 O(n)시간(O(len(A))
-
A.insert(a,b) : A[a]에 b 대입 =>모두 오른쪽으로 이동하므로 A의 크기만큼 시간 필요
=> 최악(+평균)의 경우는 A.pop(0)일 때로 0(n)시간 (O(len(A))
-
A.remove(value): A에서 value 제거 =>최악(+평균) 0(n)시간
-
A.index(value), A.count(value) => 최악인 경우 0(n)시간 (O(len(A))
저장
1) 배열
=> 배열 선언 시 크기 정해야 함
=> 배열 크기를 변경시엔 새로운 배열을 만들기
ex) malloc
B=(int *)malloc(6 * 4) : 4비트인 int형을 6개 할당한 배열
=★★시작주소, 저장 값 종류(바이트 개수), 인덱스로 주소 계산 가능★★
ex) A[2]의 시작 주소 = A[0]의 시작 주소 + 2*4 (index =2, sizeof(int)=4)
2) 리스트
=> ★ 리스트는 용량의 크기를 자동 조절 (동적 배열)★
=> 새로운 메모리를 위해선 동적할당으로 통해 할당해줘야 함
-> append나 insert, pop 에서 메모리가 작거나 너무 크면 새로 리스트 만들어 복사
-append 연산에서 메모리 늘려야하는 상황
=>resize하는 경우 O(n)
