본문 바로가기
휴지통/자료구조-C

연결리스트2

by 신재권 2021. 2. 13.

연결의 형태가  한쪽 방향으로 전개되고  시작과 끝이 분명히 존재하는 '단순 연결 리스트'이다.

 

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

기능적으로 무엇인가를 변경하거나 추가하지 않는다면 ADT를 변경할 이유는 없다. 그래서 앞서 배열리스트에 정의한 리스트ADT를 그대로 적용해도된다. 하지만 연결리스트에 정렬 관련 기능을 추가하기 위해서 ADT를 조금확장한다.

 

정렬 기능이 추가된 리스트 자료구조의 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 또는 LNext함수의 마지막 반환 데이터를 삭제한다.

 

-삭제된 데이터는 반환된다.

-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

 

int LCount(List *plist);

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

 

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

-리스트의 정렬의 기준이 되는 함수를 등록한다. 

 

 

위의 ADT에 새로 추가된 함수는 SetSortRule이 전부이고, 그 이외에는 앞서 배열리스트의 ADT와 완전히 동일하다. 그리고 ADT에는 명시되어 있지는 않지만 우리는 다음 내용과 관련해서 결정을 해야한다 .

"새노드를 추가할 때, 리스트의 머리와 꼬리중 어디에 저장을 할 것인가?"

 

두 가지 방법 모두 장점과 단점이 있다. 머리에 추가할 경우 장점과 단점은 다음과 같다.

장점 : 포인터 변수 tail이 불필요 하다.

단점 : 저장된 순서를 유지하지 않는다.

 

반면 꼬리에 추가할 경우의 장점과 단점은 다음과 같다.

장점 : 저장된 순서가 유지된다.

단점 : 포인터 변수 tail 필요하다.

 

어떠한 방법이 더 좋다고 판단할 성격의 문제가 아니다.

"포인터 변수 tail을 유지하기 위해서 넣어야할 부가적인 코드가 번거롭게 느낄수 도있다. 게다가 리스트 자료구조는 저장된 순서를 유지해야 할 자료구조가 아니다"

 

그래서 머리에 추가하는 과정을 살펴보겠다.

 

새로 추가된 함수 SetSortRule에 대해서 이야기하자.

일단 C 함수 포인터를 알고있어야 한다. 

 

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

이 함수는 연결리스트의 정렬 기준을 지정하기 위한 함수이다 .정렬의 기준이란 것이 정수를 대상으로 보면 수의 크기가 전부이지만, 경우에 따라서는 알파벳의 순서이나 이름과 같은 문 자열의 길고 짧음의 대상이 될수도 있다. 따라서 다양한 가능성을 염두에 두고 ADT를 정의해야 실제 쓸모 있는 자료구조를 만들 수 있다. 

 

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

함수 포인터를 잘 알고 있다면 , SetSortRule 함수의 매개변수 선언에 이썽서 이것이 의미하는 바를 다음과 같음을 알수있다.

"반환형이 int고 LData형 인자를 두 개 전달받는 함수의 주소 값을 두 번째 인자로 전달해라"

 

따라서 다음과 같이 정의된 함수의 주소값이 SetSortRule 함수의 두 번째 인자가 될 수 있다.

int WhoIsPrecede(LData d1, LData d2)   //typedef int LData;

{

   if(d1 <d2)

     return 0;   //d1이 정렬 순서상 앞선다

   else 

     return 1;   //d2가 정렬 순서상 앞서거나 같다.

}

 

그리고 SetSortRule의 두번째 인자로 전달되는 함수는 위의 함수 정의에서 보이듯이 다음 조건을 갖춰서 정의해야 하는 것으로 결정하겠다.

"매개변수 d1에 전달되는 인자가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우에는 0을 반환하고, 매개변수인 d2에 전달되는 인자가 정렬 순서상 앞서거나 같은 경우에 1을 반환한다.

 

이렇듯 반환 값이 어떻게 되고 또 그것이 어떤 의미를 갖는지는 , 연결리스트를 구현하는 우리들이 결정할 문제이다. 

