📖 7장 Keywords
- 데이터 구조
배열, 문자열, 연결리스트, 트리 - 가비지 컬렉션
참조 지역성: 필요한 데이터를 서로 가까이 유지하라
기본 데이터 타입
C언어의 포인터는 메모리 주소로 해석된다.
일부 언어는 레퍼런스라는 더 추상적인 개념을 사용한다.
자바는 포인터가 없는 언어이다.
배열
각각의 인덱스가 있는 요소를 갖는다.
상대 주소 지정: 0번째 요소의 주소인 기저주소로부터 얼마나 멀리 떨어져 있는지를 나타내는 offset으로 지정하는 것
비트맵
: 비트의 배열
비트맵에서는 비트 설정하기, 비트 지우기, 비트가 1인지 검사하기, 비트가 0인지 검사하기 등의 기본 연산을 수행할 수 있다.
특정 비트가 들어있는 바이트를 찾고, 자원이 사용 가능하거나 사용 중인지 여부를 표현할 때도 용이하다.
문자열
: 여러 문자로 이루어진 시퀀스
문자열을 연산할 때에는 그 길이를 알아야 한다.
문자열 안에 길이를 저장하여 길이에 접근할 수 있다.
C언어는 문자열을 위한 전용 데이터 타입을 제공하지 않는다.
1차원 바이트 배열을 사용하는 '문자 배열'이다. 이로 인해 C에서 1바이트를 나타내는 데이터 이름이 char이 됐다.
C언어에서 문자열은 길이를 저장하지 않는다.
대신 문자 배열에 들어 있는 문자열 데이터의 끝에 바이트를 하나 추가하고, 문자열의 끝을 표시하는 문자로 NUL을 넣는다.
=> 아스키 NUL문자 (0)을 문자열 터미네이터로 사용한다.
문자열 길이가 6이면, 문자열 터미네이터 1바이트를 포함하여 실제로는 7바이트를 사용하는 것이다.
주어진 값이 0인지 검사하는 명령어를 통해 NUL은 좋은 터미네이터 문자로 사용될 수 있다.
(문자열 중간에 NUL을 넣지 못함에 따라 장단점 존재)
복합 데이터 타입
: structure
프로그램의 synctatic sugar 즉 편의 문법.
사용자가 원하는 대로 구조가 복잡한 데이터 타입을 만들어서 프로그래밍 언어가 기본 제공하는 데이터 타입처럼 사용할 수 있다.
단일 연결 리스트
배열과 비슷하지만 다르다.
배열의 요소는 메모리에서 연속적으로 위치하지만 리스트 노드는 메모리에서 아무 위치나 가질 수 있다.
리스트에서 맨 앞은 head, 마지막은 tail이라고 부른다.
노드를 추가할 때에는 head 앞에 추가한다.
노드를 삭제할 때에는 삭제할 노드의 바로 앞 노드의 next 포인터가 삭제할 노드의 next 포인터가 가리키는 노드를 가리키게 해야 한다.
즉, A의 next 포인터가 B를 가리키고,
B의 next 포인터가 C를 가리키는데, B를 삭제하려면,
A의 next 포인터가 B가 아닌 C를 가리키게 해야한다.
동적 메모리 할당
배열 등의 변수가 사용하는 메모리는 정적이다.
리스트 노드는 동적이다. 동적인 대상에 사용할 메모리는 heap에서 얻는다.
연결 리스트에 추가된 요소는 동적으로 메모리가 할당된다.
문자열이 들어있는 연결 리스트는 노드와 문자열 각각에 메모리를 할당해야 한다.
이 경우에 노드를 할당한 뒤에 문자열을 할당하는 대신에, 노드와 문자열을 동시에 할당하는 것이 좋다.
둘의 크기를 합하고, 메모리 경계를 나타내는 패딩을 추가한 크기의 공간을 할당하여 메모리를 효율적으로 사용한다.
가비지 컬렉션
동적 메모리를 명시적으로 관리하면서 잘못된 포인터를 사용하면 프로그램이 중단된다.
포인터 사용 문제를 해결하는 것에서 가비지 컬렉션이 출발했다.
프로그래밍 언어의 런타임 환경이 변수 사용을 추적해서 더 이상 사용하지 않는 메모리를 자동으로 해제해준다.
자동 해제를 구현하는 방법은 다양하다.
자바, 자바스크립트는 포인터가 없지만 동적 메모리 할당을 지원한다.
LISP를 위해 발명된 가비지 컬렉션을 구현한다.
불필요한 참조는 메모리 재활용을 방해한다. -> 프로그램이 느려진다.
이중 연결 리스트
앞서 말한 단일 연결 리스트의 노드 삭제는 복잡한 과정을 거치기 때문에 느리다.
경우에 따라 오랫동안 리스트를 순회해야 할 수도 있다.
이중 연결 리스트는 노드에 이전/다음 노드에 대한 포인터가 들어있는 리스트로, 단일 연결 리스트의 문제를 해결한다.
수정/삭제할 노드를 찾기 위해 앞에서부터 방문하지 않아도 되고,
리스트 전체를 방문하지 않아도 원하는 위치에 노드를 추가하거나 삭제할 수 있다.
계층적인 데이터 구조
선형성은 데이터 저장에 유리할 수 있고, 계층성은 데이터를 효율적으로 가져오기에 적합한 특성이다.
선형적 데이터 구조는 리스트의 길이가 n이라면 최대 n번 노드를 순회해야 한다.
계층적 데이터 구조는 최대 2개의 다른 노드와 연결될 수 있는 이진 트리 등이 있다.
이진 트리의 노드 삽입 알고리즘은 간접 주소 지정을 한다는 점에서 단일 연결 리스트의 삭제와 비슷하다.
부모 노드보다 작은 수는 왼쪽 자식 노드, 큰 수는 오른쪽 자식 노드가 된다.
이로 인해 최악의 경우에도 이진 트리의 높이 만큼만 노드를 탐색하면 되므로 연결 리스트보다 성능이 좋다.
트리의 노드 구성은 노드 삽입 순서에 따라 달라진다.
균형잡히지 않은 트리의 경우 트리 균형을 회복하는 알고리즘을 적용하여 트리 탐색의 시간복잡도를 낮출 수 있다.
