배열, 문자열

배열

메모리 한 덩어리라는 표현 (연속된 데이터 집합)

여러 데이터 (같은 타입)을 연속하여 세워 놓은 자료구조
각 자료의 데이터 타입의 크기를 알기에 해당 데이터 타입의 크기만큼 점프하여 인덱스로 접근 가능

동적 배열?

임의의 크기로 데이터가 늘어나는 list 등의 경우,
내부에서 현재 요소의 개수가 총 용량(Capacity)가 넘는 경우,
새로운 크기의 배열을 생성하고 기존 배열의 데이터를 복사하는 방식을 취한다

배열 요소의 삽입

기본적으로는 맨 뒤 쪽의 요소에 추가하는 경우는 O(1)의 복잡도를 가진다.
(어느 순간에도 뒤에 하나 놓으면 되기에)
다만 그 외의 경우는 삽입 하려는 위치 뒤쪽의 모든 요소를 한 칸씩 밀어야 하므로
O(n)의 복잡도를 가진다.

배열 요소의 삭제

삽입과 비슷하다. 가장 끝에 있는것을 삭제한다면 바로 지울 수 있으나
그 외의 경우는 삭제 후, 나머지 요소를 앞으로 당겨와야 하기에 O(n)의 복잡도를 가진다

배열 요소의 접근

인덱스만 알면 바로 접근이 가능하다 (O(1))

배열 요소의 검색

모든 배열의 요소를 검사해야 하므로 (O(n))

배열과 포인터

배열은 포인터로 참조할 수 있음!
(배열 a가 있다면 a는 배열의 첫번째 요소를 가리키는 포인터변수와 유사함)
다만 배열 변수의 경우는 sizeof() 등의 함수로 배열 전체의 크기를 구할 수 있으며,
기본적으로 해당 배열을 가리키는 것을 바꿀 수 없음
(ex : int a[5] , int b[5] 가 있을 시 , a = b는 오류를 내뱉음)

문자열

일반적으로 문자(char)의 모임이며, ‘자료형’으로 분리되나
기본적인 자료형들과는 꽤나 차이가 있는 타입이다

문자열의 크기

문자열의 크기는 정해져 있지 않다
‘hell’과 ‘hello’ 의 크기가 서로 다르듯!
데이터 크기 정해져 있지 않은 점이 일반적인 자료형과 가장 큰 차이점을 가진다
그렇기에 컴퓨터는 ‘문자’의 ‘배열’로 문자열을 인식한다
C에서는 추가적으로 ‘null 문자 : ‘\0’‘를 통해 문자열의 끝을 인식한다
(‘null 문자 사용 이유’? 일반적으로 ‘배열’은 자기 자신의 크기를 모르기에 해당 문자를 통해 ‘끝’을 알려줌)
(여담으로 다른 언어에서는 추가적으로 ‘길이’를 저장하여 해당 문제를 방지하였음)
(다만 이 방식은 추가적으로 ‘길이’를 저장한다는 단점이 있다)