따라서 이는 얼마든지 바꿀수 있다 .우리는 반환 값을 0과 1로 제한했지만, 더 다양한 반환값과 의미를 부여해도 된다.

그럼 예를 들어서 D1과 D2라는 데이터가 있다고 가정해보자. 그리고 이를 대상으로 다음과 같이 함수를 호출한다고 가정해보자 .

 

int cr = WhoIsPrecede(D1, D2);

그 결과 cr에 반환된 값이 0이라면 D1 이 정렬 순서상 앞선다는 의미이므로, D1과 D2는 다음 의 순서로 저장이 되어야 한다.

head .... D1.... D2....tail   //D1이 head에 더 가깝다

 

반대로 cr이 반환된 값이 1이라면 D2가 정렬 순서상 앞선다는 의미이므로, D1과 D2는 다음의 순서로 저장되어야 한다.

haed ...D2....D1.....tail   // D2가 haed에 더 가깝다.

우리가 구현할 더미노드(Dummy Node)기반의 단순 연결 리스트

 

우리가 전에 구현했던 연결리스트는 haed -> data ->data->data->data  <-tail 

이런 구조였다.

이 연결리스트에는 다음과 같은 단점이 있다.

"노드를 추가, 삭제, 그리고 조회하는 방법에 있어서 첫번째 노드와 두번째 이후의 노드에 차이를  보인다"

 

우리는 그래서 다음 구조로 리스트를 구현한다.

head->dummyNode->data->data->data->data->NULL

 

우선 포인터 변수 tail이 사라졌다. 노드를 앞에서 부터 채우기로 하였으니 이는 불필요하다. 그리고 리스트의 맨 앞에 '더미노드(Dummy Node)'라는 것을 넣어뒀다. 이는 유효한 데이터를 지니지 않는 그냥 빈 노드를 일컫는 말이다.

하지만 이렇게 빈 노드를 미리 넣어두면 , 처음 추가되는 노드가 구조상 두 번째 노드가 되므로 노드의 추가, 삭제 및 조회의 과정을 일관된 형태로 구성할 수 있다.

정렬 기능이 추가된 연결리스트의 구조체와 헤더파일에 정의

다은은 노드를 표현할  구조체의 정의이다. 그리고 연결리스트의 구현에서 이는 결코 빠지지 않는다.

 

typedef struct _node   //typedef int LData

{
 LData data;

 struct _node *next;

}Node;

 

그런데 연결리스트의 구현에 필요한 다음 유형의 변수들은 별도의 구조체로 묶지 않고 그냥 main함수의 지역변수로 선언하기도 하고, 더 나쁜경우에는 전역변수로 선언하기도 한다.

Node *head;   //연결리스트의 머리를 가리키는 포인터 변수

Node *cur;  //참조를 위한 포인터 변수

 

위 유형의 포인터 변수들은 main함수 내에서도, 전역변수로도 선언해서는 절대 안된다.

만약 프로그램을 구현하는데 여러개의 배열이 있다면  저 포인터 변수들을 각각 선언해줘야 해 무식한 코드를 만들어야 한다.

 

즉 head와 cur과 같은 포인터 변수를 묶어서 다음과 같이 연결리스트를 의미하는 구조체를 별도로 정의해야 한다.

 

typedef struct _linkedList

{
  Node *head;  //더미 노드를 가리키는 멤버

  Node *cur;   //참조 및 삭제를 돕는 멤버

  Node *before;  //삭제를 돕는 멤버

  int numOfData;  //저장된 데이터의 수를 기록하기 위한 멤버

  int (*comp)(LData d1, LData d2);   //정렬의 기준을 등록하기 위한  멤버

}LinkedList;

 

ArrayList가 배열 기반의 리스트를 표현한 결과라면 , LinkedList는 연결 기반 리스트를 표현한 결과이다. 

다음 작성될 예제는 더미 노드 기반의 정렬삽입도 되고, 정렬 삽입의 기준도 바꿀수 있는 연결리스트를 위한 헤더파일이다.

//DLinkedList.h
#ifndef __D_LINKED_LIST_H
#define __C_LINKED_LIST_H

