[데이터 구조] 8차시 노드와 포인터 | C언어 포인터

1. 노드와 포인터

1) 배열의 순서 리스트 표현 리뷰

- Orderd list(순서 리스트)에 있어서 임의의 위치에 대한 삽입, 삭제 비용이 크다.

[bat, cat, nature, orphan, test] -> 이들은 물리적 메모리 공간에 연속적으로 write되는 특성을 가진다!

"Fast but inconvenient!!"

 

- 순서 리스트 L의 순차 표현과 원소 삽입

 

 

- 순서 리스트 L의 원소 삭제

 

- 배열로 순서 리스트를 표현할 때 장점

1️⃣ 표현이 간단함

2️⃣ 빠른 임의 접근(Immediate Random Access): 인덱스는 직접 메모리 주소로 변환할 수 있기 때문에 원소 접근이 빨라짐

 

- 배열로 순서 리스트를 표현할 때 단점

1️⃣ ! 순차적으로만 ! 표현할 수 있음

2️⃣ 어떤 작업은 자료 이동 때문에 시간이 많이 걸림

3️⃣ 자료의 크기가 미리 정의되어야 함(수행 중, 배열의 오버플로우나 과도한 메모리 할당 발생 가능)

4️⃣ 메모리 내 저장 공간 전체가 한 번에 할당되고, 한 번에 회수됨

 

- 순차 표현의 단점을 해결할 방법 -> pointer를 사용하여 linked list를 구현하자!

 

 

 

2) 노드와 연결 표현

(1) 연결 표현 or 비순차 표현(non-sequential representation)

- 원소의 물리적 순서(저장 위치)가 리스트의 논리적 순서(링크 순서)와 일치할 필요가 없음

- 원소를 저장할 때 이 원소의 다음 원소에 대한 주소도 함께 저장해야 함

- 노드: <원소, 주소> 쌍의 구조

 

(2) 노드(node): <원소, 주소> 쌍

• 원소: 데이터(data) 필드, 즉 노드가 가진 데이터(값)를 저장하는 필드
• 주소: 링크(link) 필드, (포인터) 값을 저장, 이 주소는 다음 노드 혹은 상황에 따라 전 노드의 주소임

 

 

 

3) 노드 구조

 

* 포인터 변수에는 주소가 있음. 그 주소를 따라가면 integer와 같은 자료형이 나옴. 이 integer의 크기만큼만 할당 받을 수 있음.

 

 

* 배열 이름 = 포인터 변수

 

 

 

4) 연결 리스트 표현

(1) 특징

1️⃣ Linked list 표현 내의 모든 element들을 "node"라 부름

2️⃣ 각 "node"는 "다음 node"에 대한, 메모리 내 위치 정보(= Memory Address, Pointer)를 갖고 있음.

(단순 address와 포인터는 다르다.)

 

 

(2) 장점

1️⃣ Element들이 순서대로 메모리에 저장되지 않고, 임의의 위치에 편리하게 저장됨.

• Element들의 순서와 메모리 저장 위치는 무관함
• 즉, Element가 임의의 주소(예: 0x7800, 0x9104 ... )에 Random 저장됨

2️⃣ 임의의 위치에 노드를 삽입하거나, 삭제하는 비용이 감소함

• 배열처럼 원소 삽입 삭제 시 밀고 당기지 않음

 

(3) 단점

1️⃣ Pointer를 잘 사용해야 하기 때문에 운용이 복잡함

2️⃣ 다음 노드의 주소를 저장할, "Link"를 추가로 정의해야 해서 Memory 소모됨

3️⃣ 배열 같은 순차표현에 비해 처리 속도가 상대적으로 느림

 

 

 

 

(4) 연결 리스트 표현

1️⃣ 링크에는 실제로 화살표 대신 주소 값이 들어가 있음

 

 

2️⃣ 연결 리스트의 마지막 노드의 링크 값으로 null을 저장

- null: 어떤 주소 값도 가지고 있지 않다는 것을 나타내는 특별한 값

 

 

3️⃣ 연결 리스트 전체는 포인터 변수 L로 나타냄, 포인터 변수 L에는 리스트 첫 번째 노드의 주소(1000번지)가 저장됨

- 공백 리스트(empty list)의 경우 L의 값은 null이 됨

- 이렇게 null 값을 가진 포인터를 널 포인터(null pointer)라 함

- L은 리스트의 이름이 됨

 

 

4️⃣ 노드의 필드 선택은 점 연산자(. : dot operator)를 이용

 

5️⃣ 포인터 변수에 대한 연산은 제한되어 있음

 

2. C언어에서의 포인터

1) C언어에서의 포인터

(1) 포인터

