[자료구조] 단순 연결 리스트(LinkedList) 노드의 삽입 연산

노드의 삽입 연산

단순 연결 리스트의 노드를 삽입하는 방법은 다음과 같다.

1. 삽입할 노드를 준비한다.

2. 새 노드의 데이터 필드에 값을 저장한다.

3. 새 노드의 링크값을 지정한다.

4. 리스트의 앞 노드에 새 노드를 연결한다.

 

다음과 같은 단순 연결 리스트의 '월'과 '금' 사이에 새 원소 '수'를 삽입하는 과정을 예로 들어보자.

단순 연결 리스트의 예시

 

 1. 삽입할 노드 준비 : 삽입할 새 노드로 만들 공백 노드(150번지의 노드)를 메모리에서 할당받는다. 포인터 변수 new가 새 노드를 가리키게 한다.

1. 삽입할 노드 준비

 

2. 새 노드의 데이터 필드값 저장 : new 노드의 데이터 필드에 '수'를 저장한다.

2. 새 노드의 데이터 필드값 저장

 

3. 새 노드의 링크 필드값 저장 : 앞 노드인 '월'의 링크 필드값(200)을 new 노드의 링크 필드에 저장한다. 200은 다은 노드인 '금'의 주소이므로 new 노드는 '금' 노드에 연결된다.

3. 새 노드의 링크필드값 저장

 

 

4. 리스트의 앞 노드에 새 노드 연결 : 앞 노드인 '월' 노드의 링크 필드에 new 노드의 주소값인 150을 저장하여 '월' 노드가 new 노드와 연결되도록 한다.

4. 리스트의 앞 노드에 새 노드 연결

 

다음과 같은 방법으로 단순 연결 리스트에서는 삽입 연산을 할 때 물리적 순서를 유지하기 위해 원소들을 이동시키지 않아도 된다. 링크 필드의 포인터값에 대한 연산만으로 삽입 연산을 쉽게 수행할 수 있다.

 

리스트의 첫 번째 노드 삽입

void insertFirstNode(Node** Head, char* x) {Node* new = (Node*)malloc(sizeof(Node)); //노드의 생성
    strcpy(new->data, x);
    new->link = *Head;
   *Head = new;
}

 

2   // 삽입할 새 노드 new를 할당한다.

3   // new 노드의 데이터 필드에 x를 저장한다.

4   // new 노드의 링크 필드에 헤드(첫번째 노드)의 값을 저장하여 new 노드가 Head 다음의 노드와 연결되도록 한다.

5   // Head 노드는 맨 앞에서 첫번째 노드인 new 노드를 가르키도록 한다.

 

리스트의 중간 노드 삽입(주어진 pre 노드 뒤에 삽입)

void insertMiddleNode(Node** Head, Node* pre, char* x) {
    Node* new = (Node*)malloc(sizeof(Node));
    strcpy(new->data, x);
 
    if (*Head == NULL) {
        new->link = NULL;
       *Head = new;
    }
    else {
        new->link = pre->link;
        pre->link = new;
    }
}

 

5  // Head가 공백이면, 즉 공백 리스트이면 new 노드를 첫번째이자 마지막 노드로 연결한다.

6  // new 노드의 링크값을 NULL로 하고 (마지막 노드니까)

7  // Head 노드가 맨 앞에서 첫번째 노드인 new 노드를 가르키도록 연결한다.

9  // 리스트가 공백 리스트가 아니면

10  // new 노드의 링크값에 주어진 pre 노드의 링크값을 저장하여 new 노드와 pre노드 다음의 노드와 연결한다. 

11  // pre 노드의 링크값에 new를 연결시켜 pre 노드는 new 노드를 가르키도록 한다.

 

리스트의 마지막 노드 삽입

void insertLastNode(Node** Head, char* x) {
    Node* new = (Node*)malloc(sizeof(Node));
    Node* tmp;
 
    strcpy(new->data, x);
    new->link = NULL;
 
    if (*Head == NULL) {
       *Head = new;
    }
    else {
        tmp = *Head;
        while (tmp->link != NULL) {
            tmp = tmp->link;
        }
        tmp->link = new;
    }
}

 

5  // new 노드의 데이터 필드에 값을 저장한다.

6  // new 노드는 마지막 노드로 삽입되기에 링크필드 값을 NULL로 저장한다.

8  // 공백리스트면

9  // new 노드를 리스트의 시작 노드로 연결한다.

11  // 공백리스트가 아니면

12  // tmp 노드를 첫번째 노드로 저장하여

13 // tmp 노드의 링크 필드값이 NULL이 아니면, 즉 tmp 노드가 마지막 노드가 아니면

14  // tmp 노드를 다음 노드로 연결시켜 tmp 노드가 마지막 노드가 될때까지 반복한다.

16  // new 노드를 마지막 노드(tmp 노드)로 연결한다.