#define TRUE 1
#define FALSE 0

typedef int LData;

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

typedef struct _linkedList
{
	Node *haed;
    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 *pdata);

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

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

#endif

 

더미노드(Dummy Node)기반의 단순 연결리스트 구현1 :리시트 초기화와 노드 삽입

다음은 연결리스트를 표현한 구조체의 정의이다. 연결리스트를 생성하기 원한다면 다음 구조체의 변수를 하나 선언하거나 동적으로 할당하면된다. 따라서 이후로는 다음 구조체의 변수를 가리켜 그냥 '리스트'라 하겠다.

 

typedef struct _linkedList

{

  Node *head;

  Node* cur;

  Node* before;

  int numOfData;

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

}LinkedList;

 

위 구조체 변수가 선언되면 이를 대상으로 초기화를 진행해야 하는데, 이때 호출되는 함수는 다음과 같다.

 

void ListInit(List *plist)

{

  plist->head = (Node *)malloc(sizeof(Node));  //더미 노드의 생성

  plist->head->next = NULL;

  plist->comp = NULL;

  plist->numOfData = 0;  

}

 

위의 초기화 결과를 설명하면 

head가 더미노드를 가리키고 있다. 

더미노드의 next는 NULL을 가리키고 있는 상태이다.

haed ->Dummy  Node->NULL

 

위에 표현되진 않았지만 리스트의 멤버 comp가 NULL로, 멤버 numOfData가 0으로 초기화 된다는 사실을 기억해야 한다. 이제 위 상황에서 노드의 추가를 위해 호출되는 함수는 다음과 같다.

 

void LInsert(List *plist, LData data)

{  

  if(plist->comp ==NULL)   //정렬기준이 마련되어 있지 않다면 

      FInsert(plist , data);   //머리에 노드를 추가

  else  //정렬 기준이 마련되었다면

      SInsert(plist, data);  //정렬 기준에 근거하여 노드를 추가

}

 

위의 함수에서 보이듯이 노드에 추가는 리스트의 멤버  comp에 무엇이 저장되어 있느냐에 따라서 FInsert또는 SInsert 함수를 통해서 진행이 된다. 그런데 이 두함수 모두 헤더파일에 선언된 함수가 아니다. 즉 리스트를 사용하는 프로그래머는 이 두함수를 직접 호출할 수 없다. 리스트 내부적으로 호출이 되도록 정의된 함수들이기 때문이다. 그럼 먼저 comp가 NULL일때 호출되는 FInsert 함수를 보자

 

void FInsert(List *plist , LData data)

{   

   Node *newNode = (Node* ) malloc(sizeof(Node));  //새 노드 생성

  newNode->data = data;   // 새 노드에 데이터 저장

  

  newNode ->next = plist ->haed ->next;  //새 노드가 다른 노드를 가리키게 함

  plist->head->next = newNode;   //더미노드가 새 노드를 가리키게 함

 

  (plist -> numOfData)++;   //저장된 노드의 수를 하나 증가시킴

}

 

위의 함수를 이해하기 위해서는 현재 포인터 변수 head가 NULL이 아닌 , 더미노드를 가리키고 있다는 사실을 잊지 말아야 한다. 그리고 위의 함수에는 if ..else 구문이 없다는 사실에도 주목해야 한다.

이는 모든 노드의 추가과정이 일관되게 정의되었음을 뜻하는 것이며, 이것이 바로 더미노드가 주는 이점이기 때문이다. 

 

그럼 현재 연결리스트에  4와 6이 저장된 상태에서 위의 함수가 다음과 같이 호출되었다고 가정해보자.

FInsert(plist ,2);  //plist는 리스트의  주소를 담고있는 포인터 변수

 

그러면 이어서 다음 두문장이 차례로 실행된다.

 

void FInsert(List *plist , LData data)

{   

   Node *newNode = (Node* ) malloc(sizeof(Node));  //새 노드 생성

  newNode->data = data;   // 새 노드에 데이터 저장

  ...

}

 

head ->DMY->4->6->NULL

newNode ->2

 

그리고 이어서 다음 두 문장이 실행된다.

