단순 연결 리스트

---

단순 연결 리스트 ADT

• void ListInit(List *plist);

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

• 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 or LNext 함수가 리턴하는 데이터를 삭제
  • 삭제된 데이터는 리턴
  • 마지막 반환 데이터를 삭제, 반복 호출 허용 안함

• int LCount(List *plist);

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

• void SetSortRule(List plist, int (comp)(LData d1, LData d2));

  • 리스트에 정렬의 기준이 되는 함수 등록

---

이번 연결 리스트에서는 tail 포인터 변수를 사용하지 않고 구현하였다

tail을 사용하는 경우 저장된 순서가 유지되지만, 부가적인 코드가 생긴다.
하지만 리스트 자료구조는 저장된 순서를 유지해야 하는 자료구조가 아니기 때문에 꼭 저장된 순서를 유지할 필요는 없다.

그리고 이번에는 head에 바로 저장하는 것이 아니라 더미(dummy) 노드를 추가한 형태의 연결 리스트를 만든다.

아직 더미 노드가 주는 편리함을 제대로 이해하지는 못했다.
하지만 포스팅을 하다보면 알게 되겠지

헤더파일

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#define TRUE 1
#define FALSE 0

typedef int LData;

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

typedef struct _linkedList
{
   Node *head;
   Node *cur;
   Node *before;
   int numOfData;
   int (*comp)(LData d1, LData d2);
} LinkedList;

typedef LinkedList List;

void ListInit(List *plist);
void LInsert(List *plist, LData data);

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

LData LRemove(List *plist);
int LCount(List *plist);

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

#endif

소스파일

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"

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

void FInsert(List *plist, LData data)
{
   Node *newNode = (Node *)malloc(sizeof(Node));
   newNode->data = data;
   newNode->next = plist->head->next;
   plist->head->next = newNode;
   (plist->numOfData)++;
}

void SInsert(List *plist, LData data)
{
}

void LInsert(List *plist, LData data)
{
   if (plist->comp == NULL)
   {
      FInsert(plist, data);
   }
   else
   {
      SInsert(plist, data);
   }
}

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;
}

LData LRemove(List *plist)
{
   Node *rpos = plist->cur;
   LData rdata = rpos->data;

   plist->before->next = plist->cur->next;
   plist->cur = plist->before;

   free(rpos);
   (plist->numOfData)--;

   return rdata;
}

int LCount(List *plist)
{
   return plist->numOfData;
}

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

메인파일

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"

int main()
{
   List list;
   int data;
   ListInit(&list);

   // 데이터 5개 저장
   LInsert(&list, 11);
   LInsert(&list, 11);
   LInsert(&list, 22);
   LInsert(&list, 22);
   LInsert(&list, 33);

   // 저장된 데이터 전체 출력
   printf("현재 데이터 수 : %d \n", LCount(&list));

   if (LFirst(&list, &data))
   {
      printf("%d ", data);

      while (LNext(&list, &data))
      {
         printf("%d ", data);
      }
   }
   printf("\n\n");

   // 숫자 22 검색해서 모두 삭제
   if (LFirst(&list, &data))
   {
      if (data == 22)
      {
         LRemove(&list);
      }
      while (LNext(&list, &data))
      {
         if (data == 22)
         {
            LRemove(&list);
         }
      }
   }

   // 삭제 후 남아있는 데이터 전체 출력
   printf("현재 데이터 수 : %d \n", LCount(&list));

   if (LFirst(&list, &data))
   {
      printf("%d ", data);

      while (LNext(&list, &data))
      {
         printf("%d ", data);
      }
   }
   printf("\n\n");

   return 0;
}

메인 결과

현재 데이터 수 : 5 
33 22 22 11 11 

현재 데이터 수 : 3
33 11 11