연결 리스트로 구현한 리스트

1. 연결 리스트로 구현된 리스트

• 리스트는 스택이나 큐와 같은 선형 자료구조이지만 중간에 요소를 삽입하거나 삭제할 수 있고, 이 때문에 배열로 구현하면 많은 자료의 이동이 필요해 비효율적이다. 연결리스트를 이용하면 이 문제를 해결할 수 있다.

1) 리스트의 구조

• 연결 리스트에는 node가 사용되는데, 각 노드에는 항목의 자료를 저장하는 데이터 다음 노드를 가리키는 링크 필드가 있다.
• 연결 리스트를 이용하면 더 이상 배열이 필요 없으며, 리스트의 시작은 헤드 포인터(head pointer)만 있으면 된다. 노드들은 연속적으로 연결되어 있고, 마지막 노드의 링크 필드에는 NULL이 저장되어 더 이상 연결된 노드가 없음을 알린다.

2) 단순한 연산들

• 공백상태 검사 연산 is_empty()는 head가 NULL인지를 검사하면 된다.
• 포화상태 검사 연산은 더 이상 의미가 없다.
• 리스트의 초기화 연산 init_list()에서는 head를 NULL로 바꾸면 된다.

3) 연결리스트를 이용한 리스트의 항목 참조 연산

• 아래 소스는 포인터 p를 이용해 각 노드를 방문하는 방법을 보여준다.
• 처음에는 p가 head가 되어야 하고, 매 반복마다 p=p->link가 되어야 한다.

Node* get_entry(int pos){//연결리스트를 이용한 리스트의 항목 참조 연산
  Node* p = head;
  for(int i=0;i<pos;i++,p=p->link)
    if(p==NULL)
      return NULL;
  return p;
}

4) 연결리스트를 이용한 리스트의 크기 연산

• size()는 head에서부터 하나씩 다음 노드를 따라가면서 몇 개의 노드가 연결되어는지 확인해야 한다. 마지막 노드의 링크 필드 NULL이므로, 이를 검사해서 반복을 종료하면 된다.

int size(){//연결리스트를 이용한 리스트의 크기 연산
  Node* p;
  int count = 0;
  for(p=head;p != NULL; p=p->link)
    count++;
  return count;
}

5) 연결리스트를 이용한 리스트의 항목 교체 및 탐색 연산

• pos위치의 항목을 찾아 e로 교체하는 연산 replace(pos, e)를 위해서는 get_entry(pos)를 이용해 먼저 노드를 찾아야 한다.
• pos번째 노드가 NULL이 아니면 데이터 필드를 e로 교체하면 된다.
• find(e)연산은 head에서부터 순서대로 모든 노드를 방문하면서 검사하고, 만약 일치하는 노드가 있으면 반환한다. 만약 찾는 항목이 없으면 NULL을 반환해야 한다.

void replace(int pos,Element e){//연결리스트를 이용한 리스트의 항목 교체 및  탐색 연산
  Node* node = get_entry(pos);
  if(node!=NULL){
    node->data = e;
  }
}
Node* find(Element e){
  Node* p;
  for(p = head; p! = NULL ; p=p->link)
    if(p->data == e)
      return p;
  return NULL;
}

6) 연결리스트를 이용한 리스트의 정리 연산

• 리스트를 비우는 clear_list()는 동적으로 할당된 모든 연결된 노드를 해제해야 한다.
• 리스트가 공백상태가 아닐 동안 계속 맨 앞의 노드를 삭제하면 된다.

void clear_list(){//연결리스트를 이용한 리스트의 정리 연산
  while(is_empty() == 0)
    delete(0);
}

7) 연결리스트를 이용한 리스트의 노드 삽입 연산

(1) 먼저 삽입하려는 노드 N이 C를 가리키게 함.(node->link = before->link;)

(2) 노드 B가 노드 N을 가리키게 함.(before->link = node;)

void insert_next(Node *before, Node *node){//연결리스트를 이용한 리스트의 노드 삽입 연산
  if(node != NULL){
    node->link = before->link;
    before->link = node;
  }
}

8) 연결리스트를 이용한 리스트의 삽입 연산

void insert(int pos, Element e){//연결리스트를 이용한 리스트의 삽입 연산.
  Node *new_node, *prev;
  new_node = (Node*)malloc(sizeof(Node));//새로운 노드를 할당하고 데이터 필드는 항목 val, 링크 필드는 NULL로 초기화함.
  new_node->data = e;
  new_node->link = NULL;
  if(pos==0){// 리스트의 맨 앞에 삽입하는 경우는 new_node 다음에 head를 연결해 주고, 이제 head를 new_node로 교체 해주면 됨.
    new_node->link = head;
    head = new_node;
  }
  else{ 
    prev = get_entry(pos - 1);리스트의 중간에 삽입하는 경우는 pos-1 위치의 노드 prev를 찾고
    if( prev != NULL)// insert_next(prev,new_node)를 호출하면 됨.
      insert_next(prev, new_node);
    else//만약 prev가 NULL이라면 삽입이 불가능한 위치이므로 동적 할당한 node를 해제하면 됨.
      free(new_node);
  }
}

9) 연결리스트를 이용한 리스트의 노드 삭제 연산

(1) 먼저 노드 removed(삭제할노드)가 N을 가리키도록 함 : removed = before->link;

(2) removed가 NULL이 아닌 경우 노드 B가 노드 C를 가리키게 함. : before->link = removed->link;

(3) removed를 반환 함. : return removed;

Node* remove_next(Node* before){//연결리스트를 이용한 리스트의 노드 삭제 연산
  Node* removed = before->link;
  if(removed != NULL){
    before->link = removed -> link;
  }
  return removed;
}

10) 연결리스트를 이용한 리스트의 삭제 연산

void delete(int pos){//연결리스트를 이용한 리스트의 삭제 연산
  Node* prev, *removed;
  if(pos==0 && is_empty() == 0){//리스트가 공백상태가 아니면서 맨 앞 노드를 삭제하는 경우에 대한 처리.
    removed = head;//head를 removed에 복사
    head = head->link;//head는 다음 노드를 가리키게 한 다음.
    free(removed);// removed에 메모리 해제
  }
  else{// 그렇지 않으면pos-1번째 노드를 찾아
    prev = get_entry(pos - 1);
    if(prev != NULL){//이 노드가 NULL이 아니면
      removed = remove_next(prev);// remove_next()로 연결리스트에서 꺼낸 후
      free(removed);// 메모리 해제.
    }
  }
}