void FInsert(List *plist , LData data)

{   

   ,,,,

  newNode ->next = plist ->head ->next;  //새 노드가 다른 노드를 가리키게 함

  plist->head->next = newNode;   //더미노드가 새 노드를 가리키게 함

....

}

 

첫번째 문장으로 인해

현재 plist->head->next 는 더미노드가 다음 노드 4를 가리킨다. 

하지만 이것을 newNode ->next에 넣어 

newNode->next가 노드 4를 가리키게 한다.

 

두번째 문장으로 인해

더미노드가 newNode를 가리키게 한다.

head-> DMY ->2->4->6->NULL

 

이렇게 해서 comp가 NULL일 때 노드의 추가과정을 모두 보였다. 

더미노드(Dummy Node)기반의 단순 연결 리스트 구현2: 데이터 조회

우리가 정의한 리스트 ADT를 기준으로 '조회'하면 떠오르는 두 함수는 LFirst와 LNext이다.

이 두함수의 기능은 배열리스트의 LFirst 그리고 LNext와 동일하다. 

먼저 LFirst함수를 볼 것인데, 아래의 주석에서 말하는 '첫번째 노드'는 더미 노드와 다음에 연결된 노드를 뜻하는 것임에 유의하자. 그리고 이후로도 더미 노드의 다음에 연결된 노드를 가리켜 '첫번째 노드'라 하겠다.

 

int LFirst(List *plist , LData *pdata)

{

  if(plist->head ->next ==NULL)   //더미 노드가 NULL을 가리킨다면 .

     return FALSE;  //반환할 데이터가 없다.

 

  plist->before = plist->head;   //before는 더미노드를 가리키게 함

  plist->cur = plist ->head->next;  //cur은 첫번째 노드를 가리케가 함

 

 *pdata = plist->cur->data;   //첫 번째 노드의 데이터를 전달

  return TRUE;  //데이터 반환 성공

}

 

위 함수의 핵심이 되는 두 문장은 다음과 같다.

plist->before = plist ->head;  //before은 더미노드를 가리키게 함

plist ->cur = plist->head->next;  //cur은 첫 번째 노드를 가리키게 함

 

그리고 리스트에 2, 4 ,6  , 8이 저장된 상태에서 LFirst 함수가 호출되고, 이어서 두 문장이 실행되었을 때  상황을 살펴보자

head->DMY->2->4->6->8->NULL

첫번째 문장으로 인해 head가 가리키는 (즉 더미노드)를 before이 가리키게 한다.

두번째 문장으로 인해 head의 next 노드 (즉 첫번째 노드)를 cur이 가리키게 한다.

 

때문에 이어서 실행되는 다음 문장을 통해서 첫 번째 데이터가 전달된다(반환된다)

 *pdata = plist->cur->data;  //첫번째 노드의 데이터를 전달

 

그렇다면 리스트 구조체의 멤버에 before를 둬서 멤버 cur보다 하나 앞선 노드(왼쪽에 있는 노드)를 가리키게 하는 이유는 무엇일까?  이는 잠시후에 설명하는 '노드의 삭제'와 관련이 있으니 before가 cur보다 하나 앞선 노드를 가리킨다는 사실에 주목해야 한다. 그리고 이관계는 이어서 호출되는  LNext 함수가 호출되어도 유지되어야 한다.

 

int LNext(List  *plist, LData *pdata)

{

  if(plist->cur ->next ==NULL)  //cur이 NULL을 가리킨다면, (즉 마지막 데이터라면)

      return FALSE;   //반환할 데이터가 없다

  

  plist->before = plist->cur;  //cur이 가리키던 것을 before가 가리키게 함

  plist->cur = plist ->cur ->next;   //cur은 그 다음 노드를 가리킴

 

  *pdata = plist->cur ->data;   //cur이 가리키는 노드의 데이터 전달

  return TRUE;   //데이터 반환 성공

}

 

이렇듯 LNext함수는 LFirst함수와 많이 유사하다. 그리고 LFirst 함수와 유사하게 다음 두문장도 LNext 함수의 핵심이라 할 수 있다.

