한빛미디어

책 구성은 크게 3단계로 이뤄진다.

1단계: 자료구조, 알고리즘 정의를 설명하고 C언어 기본문법을 복습한다.

2단계: 자료구조 -리스트, 스택, 큐, 트리

3단계: 알고리즘 -정렬, 탐색, 우선순위 큐와 힙, 해시 테이블, 그래프, 문자열 탐색

예전에 유튜브에서 봤는데 C로 자료구조를 공부하면서 자료구조마다 속도가 어떻게 달라지는지를 인지하는 게 좋다고 한다. 

자료구조를 이해하는데 C의 구조체와 포인터를 사용하면서 이해해보자.

그리고 그 단계가 지나면 알고리즘에 자료구조를 활용한다. 이때는 C++이나 자바를 사용한다.

자바의 경우 객체지향이 있다. 알고리즘을 개선해 효율성을 높이는 경험을 쌓는다. 

그 다음에 응용분야로 넘어가면 된다. 

챕터 2: 자료구조

1. 리스트

-append, insert, remove, getat(특정노드 반환)

-배열과의 차이 : 배열은 생성시점에 배열의 크기 지정 필수, 생성 후에는 크기 변경 불가

but 리스트는 유연하게 크기를 바꿀 수 있음

-링크드 리스트 : 노드를 연결해서 만든다. 

데이터 + 다음 노드에 대한 포인터로 이뤄짐

헤드(첫 번째 노드), 테일(마지막 노드)

-노드 생성에 자동메모리가 적합하지 않음(자동메모리상에 생성된 지역변수가 return문이 실행되면 제거가 되어 해당 변수의 메모리를 가리키는 포인터는 오류가 나게 됨)

-노드 생성에는 자유저장소 사용 : 메모리 할당 malloc() 함수 사용

-sizeof(Node) : 해당 Node리스트의 길이

-sizeof(*Node) : 포인터가 Node리스트의 0번째 주소를 가리키기 때문에 1이 나옴

-링크드 리스트의 단점 : 다음 노드를 가리키는 포인터로 추가 메모리가 필요, 특정 위치에 있는 노드 찾는 비용이 크다.

-링크드 리스트의 장점 : 레코드의 추가, 삽입, 삭제가 잦지만 조회가 드문 작업에서 유리함

예) DB에서 조회하던 레코드를 순차적으로 다룰 때

2. 스택

-입출력은 스택의 꼭대기에서만 이루어짐

-후입선출

-자동메모리도 스택임(지역 변수는 스택에 할당된다)

-대부분의 네트워크 프로토콜이 스택임

-이미지 편집 프로그램의 되돌리기도 스택

-구현방법 

1) 배열 : 용량을 동적으로 변경시 비용이 크지만 구현이 간단함

2) 링크드 리스트 : 스택 용량에 제한이 없음

 "한빛미디어 <나는 리뷰어다> 활동을 위해서 책을 제공받아 작성된 서평입니다."