• 다른 어떤 변수(variable)의 주소(address)를 그의 값으로 저장하는 변수
• C 언어에서는 모든 변수가 주소를 가지고 있기 때문에, 모든 타입에 대해서 포인터 타입(type)이 존재한다.

 

(2) 포인터 선언

• 데이터 타입 이름 뒤나 변수 이름(식별자) 앞에 *를 붙임

 

(3) 포인터의 초기화

• 포인터를 선언만 하고, 초기화하지 않으면 값은 미정(undefined)이 됨
• 이 포인터를 초기화하기 위해서는, 포인터 변수에 주소를 지정해야 함
• 변수의 주소를 구하고자 할 때에는, 주소 연산자 '&'를 해당 변수 앞에 붙이면 구할 수 있음

 

(4) 값 참조

• 포인터가 지시하는 주소의 값(내용)을 참조하기 위해서는 포인터 역참조(de-reference)를 해야 함
• 즉, 포인터 pc에 저장되어 있는 주소를 참조해 그 주소를 따라 가서 거기에 저장되어 있는 내용(값)을 검색
• 이 역 참조는 포인터 변수 앞에 *를 붙여 표현함

 

(5) 값의 변경

 

 

 

 

2) 배열에 대한 포인터

(1) 배열에 대한 포인터

• 배열 원소의 타입에 일치하는 포인터 변수를 선언하여 사용

 

 

(2) 문자 배열의 처음 두 원소에 값을 지정하는 방법

• 배열을 이용하는 방법
  letters[0] = 'a';
  letters[1] = 'b'
  
  
• 포인터를 이용하는 방법
  - 포인터 pc가 배열 letters[]의 시작을 지시하게끔 초기화
  pc = &letters[0]; 또는 pc = letters;
  pc = &letters; (X)
  
  - 배열에 값을 지정
  *pc = 'a'; *(pc+1) = 'b';
  또는 *(pc++)='a'; *(pc++)='b'; // ++에서, char은 1byte이므로 1byte씩 이동. 만약 int였다면 ++ 한 번에 4byte 이동함
  
  

 

(3) 포인터에 대한 ++ 연산자

• 포인터는 현재의 원소 다음에 있는 원소를 가리키게 됨
  ➡️ 포인터 값이 증가되면 배열의 다음 원소를 지시하게 됨
  
  
• 포인터 pc가 배열 letters[]의 첫 번째 원소인 letters[0]을 가리키고 있으면 pc++는 pc가 배열 letters[]의 두 번째 원소, letters[1]을 가리키도록 이동시킴
  ➡️ 이 예에서는 포인터가 char 타입이기 때문에 포인터 값이 증가되면 포인터는 다음 바이트 즉, 다음 문자를 가리키게 됨
  
  

 

(4) 포인터 배열

• C에서는 어떤 타입의 변수 배열도 정의 가능
• 포인터도 다른 변수의 주소를 저장하는 변수이기 때문에 포인터 배열(array of pointers)을 정의할 수 있음
• 이 경우에 배열의 각 원소는 포인터가 됨

 

 

 

(5) struct 배열

struct frequency {
    char letter;
    int count;
};

struct frequency sa[10], *ps; /*struct 배열과 포인터*/
ps = sa; /*ps에 배열의 시작 주소, sa[0]를 지정*/

ps -> letter = 'a';
ps -> count = 0; /*첫 번째 원소의 문자와 정수*/
ps++; /*ps가 sa[1]을 가리키도록 증가. 5byte 점프*/
ps-> letter='b'; /*두 번째 원소의 문자*/

 

 

 

(6) 자체 참조 구조(self-referential structure)

- struct의 멤버는 같은 타입의 또 다른 struct를 지시하는 포인터도 될 수 있음

struct char_list_node {
	char letter;
	struct char_list_node *next;
};

struct char_list_node *p;

 

• struct 타입의 char_list_node를 선언하는 동시에 p를 struct char_list_node 타입에 대한 포인터로 선언
• char_list_node 타입의 노드로 구성된 연결 리스트를 형성할 수 있게 하고 포인터 p는 이 리스트의 노드를 지시할 수 있게 함
• "p = p -> next"와 같이, 포인터를 순회시키는 문장을 사용함으로, 이 포인터 p가 가리키는 노드에 연결된, 다음 노드 접근

 

 

(7) typedef 키워드

- 리스트 처리를 위해 노드와 포인터를 정의할 때 typedef를 이용하면 더욱 간결해짐

typedef struct char_list_node *list_pointer;
struct char_list_node{
	char letter;
	list_pointer next;
};

list_pointer p = NULL;

•  포인터 타입 list_pointer는 아직 정의되지 않은 char_list_node라는 struct 타입을 이용하여 정의
• 포인터 p는 NULL 값으로 초기화