Linked List - 연결 리스트 코드 구현

Programming/C DataStructure

Linked List - 연결 리스트 코드 구현

양디 2015. 12. 28. 16:34

Linked List : 연결 리스트

저번 시간에는 연결 리스트의 개념에 대해 배워 보았다.

이번 포스팅은 연결 리스트를 어떻게 구현하는지에 관한 내용이다.

어떤 개념을 이해하는 데에 효과적인 방법으로는 ,

자신이 직접 코드를 작성하는 것 / 남이 짠 코드를 분석하는 것 이라고 생각한다.

따라서 이 두 가지 방법을 모두 다 사용하기 위해 절반의 코드를 작성하여 업로드 할 것이다.

비어 있는 부분의 코드를 직접 작성하기 위해서는, 기존에 작성되어 있는 코드를 잘 이해하여야 한다.

그럼 시작해보자.

우선 굉장히 단순하게 연결 리스트를 구현하기 위한 것이다.

1. 구조체 정의

1
2
3
4
5
6
7
8
9
10
typedef struct _node {
    int data;
    struct _node *next;
}Node, *pNode;
 
typedef struct _list {
    int count;  // 노드의 갯수를 저장한다.
    pNode head; // 첫번째 노드를 가리킨다.
    pNode tail; // 마지막 노드를 가리킨다.
}List, *pList;
cs

각각 노드와 리스트를 정의하였다. 노드 구조체는 Node, 포인터는 pNode이고,

연결리스트의 경우는 List와 pList의 포인터로 정의하였다.

단순 연결 리스트이며, 코드가 이해가 안된다면 개념 부분을 다시 보고 오는 것이 좋겠다.

2. 함수 정의

함수들은 사용 목적, 환경에 따라 달라지므로 포스팅에서는 가장 기본적인 기능들만을 추가하려고 한다.

첫번째로 리스트를 생성하는 함수이다.

1
2
3
4
5
6
7
pList makeList() {
    pList list = (pList)malloc(sizeof(List));
    list->count = 0;
    list->head = NULL;
    list->tail = NULL;
    return list;
}
Colored by Color Scripter
cs

List를 malloc으로 동적할당하고, 새로 만든 List의 내부 속성들을 설정한다.

처음에는 아무 Node가 존재하지 않기 때문에 count는 0, head와 tail도 null포인터를 가리키게 된다.

그리고 만들어 낸 list를 반환한다. 정의는 이런 식으로 하고 실제 사용은 다음과 같이 하겠다.

1
pList list = makeList();
cs

위와 같이 본 함수에서 포인터를 생성하여 리스트를 만든다.

두번째로 리스트에 추가할 노드를 만든다.

1
2
3
4
5
6
7
//Node를 만드는 함수. Data를 입력 받아서 저장하고, 만든 node를 반환한다.
pNode makeNode(int data) {
    pNode node = (pNode)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}
Colored by Color Scripter
cs

List와 비슷한 모습이다. data를 받아서 node에 집어 넣고, 기본적으로 next는 아직 연결이 되지 않았으므로 NULL로 하고 반환한다.

세번째로 리스트에 노드를 추가시키는 함수이다.

1
2
//집어 넣을 노드인 N을 List L의 가장 처음, 즉 head에 집어 넣는 함수.
void insertFront(pList L, pNode N)
cs

insert는 front, rear, middle 어디든 가능하지만 가장 기본적인 front 즉 head에 집어 넣는 함수를 구현해보자.

이 부분은 직접 구현했으면 해서 코드를 적지는 않겠다.

다만 알고리즘은 다음과 같다.

고려하여야 할 사항이 한가지 있는데, 노드를 넣을 때 해당 노드가 처음인지 아닌지가 바로 그것이다.

처음 집어넣는 노드라면 head인 것과 동시에 tail이 되는 것이다.

반면에 기존에 노드가 존재한다면, 새로 넣는 node는 head가 되고, next는 기존의 head가 되는 것이다.

따라서 L의 내부에 노드가 존재하는지 조건문으로 판별하고,

판별 결과에 따라서 head, tail, N, N->next 들을 수정해주면 되겠다.

또한 List의 count를 증가시켜주는 것은 당연히 해줘야겠지 !

네번째로 리스트에서 해당 Data를 갖고 있는 노드가 있으면 삭제하는 함수이다.

1
void deleteData(pList L, int data)
cs

List의 첫번째 노드부터 시작해서 요청 data와 같은 data를 갖고 있는 node가 있다면 free 시키는 함수이다.

고려하여야 할 사항은 다음과 같다.

먼저 반복문을 통하여 node를 하나씩 검사한다. 만약 data가 같은 노드를 발견하면 삭제를 한다.

삭제 할 때 조건문이 3개로 분기가 되는데 ,

첫번째. 삭제하는 노드가 head일 경우 ,

이 경우에는 head를 삭제하는 노드의 next로 변경해주고 free해주면 되겠다.

두번째. 삭제하는 노드가 tail일 경우,

이 경우에는 삭제하기는 노드의 앞 노드를 tail로 바꿔주고 free시켜주면 되겠다.

세번째. 삭제하는 노드가 중간의 노드일 경우,

이 경우에는 삭제하는 노드의 앞 노드와 뒤 노드를 연결시켜주고 삭제하면 되겠다.

hint! 즉, 유지해야 할 노드는 <앞 노드, 삭제할 노드, 뒷 노드>의 세가지 인 것이다.

그러나 뒷 노드는 node->next로 접근이 가능하므로 신경쓰지 않아도 되지만, 앞 노드는 유의하여야 한다!

마지막으로 리스트를 Free시켜주는 함수이다.

1
2
3
4
5
6
7
8
9
10
void freeList(pList L) {
    pNode tmp = L->head;
    pNode prev = NULL;
    for (size_t i = 0; i < L->count; i++)
    {
        prev = tmp;            
        tmp = tmp->next;    
        free(prev);            
    }
}
Colored by Color Scripter
cs