plist ->before = plist->cur;  //cur이 가리키던 것을 before이 가리키게 함

plist ->cur = plist->cur->next;   // cur은 그 다음 노드를 가리키게 함

 

즉 cur과 before 가리키는 대상을 하나씩  오른쪽으로 이동하게 된다.

 

이렇듯 cur이 마지막 노드를 가리킬 때 까지 LNext함수가 호출되면, cur과 before가 한칸씩 다음 노드로 이동하니 cur을 이용해서 모든 데이터를 참조하게 된다.

 

더미노드(Dummy Node)기반의 단순연결리스트 구현 3: 노드의 삭제

연결리스트에서 데이터의 추가만큼이나 신경써야 할 것이 삭제이다 .그리고 삭제를 담당하는 LRemove함수를 구현하기에 앞서 삭제 과정을 파악해야한다. 이전에 구현한 배열 기반리스트에서와 마찬가지로 LRemove 함수의 기능은 다음과 같다

"바로 이전에 호출된 LFirst, LNext 함수가 반환한 데이터를 삭제한다."

 

head->DMY->2->4->6->8->NULL

현재 before은 2를 가리키고 cur은 4를 가리키고 있다고 가정해보자.

이 상황은 LNext함수의 호출을 통해 4가 반환되었다는 뜻이다. 따라서 LRemove함수의 호출시 소멸시켜야 하는 노드는 현재 cur이 가리키는 , 4가 저장된 노드이다. 따라서 삭제의 최종결과는 다음과 같다.

 

head->DMY->2->6->8->NULL

현재 before과 cur이 2를 가리키고있다.

 

여기서 주목할 것은 cur의 위치가 재조정되었다는 사실이다. 4가 지정된 노드가 지워졌다고 해서 6이 저장된 노드를 가리키게 해서는 안된다. 그렇게 되면 6까지 참조가 이뤄졌다는 뜻이되기 때문이다. 따라서 cur이 가리키는 위치를 한 칸 왼쪽으로 이동시켜야 한다. 그리고 이렇듯 cur의 위치를 한칸 왼쪽으로 이동시키기 위해서는 before의 도움이 필요하다.

 

"cur만 한 칸 왼쪽으로 이동시키면 ,before와 cur이 동일한 위치를 가리키게 되니까, before 도한칸 왼쪽으로 이동시켜야 하는거 아닌가?"

라 생각할 수 있다.

 

재차 LFirst나 Lnext함수가 호출되면 before는다시 cur보다 하나 앞선노드(왼쪽의 노드)를 가리키게 되므로 굳이 이 상황에서는  before의 위치까지 재조정할 필요는 없다. 무엇보다도 노드들이 한쪽 방향으로만 연결되어있기 때문에 before를 한 칸 왼쪽으로 이동시키기 위해서는 그 만큼 대가를 치뤄야 한다. 

LRemove함수를 보이겠다.

 

LData LRemove(List *plist)

{  

   Node *rpos = plist->cur ;   //소멸 대상의 주소 값을 rpos에 저장

   LData rdata = rpos->data;  //소멸 대상의 데이터를 rdata에 저장

 

  plist->before ->next = plist->cur ->next;  //소멸 대상을 리스트에서 제거

  plist->cur = plist ->before;  //cur이 가리키는 위치를 재 조정

 

  free(rpos);  //리스트에서 제거된 노드 소멸

 (plist->numOfData)--;   //저장된 데이터의 수 하나 감소

  return rdata;   //제거된 노드의 데이터 반환

}

 

 Node *rpos = plist->cur ;   //소멸 대상의 주소 값을 rpos에 저장

   LData rdata = rpos->data;  //소멸 대상의 데이터를 rdata에 저장

위 두문장이 실행되었다면 

rpos는 현재 cur이 가리키는 노드를 가리키게 될것이고 ,

rdata는 rpos가 가리키는 노드의 데이터를 저장한다.

 

 

plist->before ->next = plist->cur ->next;  //소멸 대상을 리스트에서 제거

  plist->cur = plist ->before;  //cur이 가리키는 위치를 재 조정

