C++로 쉽게 풀어쓴 자료구조/ 포인터와 연결 리스트

포인터(Pointer)

포인터의 개념

컴퓨터에게 CPU와 Memory는 핵심 요소이고, 모든 메모리는 주소를 갖는다. 포인터는 그 메모리의 주소를 가리키는 변수를 의미한다. 보통 그 주소에는 다른 변수가 저장되어 있는데, 포인터를 이용하면 해당 데이터에 접근할 수 있다.

보통 컴퓨터의 메모리는 바이트 단위로 구성되어 있고 각 바이트마다 순차적으로 주소가 매겨져 있다.

char ch = 'a'; // 1. 문자형 변수 ch 선언 및 초기화
char* p; // 2. 포인터 변수 p 선언
p = &ch; // 3. 포인터 변수 값 저장
*p = 'b'; // 4. ch = 'b'; 와 동일. p가 가리키는 곳의 내용을 'b'로 교체
char** pp; // 5. 이중 포인터 변수 pp를 선언
pp = &p; // 6. p의 주소를 pp에 복사

  1. 이 문장은 char형 변수 ch를 선언하고 초기화 한다. 즉, 메모리에서 char 형을 저장할 수 있는 크기의 공간을 찾아 ch란 이름을 부여하고, 그 공간에 ‘a’를 복사한다. 모든 메모리는 주소를 가지므로 변수 ch도 주소가 있는데, 아래 그림의 예에서는 0x1236번지가 할당되었다. 모든 변수(또는 객체)는 반드시 메모리를 차지하며 주소를 갖지만 상수는 공간을 차지하지도 않고 따라서 주소도 없다.
  2. char* p; 문장은 새로운 포인터 변수 p를 선언한다. 포인터 역시 변수이기 때문에 메모리를 차지하고 주소를 갖는다. 아래 그림의 예에서는 0x5678번지가 이 변수를 위해 할당되었다. 자료형이 char* 이므로 p는 char 변수가 저장되어 있는 공간의 주소를 저장하기 위해 사용될 것이다. 그렇다면 포인터 변수의 크기는 어떻게 될까? 일단은 단순히 4바이트라고 생각하자. 사실 최근에 개인용 컴퓨터의 메모리가 4G바이트(232 바이트)를 넘어서면서 64비트 운영체제를 사용하는 경우가 많다. 만약 64비트 주소체계를 사용한다면 포인터 변수의 크기는 8바이트가 된다.
  3. p = &ch; 문장은 ch의 주소를 포인터 변수 p에 저장하는 문장이다. 변수의 주소는 &연산자를 이용하여 얻는다. 즉 &ch 연산의 결과는 주소(변수 ch가 있는 메모리의 주소)이며, 자료형은 ch가 char형이므로 &ch는 char*가 된다. 아래 그림에서는 &ch의 주소가 0x1236번지이므로 p에는 이 주소가 복사된다. 결국 포인터 변수 p에 변수 ch의 주소가 저장되어 있으며, 이것을 보통 ‘p가 변수 ch를 가리킨다’고 한다.
  4. 포인터 변수가 가리키는 메모리의 내용을 추출하거나 변경하려면 *연산자를 이용한다. 앞의 문장들에 이어 *p = ‘b’; 라는 문장을 실행 시키면 변수 ch의 값이 바뀌게 된다.
  5. char** pp; 문장은 이중 포인터 변수 pp를 선언한다. pp도 변수이므로 메모리 공간을 차지하고 주소를 갖는다. pp의 크기는 p와 동일한데 이는 하나의 컴퓨터에서 주소체계는 동일하며 주소가 몇 번지이든 주소를 저장하는데 필요한 공간은 동일하기 때문이다.
  6. pp = &p; 문장은 변수 p의 주소를 이중 포인터 변수 pp에 복사한다. 3에서 설명한 바와 같이 &p는 변수 p의 주소를 추출한다. 그렇다면 &p의 자료형은 무엇일까? 답은 char** 이다. p의 자료형이 char* 이므로 &p는 char* 형 변수가 들어 있는 메모리의 주소이므로 char**가 된다. 결국 &p의 자료형은 변수 pp의 자료형과 일치하며 &p의 연산 결과를 pp에 복사할 수 있다. 이 문장으로 *pp와 p는 전적으로 동일해졌다.

