한 권으로 읽는 컴퓨터 구조와 프로그래밍

7장. 데이터 구조와 처리 - 어떻게 해야 프로그램에서 데이터를 잘 구성하고 처리할까

데이터 구조 : 데이터를 조직화하는 표준적인 방법.

→ 데이터 구조 중 상당수는 여러 유형의 메모리를 더 효율적으로 사용하기 위해 존재

 

참조 지역성 = 필요한 데이터를 (메모리에서) 서로 근처에 유지하라. 금방 사용할 데이터라면 더 가까운 곳에 저장하라!

 

기본 데이터 타입

프로그래밍 언어는 다양한 기본 데이터 타입(primitive data type) 제공

- 크기(비트 수) 와 해석(부호가 있는지 없는지, 부동소수점 수인지, 문자인지, 포인터인지, 불리언인지)이라는 두 측면 존재

 

• 포인터
  • 컴퓨터 아키텍처에 따라 결정되는 크기의 부호가 없는 정수
  • 정숫값이 아니라, 메모리 주소로 해석됨 - 원하는 값이 있는 위치를 포인터로 알 수 있음
  • 일부 언어는 잘못된 포인터 사용으로 인한 오류를 막기 위해 참조(reference)라는 더 추상적인 개념을 구현

 

배열

앞에서 본 데이터 구조는 ... 이를 집처럼 생각할 수 있다. ... 배열은 아파트와 같다. 아파트 한 동에는 주소가 있고, 한 아파트 동 안의 각 집에는 번호가 있다. 프로그래머는 호수를 인덱스라고 부르고, 각각의 집을 원소 라고 부른다.

 

비트맵

원하는 데이터를 표시하기에 기본 데이터가 너무 클 때 - 비트의 배열인 비트맵 사용 O

비트맵 기본 연산 : 비트 설정(set, 1로 만들기), 지우기(clear, 0으로 만들기), 1인지 검사하기, 0인지 검사하기

 

문자열

여러 문자로 이뤄진 시퀀스 - 배열과 마찬가지로 문자열 연산 시에도 그 길이를 알아야 함

→ 문자열 안에 길이 저장 / 문자열 터미네이터

 

복합 데이터 타입

현대적인 대부분의 언어는 원하는 대로 데이터 타입 만들 수 있는 방법 제공(=구조체 structure)

구조체 스위트 안에 있는 여러 방을 - 구조체의 멤버member라고 함

 

단일 연결 리스트

연결 리스트 - 목록에 들어갈 원소 개수를 모르는 경우 배열보다 더 잘 작동

 

동적 메모리 할당

힙 영역 → 정적으로 할당된 데이터 영역 다음에 프로그램 런타임 라이브러리가 설정해 주는 영역

- 동적인 대상(필요에 따라 생기기도 하고, 사라지기도 하는)에 사용할 메모리를 힙에서 얻음

가비지 컬렉션

포인터를 사용해 존재하지 않는 메모리에 접근하거나 프로세서의 메모리 경계에 맞지 않는 주소 접근 시 - 예외 발생 및 프로그램 중단

Java나 Javascript 같은 언어는 포인터가 없지만, 직접 malloc이나 free하지 않으면서도 동적 메모리 할당 지원 → 가비지 컬렉션을 구현!

 

Java 같은 언어를 포인터 대신 참조를 사용!

→ 참조는 포인터를 추상화해서 거의 비슷한 기능을 제공하지만, 실제 메모리 주소를 노출하지는 X

 

new 연산자 : 데이터 요소를 만들어내면서 이 요소가 사용할 메모리도 할당

데이터 요소 삭제 대응 연산자는 없지만, 언어의 런타임 환경이 변수 사용을 추적해서 더 이상 사용하지 않는 메모리를 자동으로 해제!

 

이중 연결 리스트

노드에 다음 원소에 대한 포인터뿐만 아니라, 이전 원소에 대한 포인터도 들어 있는 리스트

 

계층적인 데이터 구조

연결 리스트의 노드 연결 위해 포인터를 사용 - 노드에 들어갈 수 있는 포인터 수에는 제한이 없기 때문에, 메모리 공간이 허용하는 한 원하는 대로 데이터 조직 가능! (ex 2진 트리)

 

데이터베이스

데이터베이스 : 정해진 방식으로 조직화된 데이터 모음

데이터베이스 관리 시스템(DBMS) : 데이터베이스에 정보를 저장하고 읽어올 수 있게 해주는 프로그램

 

B트리라는 데이터 구조를 활용한 시스템 - B 트리 : 균형 트리이지만 2진 트리는 아님

→ 균형 2진 트리보다는 공간을 덜 효율적으로 사용하지만 성능이 더 낫고, 특히 디스크에 데이터를 저장할 때 더 성능이 좋음