[자료구조 - C언어] 자료구조 제11강: 연결 리스트 - 개념과 기본 동작들(5)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

1. 연결 리스트 순회하기

• 순회(traverse): 연결 리스트의 노드들을 처음부터 순서대로 방문하는 것
• p = p → next;
  • 그 다음 주소로 넘어감

//입력된 문자열 word와 동일한 단어를 저장한 노드를 찾아
//그 노드의 주소를 반환하는 함수
Node *find(char *word){
    //연결 리스트를 순회할 노드 포인터 p
    //처음에는 첫 번째 노드를 가리키도록
    Node *p = head;
    while(p != NULL){    //p가 null이 될 때 까지
        if (strcmp(p-> data, word) == 0)
            return p;         //찾으면 그 주소를 반환
        p = p -> next;       //그렇지 않으면 다음 주소로 넘어감
    }
    return NULL;          //연결리스트를 끝까지 순회했지만 원하는 데이터를 찾지 못함
}

1-1. index 번째 노드의 주소 반환

//연결리스트의 Index 번째 노드의 주소를 반환하는 함수
Node *get_node(int index){
    //에러처리
    if(index<0)
        return NULL;

    Node *p = head;
    //노드 개수 < index를 방지하기 위해
    //p==NULL이라면 NULL을 리턴
    for (int i=0;i<index && p!=NULL; i++)
        p = p -> next;
    //index만큼 전진한 후 p 리턴
    return p;
}

 

2. index 번째 위치에 새로운 노드 삽입하기

int add(int index, char *item){
    if(index<0)
        return 0;

    //index가 0이라면 맨 앞에 삽입
    if(index==0){
        add_first(item);
        return 1;
    }

    //index 번째 위치에 삽입이기 때문에
    //index-1 번째 주소값이 필요
    Node *prev = get_node(index-1);
    if(prev !=NULL){
        add_after(prev, item);
        return 1;
    }

    return 0;
}

void add_first(char *item){
    Node *temp = (Node *)malloc(sizeof(Node));
    temp -> data = item;
    temp -> next = head;
    head = temp;
}

int add_after(Node *prev, char *item){
    if(prev == NULL)
        return 0;

    Node *temp = (Node *)malloc(sizeof(Node));
    temp -> data = item;
    temp -> next = prev -> next;
    prev -> next = temp;

    return 1;
}

 

3. index 번째 위치의 노드 삭제하기

Node *remove(int index){
    if(index<0)
        return NULL;
    if (index==0)
        return remove_first();

    Node *prev = get_node(index-1);
    if(prev==NULL)
        return NULL;
    else
        return remove_after(prev);
}

Node * remove_first(){
    if(head == NULL){
        return NULL;
    }
    else{
        Node *temp = head;
        head = head -> next;
        return temp;
    }
}

Node * remove_after(Node *prev){
    Node *temp = prev -> next;
    if(temp == NULL){
        return NULL;
    }
    else{
        prev -> next = temp -> next;
        return temp;
    }
}

 

4. 입력된 스트링을 저장한 노드를 찾아 삭제하기

• 입력된 데이터를 통해 노드를 삭제하려면
  • 검색 → 삭제 과정을 거쳐야 한다.
  • 연결 리스트를 순회해서 데이터를 비교한 후 삭제할 노드를 찾았다!

  Node *remove(char *item){
      Node *p = head;
      while(p!=NULL && strcmp(p->data, item)!=0){
        p = p->next;
      }
  }

  • 하지만 노드를 삭제하기 위해서는 삭제할 노드가 아니라
    • 삭제할 노드의 직전 노드의 주소가 필요하다.(remove_after())
      

      

  • 포인터를 2개(p, q)를 사용해서
    • p는 삭제할 노드를 찾는 역할
    • q는 p를 한 칸 뒤에서 따라가며 삭제할 노드의 직전 노드의 주소를 저장하는 역할

Node *remove(char *item){
    Node *p = head;
    Node *q = NULL;

    //일치하지 않는 동안
    while(p!=NULL && strcmp(p->data, item)!=0){
        q = p;                  //q는 p를 한 칸 뒤에서 따라가는 역할
        p = p->next;    //p는 한칸 전진
    }
    if(p=NULL)
        return NULL;
    if(q=NULL)          //첫 번째 노드를 삭제해야할 경우
        return remove_first();
    else
        return remove_after(q);
}

 

5. 오름차순 정렬된 연결 리스트에 새로운 데이터 삽입하기

void add_to_ordered_list(char *item){
    Node *p = head;
    Node *q = NULL;

    while(p!=NULL && strcmp(p->data, item) <= 0){
        q = p;
        p = p -> next;
    }

    if(q=NULL)
        add_first(item);
    else
        add_after(q, item);
}

• strcmp는 비교하는 두 string이
  • 동일하면 0을 리턴
  • 다른 경우 str1 > str2 (= 사전식 순서로 str1이 str2보다 더 뒤쪽에 나오면) → 음수를 리턴
    • strcmp(str1, str2) > 0 : str2보다 str1이 사전식 순서로 더 뒤쪽

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=s-c2IbG0E_I