연결리스트

연결리스트 (Linked List)

연결리스트의 구현을 이해하기 위해서는,

malloc 함수와 free함수 기반의 메모리 동적할당에 대한 완전한 이해가 필요

배열은 index를 이용해 순차 접근이 가능한 자료구조

배열은 기본적으로 정적이다. (길이의 변경 불가능)

#include <stdio.h> int main(void) { int arr[10]; int readCount = 0; int readData; int i; while (1) { printf("자연수 입력 (0이하 값 입력시 종료): "); scanf("%d", &readData); if (readData < 1) break; arr[readCount++] = readData; } for (i = 0; i<readCount; i++) printf("%d ", arr[i]); return 0; }

위의 예제에서 0 이하의 값을 입력하지 않고, 

계속해서 할당된 배열의 길이를 넘어서는 입력을 할 시 디버그 에러가 나게 된다.

이를 해결하기 위해선 메모리의 동적할당을 이용해야 한다.

* head : 첫번째 node를 가리키기 위함

* tail : head와 달리 필요없을 수도 있음

* cur : (current) 순차접근을 위한 것

//노드의 머리에 추가하는 연결리스트
 
/* 노드 추가 과정 (동적 할당) */
    Node * newNode = NULL;
    newNode = (Node *)malloc(sizeof(Node));
    newNode->data = readData;
    newNode->next = NULL;
 
    if (head == NULL)
    {
      head = newNode;
      //tail = newNode;
    }
    else
    {
      newNode->next = head;
      head = newNode;
    }
  }

새 노드를 연결리스트 머리에 추가하는 경우는, * tail이 불필요하지만 저장된 순서가 역순이 된다.

꼬리에 추가하는 경우는 저장된 순서가 유지되지만 * tail이 필요

노드의 꼬리에 추가하는 연결리스트

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node
{
  int data;
  struct _node * next;
}Node;
 
int main(void)
{
  // NULL 초기화
  Node * head = NULL;
  Node * tail = NULL;
  Node * cur = NULL;
  Node * newNode = NULL;
 
  // 데이터 입력받는 과정
  int readData;
  while (1)
  {
    printf("자연수 입력: ");
    scanf("%d", &readData);
 
    if (readData < 1)
      break;  
 
    // 노드 생성
    newNode = (Node*)malloc(sizeof(Node));
    newNode->data = readData;
    newNode->next = NULL;
 
    if (head == NULL)
      head = newNode;
    else
      tail->next = newNode;
 
    tail = newNode;
  }  
  // 데이터 출력과정
  printf("\n 전체 데이터 출력: \n");
  if (head == NULL)
    printf("데이터 없음");
 
  else
  {
    cur = head;
    printf("%d ", cur->data);
 
    while(cur->next != NULL)
    {
      cur = (*cur).next;
      printf("%d ", (*cur).data);
    }
  }
  printf("\n");
 
  // 메모리 해제 과정
  if (head == NULL)
    return 0;
 
  else
  {
    Node * delNode = head;
    Node * delNextNode = head->next;    
    printf("%d 삭제 \n", head->data);
    free(delNode);
 
    while (delNextNode != NULL)
    {
      delNode = delNextNode;
      delNextNode = delNode->next;
      printf("%d 삭제 \n", delNode->data);
      free(delNode);      
    }
  }
}

정렬 기능 추가된 연결 리스트의 ADT

추가되는 함수

void SetSortRule(List * plist, int (*comp)(LData d1, Ldata d2)  

int (*comp)(LData d1, Ldata d2)  

반환형이 int인 LData형 인자를 두개 전달받는, 함수의 주소값 전달

(typedef LData int)

다음과 같이 정의된 함수의 주소값이 SetSortRule 함수의 두번째 인자가 됨

int WhoIsPrecede(LData d1, LData d2)

{

if(d1 < d2)

return 0; // d1이 head에 가까우면 0 반환

else

return 1; // d2가 head에 가까우면 1 반환

}

리스트라는 자료구조를 바꾸지 않으면서

정렬의 기준을 지정(약속)하는 함수를 정의

더미 노드 기반, 연결리스트

앞선 예제에서 첫번째 노드는 * head가 가리킨다는 점에서

다른 노드들과 차이가 있었다.

때문에 노드추가, 삭제, 조회하는 방법에 있어 일관성이 없다는 단점이 있었다.

(첫번째 노드와 두번째 이후 노드에 차이가 있다)

이를 해결하기위해 Dummy Node를 추가한다.

처음 추가되는 노드가 구조상 두번째 노드가 되며,

노드 추가, 삭제 및 조회의 과정이 일관된 형태로 구성된다.

LinkedRead.c

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node
{
    int data;
    struct _node * next;
} Node;
 
int main(void)
{
    Node * head = NULL;
    Node * tail = NULL;
    Node * cur = NULL;
 
    Node * newNode = NULL;
    int readData;
 
    head = (Node*)malloc(sizeof(Node));    // 추가 된 문장, 더미 노드 추가
    tail = head;
    
    /**** 데이터를 입력 받는 과정 ****/
    while (1)
    {        
        printf("자연수 입력: ");
        scanf("%d", &readData);
        if (readData < 1)
            break;
 
        /*** 노드의 추가과정 ***/
        newNode = (Node*)malloc(sizeof(Node));
        newNode->data = readData;
        newNode->next = NULL;
 
        /*
        if(head == NULL)
        head = newNode;
        else
        tail->next = newNode;
        */
        tail->next = newNode;
 
        tail = newNode;
    }
    printf("\n");
 
    /**** 입력 받은 데이터의 출력과정 ****/
    printf("입력 받은 데이터의 전체출력! \n");
    if (head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다. \n");
    }
    else
    {
        cur = head;
        //    printf("%d  ", cur->data);   // 첫 번째 데이터 출력
 
        while (cur->next != NULL)    // 두 번째 이후의 데이터 출력
        {
            cur = cur->next;
            printf("%d  ", cur->data);
        }
    }
    printf("\n\n");
 
    /**** 메모리의 해제과정 ****/
    if (head == NULL)
    {
        return 0;    // 해제할 노드가 존재하지 않는다.
    }
    else
    {
        Node * delNode = head;
        Node * delNextNode = head->next;
 
        //    printf("%d을(를) 삭제합니다. \n", head->data);
        //    free(delNode);    // 첫 번째 노드의 삭제
 
        while (delNextNode != NULL)    // 두 번째 이후의 노드 삭제 위한 반복문
        {
            delNode = delNextNode;
            delNextNode = delNextNode->next;
 
            printf("%d을(를) 삭제합니다. \n", delNode->data);
            free(delNode);    // 두 번째 이후의 노드 삭제
        }
    }
 
    return 0;
}