포인터 변수를 선언할 때 *는 어느 쪽에 붙여도 상관 없지만, 의미적으로는 자료형 뒤에 붙이는 것이 좋다. 다만 한 문장에서 여러 포인터 변수를 선언하고자 할 때는 변수 앞에 *를 붙여야 한다.

// 아래 2개는 동일하다.
char* p;
char *p;

char* p, q, r; // p는 char* 변수가 되지만, q, r은 char 변수가 된다.
char *p, *q, *r;

포인터는 다음과 같이 여러 가지 자료형의 대상에 대해 선언될 수 있다.

int* pi; // int 변수의 주소를 저장하기 위한 포인터
float* pf; // float 변수의 주소를 저장하기 위한 포인터
char* pc; // char 변수의 주소를 저장하기 위한 포인터
int** pp; // 포인터 변수의 주소를 저장하기 위한 포인터
Test* ps; // Test 객체의 주소를 저장하기 위한 포인터
void (*f)(int); // int를 매개변수로 갖고 반환이 없는 함수의 주소를 저장하기 위한 포인터
void* p; // 임의 자료형의 주소를 저장하기 위한 포인터
pi = (int*)p; // p를 정수 포인터로 변경하여 pi로 대입

void *p는 아무것도 가리키지 않는 포인터를 의미한다. void 포인터는 필요할 때마다 다른 포인터로 바꾸어서 사용한다.

함수와 포인터

포인터는 함수의 매개변수나 반환형으로 사용될 수 있다. 특정한 변수를 가리키는 포인터가 함수의 매개변수로 전달되면 그 포인터를 이용하여 호출된 함수에서 원래의 변수를 변경할 수 있다.

배열과 포인터

함수의 파라미터로 배열이 전달되면 함수 안에서 배열의 내용을 변경할 수 있었다. 그 이유는 배열의 이름이 배열의 첫 번째 항목을 가리키는 포인터처럼 사용되기 때문이다. 아래 그림에서 배열의 이름이 점선으로 그려져 있는 이유는 실제로 컴파일러가 배열의 이름에 공간을 할당하지는 않기 때문이다.대신에 배열의 이름이 있는 곳을 배열의 첫 번째 요소의 주소로 대치한다. 따라서 배열의 이름이 배열의 시작 주소값이기 때문에 이것을 함수의 매개변수로 전달하면 그 함수에서는 배열의 내용을 직접 건드릴 수 있게 된다.

객체와 포인터

포인터로 객체의 멤버에 접근할 때 -> 표기법을 사용하면 편리하다. 아래의 표기법은 모두 동일하다.

s.i == ps->i == (*ps).i

함수의 파라미터로 포인터를 넘기면 참조에 의한 호출(call-by-reference)이 되어 매개변수 전달을 위한 어떤 복사도 발생하지 않는다. 이는 값에 의한 호출(call-by-value)에 비해 성능상 유리하다.

자체 참조 클래스

자체 참조 클래스(self-referential class)는 특별한 클래스로서 멤버 변수들 중에서 동일한 클래스의 객체를 가리키는 포인터가 한 개 이상 존재하는 클래스를 말한다. 미리 일정한 크기를 할당하는 배열과 달리 일반적으로 항목의 개수를 미리 예측할 수 없는 경우에 자체 참조 클래스를 정의하고 동적으로 객체를 생성하여 이들을 포인터로 연결하는 구조에서 흔히 사용된다. 이러한 자체 참조는 리스트나 트리를 구성할 때 노드 클래스의 구조로 많이 사용된다.

struct ListNode {
    char data[10];
    ListNode* link;
}

함수 포인터

포인터는 변수의 주소 뿐만 아니라 함수의 주소를 담을 수도 있다.

void foo(int a) {
    printf("foo: %d\n", a);
}

void main() {
    void (*f)(int); // 함수 포인터 선언
    f = foo; // 함수 포인터에 함수 대입
    f(10); // 함수 포인터를 이용한 함수 실행
    (*f)(10); // 함수 포인터를 이용한 함수 실행 

    // 이 코드에서 다음의 표기는 동일한 의미가 된다 
    // foo(10) == f(10) == (*f)(10)
}

