연결리스트 개념

연결리스트 추상 자료형

void ListInit(List *plist)

• 초기화할 리스트의 주소 값을 인자로 전달 해야한다.
• 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List *plist, LData data)

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

int LFirst(List *plist)

• 첫 번째 데이터가 pdata가 가르키는 메모리에 저장된다.
• 데이터의 참조를 위한 초기화가 진행된다.
• 참조 성공 시 1, 실패시 0을 반환한다.

int LNext(List *plist)

• 참조된 데이터의 다음 데이터가 pdata가 가르키는 메모리에 저장된다.
• 순차적인 참조를 위해서 반복 호출이 가능하다.
• 참조를 새로 시작하려면 먼저 LData 함수를 호출해야 한다.
• 참조 성공시 1, 실패시 0을 반환한다.

LData LRemove(List *plist)

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

int LCount(List *plist)

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

연결리스트를 활용하여 다양한 자료구조를 구현할 수 있기에 다음 단계를 위한 적절한 이해가 필요하다!!!.

typedef struct _node
{
    LData data;
    struct _node *next;
} Node;

여기서

struct _node *next; 가 의미하는 바는 현재 노드의 다음 노드의 주솟값을 저장한다는 의미이다. 노드를 바구니 next변수는 다음 노드를 잡고있는 줄 정도로 이해하면 편한다.

 

typedef struct __ArrayList
{
    Node *head;
    Node *cur;
    Node *before;
    int numOfData;
} LinkedList;

head는 가장 앞의 노드를 가르킨다.

void ListInit(List *plist)
{
    plist->head = (Node *)malloc(sizeof(Node));
    plist->head->next = NULL;
    plist->numOfData = 0;
}

위의 코드를 보면 head에 메모리 공간을 할당한다. 왜 더미 노드를 만드냐 하면 더미노드가 없이 코드를 구성할 경우, 첫번째 노드와 두번째 노드의 삭제 시에 차이가 생겨 코드 길이가 늘어나는 상황이 생기기 때문이다. 그렇기에 그러한 문제를 해결 하기 위해 head가 더미 노드를 가르키도록 구성 한다.

int LFirst(List *plist, LData *pdata)
{
    if (plist->head->next == NULL)
        return FALSE;
    plist->before = plist->head;
    plist->cur = plist->head->next;

    *pdata = plist->cur->data;
    return TRUE;
}

int LNext(List *plist, LData *pdata)
{
    if (plist->cur->next == NULL)
        return FALSE;
    plist->before = plist->cur;
    plist->cur = plist->cur->next;
    *pdata = plist->cur->data;
    return TRUE;
}

위의 코드를 보면

before가 cur의 항상 뒤에 놓이는 걸 볼수 있는데, 삭제시 이전 before노드로 cur이 이동 할 수

있게 해주는 역할을한다.

 

LData LRemove(List *plist)
{
    int Ddata = plist->cur->data;
    Node *DNode = plist->cur;

    plist->before->next = plist->cur->next;
    plist->cur = plist->before;
    
    free(DNode);
    (plist->numOfData)--;
    return Ddata;
}

삭제에 대한 코드이다. 삭제시 cur이 다음 노드를 가르키는 것이 아니라 before 즉 이전 노드를 가르키는 이유는 아직 참조되지 않은 노드를 가르키기 때문이다.

삭제 전(LRemove 함수 호출 전)

삭제 후(LRemove 함수 호출 후)

노드 기반 연결 리스트 코드: https://boiling-fowl-6d6.notion.site/LinkedList-fb60710c9c914575b74d06bd619dd4bf

배열 기반 연결 리스트 코드: https://boiling-fowl-6d6.notion.site/ArrayList-25e61bb8962c4f53ad4e228489f9912c