Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

단순 연결 리스트의 마지막 노드는 NULL을 가리켰다. 

그런데, 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 '원형 연결 리스트'가 된다.

이러한 특성 때문에 원형 연결 리스트에서는 머리와 꼬리의 구분이 없다고도 이야기한다. 

원형 연결 리스트의 장점

- 단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다.

이 리스트는 변형된 모델로 알려져 있지만, 실제로는 보다 더 일반적인 모델로 인식된다.

원형 연결 리스트에는 더미 노드가 존재하지 않기 때문에, 삭제에 있어서 다음 두 가지 예외적인 상황을 구분해야 한다.

예외적 상황1    : 삭제할 노드를 tail이 가리키는 경우

예외적 상황2    : 삭제할 노드가 리스트에 홀로 남은 경우

헤더파일

헤더파일의 정의파일

메인함수

더미 노드가 추가된 형태는 다음과 같다. 

head -> Dummy -> 데이터1 -> 데이터2 -> 데이터3 -> … -> tail 

더미 노드 두 줄의 코딩으로 많은 양의 코드가 줄었다. 

새 노드를 추가할 때, 리스트의 머리와 꼬리 중 어디에 저장을 할 것인가?

- 두 가지 방법 모두 장단점이 있다.

머리에 추가할 경우

장점:    포인터 변수 tail이 불필요하다.

단점:    저장된 순서를 유지하지 않는다.

꼬리에 추가할 경우

장점:    저장된 순서가 유지된다.

단점:    포인터 변수 tail이 필요하다.

어떠한 방법이 더 좋다고 판단할 성격의 문제는 아니란다.

내가 즐겨보는 책의 저자는 머리에 추가하는 방법을 선호한다고 한다. 그 이유는 다음과 같다.

"포인터 변수 tail을 유지하기 위해서 넣어야 할 부가적인 코드가 번거롭게 느껴질 수 있다. 게다가 리스트 자료구조는 저장된 순서를 유지해야 하는 자료구조가 아니다."

라고 말하고 있다.

그리고 많은 수의 자료구조 서적들도 노드를 머리에 추가하는 방식으로 연결 리스트를 구현한다고 한다. 

나도 머리 부분에 노드를 추가하는 것이 더 괜찮은 것 같다고 생각한다.

위의 과정을 모두 밟지 않으면, 특히 ADT의 정의를 생략하면 구현도 활용도 이상한 형태로 흘러가기 쉽다.

예제

이 예제에서는 배열의 단점을 분명히 보여주고 있다.

"배열은 메모리의 특성이 정적이어서(길이의 변경이 불가능해서) 메모리의 길이를 변경하는 것이 불가능하다."

위 예제를 실행한 후 0 이하의 값을 입력하지 않고 계속해서 자연수만 입력을 하면 할당된 배열의 길이를 넘어서는 문제가 발생한다. 

이렇듯 특성이 정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다. 그래서 등장한 것이 '동적인 메모리의 구성' 이다.

프로그램 실행 중에 필요할 때마다 메모리 공간을 마련하는 유일한 방법은 "malloc 또는 그와 유사한 성격의 함수를 호출하는 메모리의 동적 할당" 이다.

연결 리스트의 기본 원리

"필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다."

동적할당으로 노드를 구성하는 예제)

자료구조는 코드를 통해서 공부하는 과목이 아니다. 코드를 통한 학습 이전에, 그림으로 설명하고 그림으로 이해해야 하는 과목이다.

위의 linked.c의 방식은 적절치 않다. 대표적인 두 가지 이유는 다음과 같다.

1. 연결 리스트의 ADT를 정의하지 않았다.

2. 삽입, 삭제, 조회의 기능이 별도의 함수로 구분되어 있지 않다.

즉, 위의 예제는 연결 리스트와 과련된 코드를 모조리 main 함수에다 집어넣었기 때문에 필요할 때 가져다 쓸 수 있는 형태가 아니다.

배열 기반 리스트의 단점

- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.

- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

배열 기반 리스트의 장점

- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.

위의 장점 및 단점은 '연결 기반 리스트' 를 대상으로 비교한 결과이다.