포인터에 대한 연산

포인터에 대한 연산은 보통의 연산과 다른 의미를 지닌다.

int A[5];
int *pi;
pi = &A[2];

위와 같은 코드가 있을 때 pi+1, pi-1은 pi의 다음 혹은 이전 객체를 가리키는 의미가 된다.

포인터 사용시 주의점

포인터는 강력한 개념이지만 프로그램에서 오류를 발생시키는 원인이 되기도 한다. 고로 포인터를 사용할 때는 다음과 같은 점을 주의해야 한다.

  1. 포인터가 어떤 값을 가리키고 있지 않을 때는 Null로 설정하는 것이 좋다.
  2. 초기화가 안 된 포인터 변수가 가리키는 곳에 자료를 저장하면 절대 안 된다.
  3. 포인터 타입 간의 변환 시에는 명시적인 형변환을 사용한다.

동적 메모리 할당

동적 메모리 할당의 개념

프로그램이 컴파일할 때 메모리의 크기가 정해지는 것을 정적 메모리 할당(static memory allocation)이라고 하고, 프로그램이 실행 중에 메모리가 할당되는 것을 동적 메모리 할당(dynamic memory allocation)이라고 한다. 정적 메모리 할당은 프로그램이 알아서 처리해주기 때문에 편하지만 고정되어 있기 때문에 확장성과 효율성이 떨어지고, 동적 메모리 할당은 필요한 만큼 추가로 사용할 수 있기 때문에 확장성과 효율성이 좋지만 프로그래머가 메모리의 생성과 해제를 직접 해줘야 하므로 번거로움이 있다.

거의 모든 운영체제에서 동적 메모리 할당을 지원하는데, C언어에서는 malloc()이나 free() 와 같은 표준 라이브러리 함수를 사용하지만, C++에서는 new와 delete 연산자를 제공하여 더 편리한 메모리 할당 방법을 지원한다.

동적 메모리 할당과 해제를 위한 연산자

new 연산자

new는 동적으로 메모리를 할당하여 주소를 반환하는 연산자로 보통 아래와 같이 사용된다.

data_type *pData = new data_type;
data_type *array = new data_type[size];

위 문장에서 new는 data_type 크기의 메모리 블록을 할당하여 그 블록의 시작 주소(즉, 포인터)를 반환하는 연산자이다. 반환된 주소값은 pData에 복사된다.

배열을 new 할 때 배열의 크기를 지정하면 그 크기(size)만큼 data_type을 저장할 수 있는 연속된 메모리를 찾아 할당하고 그 메모리 블록의 시작 주소를 반환한다. 이 주소는 array 포인터 변수에 저장된다.

만약 메모리 확보가 불가능하면 new는 null을 반환한다.

delete 연산자

delete는 동적으로 할당된 메모리 블록을 시스템에 반납한다.

delete pData;
delete [] array;

pData가 하나의 객체였던 것에 비해 array는 한꺼번에 size개의 객체를 할당하였다. 따라서 해제 시에도 이를 고려해 줘야 하는데, 여러 개의 객체가 한꺼번에 할당된 경우 []를 사용하여 정확한 크기의 메모리 해제가 이루어지도록 해야 한다.

2차원 배열의 동적 할당

new를 사용하면 1차원 배열 형태의 자료를 손쉽게 동적으로 할당 할 수 있다. 하지만 2차원 배열의 형태는 그런식으로 할당할 수 없다.

int **arr2D = new int [cols][rows]; // 잘못된 코드
delete [][] arr2D; // 잘못된 코드

C++을 포함한 대부분의 프로그래밍 언어에서는 –아마 옛날 언어들이 그렇지 않을까? C#에서는 된다– 불행히도 이와 같은 편리한 방법을 제공하지 않는다. 단지 1차원 배열 형태의 동적 할당 및 해제 방법만을 제공한다. 그렇다면 영상 처리나 행렬 등에서 흔히 사용되는 2차원 배열 형태의 자료를 동적으로 할당하려면 어떻게 해야 할까?

또한 우리는 이전에 다차원 배열을 함수의 매개변수로 전달하려면 열의 개수가 정해진 경우에만 가능하다는 문제를 확인한바 있다.

