[C언어/자료구조] 포인터 - 연결 리스트 (Linked List) 개념 총 정리 / 배열과 차이점?

오늘은 C언어의 자료 표현 방식 중
'포인터와 연결 리스트(Linked List)' 에 대해 알아보고자 한다.

 

 

 

연결 리스트는 링크(link)를 이용해 표현한 리스트이다.

연결 리스트는 배열의 한계를 극복한 표현 방법 중 하나로 동적 할당이 가능한 것이 특징이다.

그 구조를 더 이해하기 쉽게 데이터 구조를 먼저 살펴보자.

 

 

 

1. 포인터의 개념

• 데이터가 담긴 주솟값을 저장하는 변수
• 다른 어떤 변수의 주소를 그의 값으로 저장한다.
• C 언어에서는 모든 변수가 주소를 가지고 있기 때문에, 모든 변수에 대해서 포인터 유형이 존재한다.

 

 

 

2. 포인터의 특성

 

1) 초기화

- 포인터를 선언만 하고, 초기화하지 않으면 값은 미정(undefined), 포인터 변수에 주소를 지정해야 한다.

- 주소 연산자 ‘&’를 해당하는 변수 앞에 붙이면 주소를 가져온다. 이것을 포인터 변수에 할당.

 

  예1) char c = ‘w’;

         char *p;

         p = &c;

 

- 붙이지 않으면 해당 변수의 값을 가져온다. 

  예2) char c = ‘w’;

         char *p;

         p = c; => p는 문자 'w' 값을 갖게 된다.

 

 

2) 값 참조

- 포인터가 가리키는 값의 참조가 가능하다.

- 즉, 포인터 p에 저장되어 있는 주소를 참조해 그 주소를 따라 가서 거기에 저장되어 있는 내용(값)을 검색 가능

- 포인터 변수 앞에 *를 붙여 표현함 

  예) printf ("c is %c\n", c); 

        printf ("c is %c\n", *p);  => 결과 : w

 

3) 값의 변경

c의 값을 ‘x’로 변경할 때는 (1) c에 바로 ‘x’를 지정하거나, (2) 포인터 p를 이용해서 간접적으로 역 참조를 통해 변경 가능.

예)  c = 'x'; => 직접 지정

     *p = 'x'; => 간접 지정

 

 

 

 

3. 포인터의 선언

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

char c = ‘w’; => 일반 문자형 변수 c
char *p; 혹은 char* p; => 포인터형 변수 p 

 

 

4-1. 포인터의 표현 - 배열

포인터를 이용해서 배열을 표시할 수 있다. C언어에서 문자열을 표현할 때 대부분 배열이 쓰인다.

• 배열명[요소] 표현법

      - 배열 A의 i번지 주소 : A+i

      - 배열 A의 i번지 값 : *(A+i) = A[i]

 

 

 

4-2. 포인터의 표현 - 연결 리스트

 

1) 특징

• 연결 리스트 내의 모든 원소를 '노드(Node)' 라고 한다.
• 원소의 물리적 순서가 리스트의 논리적 순서와 일치할 필요가 없다. (배열과 차이점)
• 원소를 저장할 때 다음 원소에 대한 주소도 함께 저장해야 한다.
  각 노드는 다음 노드에 대한 메모리 내 위치 정보 (= Memory Address, Pointer)를 갖고 있다.
• 노드(Node) : <원소, 주소> 쌍의 구조 / 데이타(data) 필드와 링크(link) 필드로 구성됨

       - 데이터(data) 필드 : 리스트의 원소, 즉 데이터 값을 저장

       - 링크(link) 필드 : 노드의 주소 값을 저장(포인터)

 

2) 장단점

• 포인터의 개념을 이용한 연결 리스트 장단점

[장점] -원소가 랜덤한 주소에 편리하게 저장된다. (순서의 강박X)
          -임의의 위치에 노드를 삽입/삭제하는 비용이 감소한다. (배열처럼 원소 삽입/삭제 시 필수적인 이동이 없기 때문)

          

[단점] -포인터의 개념을 잘 알고 사용해야하므로 사용이 배열보다 어려움

          -다음 노드의 주소를 저장할, 링크 필드를 추가로 정의해야 하므로 Memory 가 소모된다.

 

 

 

 

---

 

 

C언어에서의 포인터와 링크 리스트(연결 리스트)의 개념 및 간단한 예제를 알아보았다.

특히 연결 리스트는 어느 언어에서나 표현이 가능한 자료 구조 중 하나이니

잘 알아두는 것이 좋다.