보통 '리스트'라고 하면 '연결 기반 리스트' 를 떠올리고 혹자는 '배열 기반 리스트' 는 불필요하다고까지 말하는 경우가 있다. 하지만 이는 잘못된 것이다.

배열 기반 리스트도 나름의 장점이 있다. 그리고 그 장점은 연결 기반 리스트에는 없는 장점이다.

"배열 기반 리스트도 각종 자료구조의 구현에 중요한 도구이고, 그 자체로도 훌륭한 자료구조이다."

배열 기반 리스트의 활용(주소 값을 저장)

ArrayList.c

ArrayList.h

리스트를 활용하는 것이라 ArrayList.h, ArrayList.c 를 포함시켜야 한다.

이 중에서 헤더파일인 ArrayList.h의 typedef 선언은 다음과 같이 변경해야 한다.

typedef int LData;        (typedef 선언 변경)     →        typedef NameCard * LData;

그리고 NameCard라는 이름의 인식을 위해서 ArrayList.h에 다음 문장도 포함시켜야 한다.

#include "NameCard.h"

#include <stdio.h>

#include <stdlib.h>

#include "Point.h"

#include "ArrayList.h"

int main(void)

{

    List list;

    Point compPos;

    Point * ppos;

    ListInit(&list);

    ppos = (Point*)malloc(sizeof(Point));

    SetPointPos(ppos, 2, 1);

    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));

    SetPointPos(ppos, 2, 2);

    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));

    SetPointPos(ppos, 3, 1);

    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));

    SetPointPos(ppos, 3, 2);

    LInsert(&list, ppos);

    printf("현재 데이터의 수: %d \n", LCount(&list));

    if(LFirst(&list, &ppos))

    {

        ShowPointPos(ppos);

        while(LNext(&list, &ppos))

            ShowPointPos(ppos);

    }

    puts("");

    compPos.xpos = 2;

    compPos.ypos = 0;

    if(LFirst(&list, &ppos))

    {

        if(PointComp(ppos, &compPos) == 1)

        {

            ppos = LRemove(&list);

            free(ppos);

        }

        while(LNext(&list, &ppos))

        {

            if(PointComp(ppos, &compPos) == 1)

            {

                ppos = LRemove(&list);

                free(ppos);

            }

        }

    }

    printf("남은 데이터의 수: %d \n", LCount(&list));

    if(LFirst(&list, &ppos))

    {

        ShowPointPos(ppos);

        while(LNext(&list, &ppos))

            ShowPointPos(ppos);

    }

    puts("");

    return 0;

}

main함수를 보면 LRemove 함수가 삭제된 데이터를 반환하도록 디자인한 이유를 알 수 있다. 위의 코드에서 리스트에 저장된 데이터는 'Point 구조체 변수의 주소 값' 이다. 이 주소 값은 Point 구조체를 동적으로 할당한 결과이기 때문에, 반드시 free 함수를 통한 메모리의 해제과정을 거쳐야 한다. 

일반적인 리스트는 메모리의 해제까지 책임을 지지 않는다. 

리스트에 저장된 값이 주소 값인 경우, 그리고 그 주소 값이 동적 할당의 결과인 경우를 구분하여 메모리의 해제를 진행하도록 구현하는 것은 무리가 있다.

때문에 LRemove 함수처럼 데이터를 소멸하는 함수는, 소멸된 데이터를 반환하도록 정의해야 한다. 그래서 메모리 소멸의 기회를 줄 수 있어야 한다. 

헤더파일의 정의

어떠한 자료구조이건 간에 '자료구조의 구현' 과 '구현된 자료구조의 활용' 은 완전히 구분되도록 ADT를 정의해야 함을 기억해야 한다.

배열을 이용하는 방법.

리스트에 다양한 종류의 데이터를 저장할 수 있게 하기 위한 typedef 선언이 존재한다.

typedef int LData;                    // 리스트에 int형 데이터의 저장을 위한 선언

typedef ArrayList List;            // List는 배열 기반 리스트이다.

이렇듯 ArrayList에 List라는 이름을 별도로 부여한 것이 당장에는 큰 의미가 없어 보인다. 하지만 ArrayList라는 이름에도 typedef 선언을 해 놓으면, 다음과 같이 List에 다른 이름을 부여하는 것만으로도 사용하는 리스트의 종류를 바꿀 수 있다.

