단순 연결 리스트의 연산 구현

• 삽입 연산 insert_first()

단순 연결 리스트에서 매개 변수 head 는 헤드 포인터이고 value 는 새롭게 추가되는 데이터이다.

ListNode* insert_first(ListNode *head, element value);

head 가 첫 번째 노드를 가리키기 때문에 리스트의 시작 부분에 노드를 추가하는 것은 비교적 쉽다. 새로운 노드를 하나 생성하고 새로운 노드의 link 에 현재의 head 값을 저장한 후에 head 를 변경하여 새로 만든 노드를 가리키도록 하면 된다. insert_first() 은 변경된 헤드 포인터를 반환한다. 따라서 반환된 값을 헤드포인트에 저장해야 한다.

위의 그림을 알고리즘으로 만들면

1. 동적 메모리 할당을 통하여 새로운 노드 p를 생성한다.

2. p->data 에 value 를 저장한다.

3. p->link 를 현재의 head 값으로 변경한다.

4. head 를 p 값으로 변경한다.

5. 변경된 헤드 포인터 변환

 

ListNode* insert_first(ListNode *head,int value)
{
  ListNode *p = (ListNode *)malloc(sizeof(ListNode));
  p->data = value;
  p->link = head; //헤드 포인터의 값을 복사
  head = p;  // 헤드 포인터 변경
  return head;  //변경된 헤드 포인터 반환환
}

 

• 삽입 연산 insert()

insert() 는 가장 일반적인 경우로서 연결 리스트의 중간에 새로운 노드를 추가한다. 이때는 반드시 삽입되는 위치의 선행 노드를 알아야 삽입이 가능하다. 선행 노드를 pre 가 가리키고 있다고 가정하자. 예를 들어서 아래 그림에서 20 과 30 사이에 35을 삽입하려면 다음과 같은 과정이 필요하다.

1. 새로운 노드를 생성하여 변수 p로 가리킨다.

2. p의 데이터 필드에 35를 저장한다.

3. p의 링크 필드가 노드 30을 가리키게 변경한다.

4. 20의 링크 필드가 35를 가리키도록 한다

5. 변경된 헤드 포인터 반환

ListNode* insert(ListNode *head,ListNode *pre,int value)
{
  ListNode *p = (ListNode *)malloc(sizeof(ListNode)); //(1)
  p->data = value; //(2)
  p->link = pre->link; //(3)
  pre->link = p;  //(4)
  return head; //(5)
}

 

 

• delete_first() 함수

첫 번째 노드를 삭제하는 함수 delete_first() 함수는 다음과 같은 원형을 가진다

ListNode* delete_first(ListNode *head);

1. 헤드 포인터의 값을 removed 에 복사한다

2. 헤드 포인터의 값을 head->link 로 변경한다

3. removed 가 가리키는 동적 메모리를 반환한다

4. 변경된 헤드 포인터를 반환한다

ListNode *delete_first(ListNode *head)
{
  ListNode *removed;
  if (head == NULL) return NULL;
  removed = head; //(1) 1,2과정은 서로 교체한다고 생각
  head = removed->link; //(2)
  free(removed); //(3)
  return head; //(4)
}

 

 

• 삭제 연산 delete()

리스트의 중간에서 삭제하는 알고리즘을 살펴보자. 다음과 같은 단순 연결 리스트에서 노드 30을 삭제한다고 하자.

1. 삭제할 노드를 찾는다

2. 노드 10의 링크 필드가 노드 30을 가리키게 한다

3. 삭제할 노드의 동적 메모리를 반납한다

4. 변경된 헤드 포인터를 반환한다

//pre 가 가리키는 노드의 다음 노드를 삭제한다
ListNode* delete(ListNode *head, ListNode *pre)
{
  ListNode *removed;
  removed = pre->link;
  pre->link = removed->link; //(2)
  free(removed); //(3)
  return head;  //(4)
}

 

 

• print_list() 함수

우리는 연결 리스트의 노드를 방문하면서 노드를 대상으로 다양한 작업을 할 수 있다. 예를 들면 노드를 방문하면서 노드의 데이터를 화면에 출력할 수 있다. 연결 리스트 안의 모든 노드의 데이터를 출력하는 함수 print_list 를 작성해보자. 노드의 링크값이 NULL 이 아니면 계속 링크를 따라 가면서 노드를 방문한다. 링크값이 NULL 이면 연결 리스트의 끝에 도달한 것이므로 반복을 중단한다. 방문 연산은 연결 리스트에서 가장 기본이 되는 연산이므로 그 개념을 확실하게 이해해야 한다.

void print_list(ListNode *head)
{
  for (ListNode *p = head; p != NULL; p = p->link)
    printf("%d->",p->data);
  printf("NULL \n");
}