헤더에 정의되어 있는 함수의 prototype을 보고, 함수를 모두 구현해보자.

1. 헤더 분석하기

#ifndef _LINKEDLIST_
#define _LINKEDLIST_
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct ListNodeType
{
    int data;
    struct ListNodeType* pLink;
} ListNode;
typedef struct LinkedListType
{
    int currentElementCount;	// ���� ����� ������ ����
    ListNode headerNode;		// ��� ���(Header Node)
} LinkedList;
LinkedList* createLinkedList();
int addLLElement(LinkedList* pList, int position, ListNode element);
int removeLLElement(LinkedList* pList, int position);
ListNode* getLLElement(LinkedList* pList, int position);
void clearLinkedList(LinkedList* pList);
int getLinkedListLength(LinkedList* pList);
void deleteLinkedList(LinkedList* pList);
#endif
#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_
#define TRUE		1
#define FALSE		0
#endif

linked list의 구조체는 총 2개로, ListNode와 LinkedList 구조체가 있다.

LinkedList구조체는 int currentElementCount와 ListNode headerNode를 멤버 변수로 가지고 있으며, currentElementCount는 현재 노드의 개수를, headerNode는 data와 pLink를 가지고 있다.

ListNode 구조체는 int data, struct ListNodeType *pLink를 멤버 변수로 가지고 있으며 data는 노드의 데이터 부분, struct ListNodeType *pLink는 다음 노드를 가리키는 주소값을 저장하고 있다.

Linked list 구현에서 headerNode는 삭제되거나 값이 변경되지 않으며, headerNode의 pLink는 다음 0번째 ListNode의 주소값을 가지고 있어 pLink가 0번째 노드를 가리킨다고 한다.

즉, 위의 그림과 같다. 오른쪽 노드가 0번째 노드이다.

2. createLinkedList 함수 구현

LinkedList* createLinkedList()
{
    LinkedList* pList = NULL;
    pList = (LinkedList*)malloc(sizeof(LinkedList));
    if (pList == NULL)//동적 할당 실패
    {
        printf("malloc failure\\n");
        return (NULL);
    }
    memset(pList, 0, sizeof(LinkedList));//LinkedList의 사이즈만큼 0으로 초기화
    return (pList);
}

함수 기능 : createLinkedList함수는 말 그대로 LinkedList를 만드는 함수이다. pList에 LinkedList를 동적 할당하고 주소를 반환하는 함수이다.

pList에 LinkedList의 사이즈(headerNode, currentElementCount의 사이즈를 더한 값)만큼 동적 할당을 한 뒤, 모두 0으로 초기화해 준다. 위의 그림과 같이 headerNode까지 할당이 되며, memset을 이용해 0으로 초기화해 주었기 때문에 headerNode내부의 data와 pLink값도 모두 0과 NULL로 초기화 된 상태이다. 동적 할당이 실패하면 NULL을 리턴하였다.

3. addLLElement 함수 구현

int addLLElement(LinkedList* pList, int position, ListNode element)
{
    ListNode* pNode = NULL;
    ListNode* nextNode = NULL;
    if (pList != NULL)
    {
        if (position >= 0 && position <= pList->currentElementCount)//position 예외처리
        {
            nextNode = (ListNode*)malloc(sizeof(ListNode));//nextNode에 동적할당
            if (nextNode != NULL)//할당 성공 시에만
            {
                pNode = &(pList->headerNode);//pNode가 헤더노드 가리키도록
                *nextNode = element;//nextNode는 포인터 변수임.
                nextNode->pLink = NULL;
                for (int i = 0; i < position; i++)
                {
                    pNode = pNode->pLink;
                }//pNode가 position - 1번째 노드 가리키도록
                nextNode->pLink = pNode->pLink;//nextNode가 원래 position번째 노드 가리킴
                pNode->pLink = nextNode;//position - 1번지 노드가 추가될 노드 가리킴
                (pList->currentElementCount)++;
                return (TRUE);
            }
        }
        else
        {
            printf("out of index\\n");//position index 벗어남
        }
    }
    return (FALSE);
}

함수 기능 : 원하는 position에 element 노드를 삽입할 수 있는 함수. element는 포인터가 아닌 ListNode값이기 때문에 ListNode를 하나 동적할당 해서 넣어야 함에 주의하자. 동적할당 하지 않으면 함수가 끝나고 사라진다. 또한 deleteLinkedList나 removeLLElement에서 free를 쓰기 때문에 stack에 있는 메모리는 free할 수 없다.

또한 position의 범위는 0부터 currentElementCount보다 작거나 같아야 한다. currentElement보다 작지 않고 같아도 된다는 점에 유의하자. headerNode는 바꿀 수 없으며, 0번째에 노드를 추가하면 headerNode→pList값이 달라진다. headerNode가 달라지는 것이 아니다.