int findMaxPixel(int a[][5], int h, int w); // 2차원 배열의 열이 정해져야만 전달 가능하다.
int findMaxPixel(int** a, int h, int w); // 이런 식으로 작성할 수 있다면 모든 크기의 배열을 처리할 수 있다.

이것은 매우 불편한 일이다. 그런데 이 문제를 해결할 수 있는 방법도 2차원 배열의 동적 할당에 있다.

2차원 배열의 동적 할당

2차원 배열을 동적으로 할당하기 위해서는 1차원 배열을 여러 번 할당하는 과정이 필요하다. rows x cols 크기의 int 행렬 mat를 동적으로 할당하는 코드를 생각해 보자.

  1. int* 형 데이터를 저장할 공간 rows개를 동적으로 할당한다. 이 공간의 주소는 이중 포인터 변수 mat에 저장한다(int **mat;)
  2. 행렬의 i번째 행의 요소를 저장하기 위한 int 형 배열을 동적으로 할당하여 그 주소를 mat[i]에 저장한다. 이때 요소의 개수는 cols개 이다.
  3. 모든 행에 대해 2번 과정을 반복한다.

int** alloc2DInt(int rows, int cols) {
    if (rows <= 0 || cols < = 0) return null;

    int** mat = new int* [rows]; // 포인터 변수를 저장할 배열
    for (int i = 0; i < rows; i++) {
        mat[i] = new int [cols];
    }
    return mat;
}

이때 행렬을 나타내는 것은 mat 변수이고, 이 변수의 자료형은 int**로 이중 포인터 변수이다. 만드는 과정은 조금 복잡해 보이지만, 일단 만들고 나면 사용하는 것은 다음과 같이 정적으로 선언한 2차원 배열과 동일하다.

int x = mat[3][4]; // 3행 4열의 값을 x에 복사

2차원 배열의 동적 해제

할당 과정에서 new 연산자가 여러 번 호출 되었으므로 해제 과정에서도 new 연산자가 사용된 횟수만큼 delete 연산자가 호출되어야 한다. 해제는 할당 과정의 역순으로 다음과 같다.

  1. 각 행에 대해 할당된 메모리를 동적으로 해제한다. 이것은 행렬의 모든 행의 인덱스 i에 대해 delete[] mat[i];를 호출하면 된다.
  2. 이제 포인터를 저장한 배열 mat 메모리를 해제한다. delete [] mat;
void free2DInt(int **mat, int rows, int cols) {
    if (mat != null) {
        for (int i = 0; i < rows; i++) {
            delete [] mat[i];
        }
        delete [] mat;
    }
}

연결 리스트

연결 리스트란?

배열은 구현이 간단하고 빠르다는 장점이 있지만 크기가 고정된다는 단점이 있다. 크기를 동적으로 조절하는 방법으로 연결된 표현(linked representation)을 사용할 수 있다. 연결된 표현은 데이터와 링크로 구성되어 있고 링크가 노드들을 연결하는 역할을 한다. 연결된 표현의 특징은 아래와 같다.

  • 데이터를 한 군데 모아두는 것을 포기한다.
  • 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다.
  • 순서를 유지하기 위해 각각의 데이터는 다음 데이터를 가리키는 줄을 가진다.
  • 첫 데이터에서부터 순서대로 줄을 따라가면 모든 데이터를 방문할 수 있다.

이와 같이 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(linked list)라고 한다. C++에서 데이터 간의 연결은 포인터를 이용하여 구현한다. 배열에 대해 연결 리스트가 갖는 장점은 아래와 같다.

  • 크기가 고정되지 않는다.
  • 중간에 자료를 삽입하는 것이 용이하다.
  • 중간에 자료를 삭제하는 것이 용이하다.
  • 데이터 저장을 위한 메모리를 공간이 필요할 때마다 동적으로 만들 수 있다.

연결 리스트의 구조

노드(node)

연결 리스트는 노드들의 집합이며 이들은 데이터를 저장하고 서로 연결되어 있다. 일반적인 노드는 데이터 필드(data field)와 링크 필드(link field)로 구성되어 있는데, 데이터 필드에는 저장하고 싶은 자료를 저장하고, 링크 필드에는 다른 노드를 가리키는 포인터를 저장한다.