위 두문장을 실행하면

 

before의 다음 노드를 cur의 다음노드(즉 삭제할 다음노드)랑 연결해 cur이 가리키는 노드를 끊어버린다(소멸시킨다)

그리고 before이 가리키는 노드 (삭제할 노드의 왼쪽노드)를 cur이 가리키게 한다. 

 

여기까지만 진행되도 리스트에서 노드는 제거된 셈이다. 따라서 다음 문장에서 제거된 노드를 완전히 소멸시키고, 데이터 수를 감소 시키고, 이어서 제거된 노드의 저장된 값을 반환하는 일인데, 이는 다음 문장에 의해서 실행이 된다.

 

  free(rpos);  //리스트에서 제거된 노드 소멸

 (plist->numOfData)--;   //저장된 데이터의 수 하나 감소

  return rdata;   //제거된 노드의 데이터 반환

 

이로써 노드의 제거는 완전히 끝이났다. 

이결과는 cur과 before이 같은 곳을 가리키게 된다.

더미노드(Dummy Node)기반의 단순 연결 리스트 구현 4: 하나로 묶기

위의 사항을 종합해 코드를 작성하겠다.

 

//DLinkedList.h
#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 sturct _linkedList
{
	Node *head;
    Node *cur;
    Node *before;
    int numOfData;
    int(*comp)(LData d1, LData d2);
}LinkedList;

typedef LinkedList List;

void ListInit(List *plist);
void LInest(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
//DLinkedList.c
#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;  //더미노드가 가리키는 다음값을 newNode가 가리키게함
    plist->head->next =newNode;  //더미노드가 가리키는 값을 newNode로 
    
    (plist->numOfData)++;
}

void SINsert(List *plist, LData data)
{
   		//다음에 설명
}

void LInsert(List *plist, LData data)
{
	if(plist->comp ==NULL)  //정렬기준이 NULL이면
    	FInest(plist ,data); 
    else			//정렬 기준이 있다면
    	SInsert(plist ,data);
}

int LFirst (List *plist, LData *pdata)
{
	if(plist->head->next ==NULL)	//더미노드 next에 저장된값이 없다면
    	return FALSE;
	
    plist->before = plist->head; //before을 더미노드를 가리키게함
    plist->cur = plist->head->next;  //cur을 더미노드의 다음노드를 가리키게 함
    
    *pdata = plist->cur->data;  //cur이 가리키는 노드의 data값을 저장
    return TRUE;
}

int LNext(List *plist, LData *pdata)
{
	if(plist->cur ->next ==NULL)		//저장된 값이 없다면
    	return FALSE;
        
   	plist->before =plist ->cur;			//before을 현재 cur이 가리키고 있는 위치로바꿈
    plist->cur = plist ->cur->next; //cur을 cur의 다음위치를 가리키고 있는 위치로 바꿈
    
    *pdata = plist->cur ->data;  //cur이 가리키고 있는 노드의 데이터를 삽입
    return TRUE;
}

LData LRemove(List* plist)
{
	Node *rpos = plist->cur;	//삭제할 노드를 임시저장
    LData rdata = rpos->data;	//삭제할 노드의 데이터를 임시저장
    
    plist ->before->next = plist->cur->next;	//cur의 다음노드를 before 다음노드가 가리키게함
    plist->cur =plist ->before;  //before의 위치를 cur에 저장함 (위치를 조정)
    
    free(rpos);  //메모리 할당 해제
    (plist->numOfData)--;
    return rdata;
}

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

void SetSortRule(List *plist , int (*comp)(LData d1, LData d2))
{
	//다음에 설명
}

 

//DLinkedListMain.c
#include <stdio.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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

저작자표시 비영리 변경금지

'휴지통 > 자료구조-C' 카테고리의 다른 글

원형 연결 리스트  (0) 2021.02.15
연결리스트 3  (0) 2021.02.14
링크드리스트1  (0) 2021.02.12
배열 기반의 리스트(List)2  (0) 2021.02.09
배열 기반의 리스트(List)1  (0) 2021.02.08

관련글

티스토리툴바