[자료구조 4장] - 연결리스트(1)

연결리스트(1)

포인터와 연결리스트

 

순차리스트와 연결리스트

배열로 구현된 순차리스트 구조는 연속적인 순서를 유지해야 하기 때문에 다음과 같은 단점이 있다.

 

1. 리스트 중간에 자료를 삽입, 삭제하기 어렵다.

2. 리스트의 크기나 모양을 바꾸고자 하는 경우 문제가 발생한다.

3. 프로그램 수행 도중 리스트의 크기가 가변적이라면 최대 크기를 산정하여 처음부터 미리 이를 준비해 두어야 하므로 기억장소를 낭비하게 된다.

 

이와 같은 단점을 보완하기 위한 방법으로 자료와 그다음 자료의 위치를 하나의 단위로 저장하여 연결고리 형태로 리스트를 구성하는 연결리스트 구조가 제안되었다.

 

배열과 같은 리스트의 구조는 데이터 크기가 컴파일 시간에 정해진다.

연결리스트는 삽입과 삭제가 자주 일어나고 크기가 가변적인 경우 편리한 자료구조이다.

 

연결리스트를 구성하기 위한 포인터와 자기 참조 구조체, 그리고 연결리스트의 기본 유형인 단순 연결리스트, 원형 연결리스트, 이중 연결리스트에 대해 알아보자.

---

포인터와 자기참조구조체

배열의 이름 : 배열의 첫 번째 주소값

포인터 타입에는 주소연산자(&)와 역참조(간접지시) 연산자(*)가 사용된다.

 

포인터 개념확인 예제

void main()
{
    int *p, q;
    q = 100;
    p = &q;
    printf("%d", *p);
}

위 예제에서 포인터 변수 p와 정수변수 q에 의하여 참조되는 데이터값 *p는 모두 같은 값 100을 갖게 됨을 확인할 수 있다.

포인터 변수 p는 간접적으로 주소 p가 가리키는 값은 int 라는 의미로 int *로 선언되기 때문에 포인터변수 p와 일반변수 q가 함께 선언될 수 있다.

 

void main()
{
    int *p, q;
    float *fp, x;
    p = &q;
    *p = 199;
    fp = &x;
    scanf("%f", fp);
    printf("%d --- %.2f\n", q, x);
}

위 예제에서는 입력으로 실수형 fp값을 받는데 fp는 x의 주소값을 가리키므로 *fp와 x는 같은 입력한 값을 가진다.

 

포인터를 매개변수로 보내는 예제

void main()
{
    int x, y, z;
    printf("세 수를 입력하시오. ");
    scanf("%d %d %d", &x, &y, &z);
    if (x > y) swap(&x, &y);
    if (y > z) swap(&y, &z);
    if (x > y) swap(&x, &y);
    printf("%d **** %d **** %d\n", x, y, z);
}

void swap(int *px, int *py)
{
    int temp;
    temp = *px;
    *px = *py;
    *py = temp;
}

위 예제는 값에 의한 호출(call by value)방식으로 리턴되었을 때 변경된 매개변수의 값을 사용하려면 포인터를 매개변수로 보내야 한다.

함수 수행 후 리턴되었을 때 매개변수 값의 변화를 가지고 있으려면 포인터에 의하여 간접적으로 접근해야 한다.

 

이 밖에 포인터를 활용하는 대표적인 예는 다음과 같이 프로그램 실행시간에 메모리를 할당받는 malloc() 함수의 리턴값을 받아 사용하는 경우이다. 이때 함수 malloc()이 제대로 기억공간을 할당받지 못하면 NULL의 값을 리턴해준다.

void main()
{
    int *ip;
    float *fp;
    ip = (int *) malloc(sizeof(int));
    fp = (float *) malloc(sizeof(float));
    *ip = 2018;
    *fp = 7.123;
    printf("year = %d: point = %.3f\n", *ip, *fp);
    free(ip);
    free(fp);
}

malloc 호출에는 int나 float를 저장하는 데 필요한 기억 장소의 크기를 결정하는 매개변수를 포함한다. malloc 호출의 반환값은 적당한 크기의 메모리 영역에 대한 첫 번쨰 주소를 가리키는 포인터이다.

 

위 예제에서 이 문장을 printf문 바로 다음에 추가한다면 7.123의 값을 저장하고 있는 기억장소에 대한 포인터가 없어진다.

fp = (float *)malloc(sizeof(float));

이렇게 되면 이 기억장소를 접근할 수 있는 방법이 없어진다. 이것을 허상참조라고 한다. 동적할당된 기억 장소에 대한 모든 포인터가 없어지면 프로그램의 입장에서 볼 때 그 기억장소도 없어지게 되는 것이다.

 

연결리스트는 노드들의 집합으로 구성된다.

자기참조구조체 : 구조체의 멤버 안에 자기 자신과 같은 타입의 노드를 가리키는 주소를 가지고 있어야 한다.

 

typedef struct self_ex *self_ex_pointer;
struct self_ex {
    long id;
    char grade;
    int escore;
    self_ex_pointer link;
};

위와 같이 정의되어 있는 경우 각 노드는 id, grade, escore의 3가지 데이터와 자기와 같은 노드구조(struct self_ex)를 가리키는 포인터로 구성되어 있다. 이 포인터는 다음 노드를 가리키며 이를 이용하여 노드들이 서로 연결되어 자료구조를 형성하게 된다.