헤드 포인터(head pointer)

연결 리스트는 첫 번째 노드를 알면 링크로 매달려 있는 전체 노드에 모두 접근할 수 있다. 따라서 연결 리스트에서는 첫 번째 노드를 가리키는 포인터가 필요한데, 이것을 헤드 포인터라고 한다. 연결 리스트의 마지막 노드는 더 연결할 노드가 없음을 표현하기 위해 null로 설정한다.

동적 할당과 해제

연결 리스트에서 노드들은 메모리 상의 어떤 곳에나 위치할 수 있다. 즉, 노드들의 주소가 연결 리스트상의 순서와 동일하지 않을 수 있다.

연결 리스트는 배열에 비해 구현이나 사용 방법이 복잡한 단점이 있는데, 오류 없이 구현했다 하더라도 동적 할당과 해제가 빈번하게 일어나는 경우 메모리 관리를 위한 처리 시간이 지나치게 많아져 프로그램이 느려질 수도 있다.

연결 리스트의 종류

연결 리스트의 종류 3가지가 있는데, 한 방향으로만 연결된 단순 연결 리스트(singly linked list), 단순 연결 리스트와 같지만 마지막 노드의 링크가 첫 번째 노드를 가리키는 원형 연결 리스트(circular linked list), 노드가 앞과 뒤 연결을 모두 갖는 이중 연결 리스트(doubly linked list)가 그것이다.

연결 리스트로 구현한 스택

연결 리스트로 구현한 스택의 구조

배열을 이용한 스택과 달리 연결된 스택에서는 각 요소들을 한꺼번에 할당하지 않고 필요할 때마다 하나씩 동적으로 할당한다. 연결된 스택에서는 노드 클래스를 추가로 정의해야 하는데, 스택에 저장할 요소 정보와 함께 다음 노드를 가리키기위한 포인터를 데이터 멤버로 가진다.

배열로 구현된 스택에서 배열의 인덱스를 나타내던 top은 포인터 변수가 되어야 한다. top은 첫 번째 노드를 가리키고, 마지막 노드의 링크 필드는 null이 된다. 연결 리스트로 구현한 스택에서는 top이 헤드 포인터가 되는데 이것이 연결된 스택 클래스의 유일한 데이터 멤버이다.

연결된 스택의 동작

삽입 연산

스택에 A-B-C  노드가 저장된 상태에서 D를 추가하려면 다음과 같이 한다.

  1. 노드 D의 링크 필드가 노드 C를 가리키도록 한다. p->link = top;
  2. 헤드 포인터 top이 노드 D를 가리키도록 한다. top = p;

삭제 연산

스택에 A-B-C 노드가 저장된 상태에서 C를 삭제하려면 다음과 같이 한다.

  1. 임시 포인터 변수 p가 노드 C를 가리키도록 한다. p = top;
  2. 헤드 포인터 top이 B를 가리키도록 한다. top = p->next;
  3. 임시 포인터 변수 p를 반환한다. return p;

연결 리스트로 구현한 큐

연결 리스트로 구현한 큐를 연결된 큐(linked queue)라고 한다. 연결된 큐도 메모리 공간에서 물리적으로 흩어져 있는 노드들로 이루어진다. 연결된 큐에서 front는 가장 먼저 삽입된 노드를, rear는 가장 최근에 삽입된 노들르 가리킨다.

연결된 큐의 연산

삽입 연산

연결된 큐가 공백 상태일 때 새로운 노드가 추가된다면, front와 rear 모두 새로운 노드를 가리키도록 하면 된다.

만일 연결된 큐가 공백 상태가 아니었다면 다음과 같이 한다.

  1. rear가 가리키던 마지막 노드가 새로운 노드 p를 가리키도록 한다. rear->link = p;
  2. rear가 새로운 노드 p를 가리키도록 한다. rear = p;

삭제 연산

큐의 삭제는 연결 리스트의 맨 앞의 노드를 꺼내오면 된다.

  1. front가 가리키는 노드를 임시 포인터 p가 가리키도록 한다. p = front;
  2. front가 다음 노드를 가리키도록 한다. front = p->link;
  3. p를 리턴한다. return p;

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기