typedef LinkedList List;    // List는 연결 기반 리스트이다.

그래서 main 함수에서도 ArrayList가 아닌 List라는 이름을 이용하여 예제를 작성한 것이다.

함수의 정의

curPosition 변수는 저장된 값을 통해서 LFirst 함수와 LNext 함수가 참조해야 할 배열의 위치를 알려주는 변수이다. 그래서 curPosition은 0이 아닌 -1로 초기화한 것이며, 여기에는 아직 데이터의 차모가 진행되지 않았다는 의미가 담겨있다.

"어떠한 라이브러리를 사용하건 저장된 데이터의 조회를 위한, LFirst 함수의 호출과 같은 별도의 과정은 거치기 마련이다."

리스트라는 자료구조는 구현방법에 따라서 다음과 같이 크게 두 가지로 나뉜다.

- 순차 리스트                        배열을 기반으로 구현된 리스트

- 연결 리스트                        메모리의 동적할당을 기반으로 구현된 리스트

하지만 이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 이 둘의 ADT가 동일하다고 해서 문제 될 것은 없다. 물론 각각의 특성적 차이 때문에 ADT에 차이를 두기도 한다. 

리스트의 ADT 정의를 위해서 리스트 자료구조의 가장 기본적이고도 중요한 특성

1. 리스트 자료구조는 데이터를 나란히 저장한다.

2. 리스트 자료구조는 중복된 데이터의 저장을 막지 않는다.

자료구조 중에서는 중복된 데이터의 저장을 허용하지 않는 경우도 있다. 하지만 리스트는 이를 허용한다. 

즉, 리스트는 수학적으로 중복을 허용하지 않는 '집합' 과는 다르다. 그리고 이것이 리스트 ADT를 정의하는데 있어서 고려해야 할 유일한 요소이다. 

리스트 자료구조의 ADT

void ListInit(List * plist);        //C++의 생성자 역할

- 초기화할 리스트의 주소 값을 인자로 전달.

- 리스트 생성 후 제일 먼저 호루되어야 하는 함수.

void LInsert(List * plist, LData data);

- 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

int LFirst(List * plist, LData * pdata);

- 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다. 

- 데이터의 참조를 위한 초기화가 진행된다.

- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환.

int LNext(List * plist, LData * pdata);

- 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.

- 순차적인 참조를 위해서 반복 호출이 가능하다.

- 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.

- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환.

LData LRemove(List * plist);

- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다. 

- 삭제된 데이터는 반환된다.

- 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

int LCount(List * plist);

- 리스트에 저장되어 있는 데이터의 수를 반환한다.

사실 위의 정보만 가지고는 리스트의 활용방법을 정확히 이해하기는 힘들다 이를 위해서는 헤더파일과 위의 함수들을 호출하는 main함수를 보아야 한다. 

그러나 위의 정보만 가지고도 리스트 자료구조가 제공하는 기능을 어느 정도 예측할 수 있어야 한다.      

모든 자료구조는 내부적으로 다양한 정보를 담게 된다. 그저 데이터만 담는 게 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기기 마련이다. 따라서 이와 관련된 변수들의 초기화가 서너행되어야 하며 이를 담담하는 함수가 ListInit이다.

LFirst 함수를 호출하도록 ADT를 디자인한 이유는 무엇일까?

- 이에 대한 해답은 "LNext 함수를 호출할 때마다 다음에 저장된 데이터를 얻을 수 있다." 라는 사살에서 찾을 수 있다. 

이것이 가능한 이유는  리스트 내에서 '데이터의 참조위치' 를 기록하기 때문이다. 따라서 처음부터 참조를 새롭게 시작하기 위해서는 바로 이 정보를 초기화해야 한다. 그리고 이를 목적으로 LFirst 함수의 호출을 요구하는 것이다.

※ 자료구조를 공부하다보니 파이썬의 자료형들을 더욱 깊이 알게 되는구나!!

파이썬의 자료형 중 리스트를 다룰때마다 대충 이런식으로 되어있구나 하고 생각했었는데,

C 자료구조를 공부하니 이런식의 ADT가 되어있다는 것을 확실히 알았다.